6
\$\begingroup\$

I'm looking for a code review, clever optimizations, and good coding practices. Unit testing has been a visual inspection and concluded expectations match. Also, is the space complexity of the extra variable used to swap \$O(1)\$? Typically, is \$O(1)\$ an acceptable space to use when code requires no extra memory?

public final class RotateNinetyInPlace {

    private RotateNinetyInPlace() {}

    private static void transpose(int[][] m) {

        for (int i = 0; i < m.length; i++) {
            for (int j = i; j < m[0].length; j++) {
                int x = m[i][j];
                m[i][j] = m[j][i];
                m[j][i] = x;
            }
        }
    }


    public static void rotateByNinetyToLeft(int[][] m) {
        // transpose
        transpose(m);

        //  swap rows
        for (int  i = 0; i < m.length/2; i++) {
            for (int j = 0; j < m[0].length; j++) {
                int x = m[i][j];
                m[i][j] = m[m.length -1 -i][j]; 
                m[m.length -1 -i][j] = x;
            }
        }
    }


    public static void rotateByNinetyToRight(int[][] m) {
        // transpose
        transpose(m);

        // swap columns
        for (int  j = 0; j < m[0].length/2; j++) {
            for (int i = 0; i < m.length; i++) {
                int x = m[i][j];
                m[i][j] = m[i][m[0].length -1 -j]; 
                m[i][m[0].length -1 -j] = x;
            }
        }
    }


    public static void main(String[] args) {
        int[][] mEven = {{1, 3},
                        {2, 4}};

        rotateByNinetyToLeft(mEven);

        for (int i = 0; i < mEven.length; i++) {
            for (int j = 0; j < mEven[0].length; j++) {
                System.out.print(mEven[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("---------------------------------");

        rotateByNinetyToRight(mEven);

        for (int i = 0; i < mEven.length; i++) {
            for (int j = 0; j < mEven[0].length; j++) {
                System.out.print(mEven[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("---------------------------------");

        int[][] mOdd = {{1, 2, 3},
                        {4, 5, 6},
                        {7, 8, 9}};

        rotateByNinetyToLeft(mOdd);

        for (int i = 0; i < mOdd.length; i++) {
            for (int j = 0; j < mOdd[0].length; j++) {
                System.out.print(mOdd[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("---------------------------------");

        rotateByNinetyToRight(mOdd);

        for (int i = 0; i < mOdd.length; i++) {
            for (int j = 0; j < mOdd[0].length; j++) {
                System.out.print(mOdd[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println("---------------------------------");

    }
}
\$\endgroup\$
  • \$\begingroup\$ this is indeed O(1) space needed (2 indexes and the swap var+ generic stack space) and yes O(1) is indeed what is understood with no extra memory \$\endgroup\$ – ratchet freak Jan 28 '14 at 10:19
  • \$\begingroup\$ I'm not sure if it requires extra memory or not, but I do know it is slower is the trick to use the xor operator (^) to swap two variables. it's something like a=a^b; b=a^b; a=a^b; but I saw (i think on stackoverflow) where someone compared the speeds and it was slower, and another person found it about the same. Food for thought. \$\endgroup\$ – Robert Snyder Jan 28 '14 at 12:48
  • 1
    \$\begingroup\$ @RobertSnyder not in the stack based +JITted java where you'd need to load both on the stack anyway and then you might as well write them out in opposite order, if the JIT optimizer thinks the xor-swap is faster then it will do so. \$\endgroup\$ – ratchet freak Jan 28 '14 at 14:26
  • 1
    \$\begingroup\$ @ratchetfreak yeah it's hard to tell what the compiler will do when it goes to optimize your code. Something that I've always struggled with. \$\endgroup\$ – Robert Snyder Jan 28 '14 at 14:33
  • 2
    \$\begingroup\$ If question is unclear drop by a comment, I will clarify asap. Please read What makes a good question? \$\endgroup\$ – ChrisW Jan 29 '14 at 15:42
12
\$\begingroup\$

You can swap entire rows.

public static void swapRows(int[][] m) {
    for (int  i = 0, k = m.length - 1; i < k; ++i, --k) {
        int[] x = m[i];
        m[i] = m[k];
        m[k] = x;
    }
}

public static void rotateByNinetyToLeft(int[][] m) {
    transpose(m);
    swapRows(m);
}

public static void rotateByNinetyToRight(int[][] m) {
    swapRows(m);
    transpose(m);
}

Rotating right can use swapRows instead of swapping columns too, if the transpose is done afterwards.


About complexity

Time complexity is irrelevant here: implementing rotateByNinetyToRight by calling three times rotateByNinetyToLeft would not change the complexity. Though physically would be three times slower.

However the transpose and swap-rows do two for-loops. One might think that for large matrices that would imply extra memory page swapping. With a bit of juggling one could immediately swap the right points:

...a.
d....
.....
....b
.c...

One could rotate (abcd) to (dabc). But that does not seem to help either in memory swapping. So I think the algorithm is also in physical time sufficiently optimal.

Extra space for x is ofcourse irrelevant.

\$\endgroup\$
  • \$\begingroup\$ nice answer.... BTW, the code I suggested does the exact a-b-c-d rotation for all points in a quadrant. \$\endgroup\$ – rolfl Jan 29 '14 at 17:07
  • \$\begingroup\$ @rolfl yes I checked and gave +1. Liked the how you picked the quarter: [0, m.length/2] x [0, m.length - m.length/2] as it should for odd m.length. \$\endgroup\$ – Joop Eggen Jan 29 '14 at 17:35
  • \$\begingroup\$ I didn't know you could use for loops that way :O \$\endgroup\$ – Michael Fulton May 25 '17 at 20:20
15
\$\begingroup\$

You ask many questions on CodeReview, which in itself is good, but you have to start helping the reviewers actually review your code. You have this habit of dumping code and expecting a review. It does not work that way (very well). For a start, let's review the ideal process for a 'real' review:

  1. you present neat and working code for review.
  2. you include a description of the context of the code - what it does, why it is needed, and what constraints it has.
  3. you provide some specifications or documentation for any complicated or significant algorithms
  4. the reviewer reviews the code, not only for neatness, and style, but to:
    • check the code works the way it is supposed to (by visual inspection)
    • suggest alternative approaches that may achieve the same results faster or in a better way
    • suggest alternative approaches that may produce different results but may be better for other reasons
  5. signs off that the code is:
    • good (or great and gives you a high five)
    • good enough but has some future anticipated improvements
    • not good enough and needs to be fixed then resubmitted

The details, descriptions, references and specifications you provide with the request is essential if the reviewer is going to give a decent review.

On Code review, the process continues with:

  • upvoting answers that are helpful (and down-voting those that are not).
  • accepting answers that (among other answers) best address your concerns.

Your question above is lacking any description of what the code is supposed to do, and how it does it. All you do say is:

  • I want hints and reviews
  • it works
  • what is the complexity

As a result, the only specification available and description of what the code should be doing, is what the code actually does. Or the title of the post....


Bottom line is that you have only given a fraction of what is needed for a good review, so, I will take a stab at doing a review with similar feedback....

A good alternative approach for your code is:

public static void rotateByNinetyToLeft(int[][] m) {

    int e = m.length - 1;
    int c = e / 2;
    int b = e % 2;
    for (int r = c; r >= 0; r--) {
        for (int d = c - r; d < c + r + b; d++) {
            int t   = m[c - r][d];
            m[c - r][d] = m[d][e - c + r];
            m[d][e - c + r] = m[e - c + r][e - d];
            m[e - c + r][e - d] = m[e - d][c - r];
            m[e - d][c - r] = t;
        }
    }
}

This approach is O(n) time complexity (n is the number of pixels in the matrix), and O(1) space complexity

I have tested this and it works.

You can use the right-handed approach for rotateByNinetyToRight

\$\endgroup\$
  • 3
    \$\begingroup\$ The top part should be FAQ'd on meta ;) +1 as soon as votes reload! \$\endgroup\$ – Mathieu Guindon Jan 29 '14 at 15:59
  • \$\begingroup\$ As mat said this is not the place to inform users. Maybe chat on this case would be prefered. Also only because the OP question does not follow the good guidelines you suggested it doesnt mean you should drop the quality of your answer, you might be guiving an incentive for ppl to behave like you to other questions \$\endgroup\$ – Bruno Costa May 28 '16 at 1:18
  • \$\begingroup\$ Hey @BrunoCosta - I guess after 2.5 years things should be cleared up \$\endgroup\$ – rolfl May 28 '16 at 2:23

protected by Jamal Aug 8 '17 at 4:11

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.