Given N*N matrix, rotate it by 90 degree to left and right without extra memory

Question

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("---------------------------------");

    }
}

Answer 1

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.

Answer 2

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