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

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

}
}

• 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 Jan 28, 2014 at 10:19
• 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. Jan 28, 2014 at 12:48
• @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. Jan 28, 2014 at 14:26
• @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. Jan 28, 2014 at 14:33
• If question is unclear drop by a comment, I will clarify asap. Please read What makes a good question? Jan 29, 2014 at 15:42

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.

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.

• nice answer.... BTW, the code I suggested does the exact a-b-c-d rotation for all points in a quadrant. Jan 29, 2014 at 17:07
• @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. Jan 29, 2014 at 17:35
• I didn't know you could use for loops that way :O May 25, 2017 at 20:20

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).

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

• The top part should be FAQ'd on meta ;) +1 as soon as votes reload! Jan 29, 2014 at 15:59
• 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 May 28, 2016 at 1:18
• Hey @BrunoCosta - I guess after 2.5 years things should be cleared up May 28, 2016 at 2:23