Today we are going to take a look at a fairly common interview question! How to Rotate a 2D Matrix by 90 Degrees in Java has a lot to do with basic linear algebra / geometry. Basically we are asked to rotate a rectangular object by +90 degrees. Hence if you are good at Maths, I assume you are going to pick up this question very fast.
First off let us start with a main assumption check. Is the 2D matrix / array a random rectangular, with different height / width or is it a square? Let us assume we do not know at first, so we can assume an M*N matrix.
The trivial solution is to just go through each element and fill a secondary array that’s N*M and put all values in the row in the original array, in a column in the secondary array.
How to Rotate a 2D Matrix by 90 Degrees in Java – Standard
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public void rotate2DMatrix(int[][] matrix) { if (matrix == null || matrix.length == 0) { // Nothing to do. Invalid input. return matrix } int m = matrix.length; int n = matrix[0].length; int[][] rotatedArray = new int[n][m]; for (int i = 0; i < m; i++) { for (int j = 0; j < n); j++) { matrix[j][m-i-1] = matrix[i][j]; } } } |
The above is indeed pretty trivial, a little math will just tell you that generically, for the matrix with dimensions M*N the item at [i][j] will simply got at item [j][M-i-1].
Now let us do a little bit of analysis. Obviously, we are doing two loops, so the time complexity is O(M*N). And also our returned array is of N*M size, so space complexity is also O(M*N)
So far so good, but let us assume that our assumption changed a bit. We do not need to worry about a generic rectangular array. We now know that our array is a square (N*N). Can we do any optimizations?
Well, we cannot do any optimizations in time complexity, as no matter what, we will need to touch and move every element, ending up in a O(N*N) as our previous algorithm. But maybe we can change the array in place, reducing our space complexity to O(1). Let’s give it a try.
How to Rotate a 2D Matrix by 90 Degrees in Java – In place
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
public void rotate2DMatrix(int[][] matrix) { if (matrix == null || matrix.length == 0) { // Nothing to do. Invalid input. return matrix } int n = matrix.length; int[][] rotatedArray = new int[n][n]; int sides = 4; int nextVale; for (int i = 0; i < Math.ceil(n/2); i++) { for (int j = 0; j < Math.floor(n/2); j++) { int currValue = matrix[i][j]; int currI = i; int currJ = j; // for each side, move the curr value there and keep the next curr value. for (int k = 0; k < sides; k++) { int temp = matrix[j][m-i-1]; matrix[j][m-i-1] = currValue; // move currI and currJ to the next side. currI = j; currJ = m-i-1; currValue = temp; } } } } |
The above solution to How to Rotate a 2D Matrix by 90 Degrees in Java simply uses the same formula (i.e. the item at [i][j] will simply go at item [j][M-i-1]), but for all 4 corners of the square at once, to simply do the rotation in place. Note that due to our way of solving this, it could be translated easily to objects with more than 4 sides, or more than 2 dimensions. All you need is to find how each point in the object gets transposed.
For more matrix questions you can take a look at Sum of numbers in a rectangular region in a matrix problem.
If you spot any typos, have a question or want to make any suggestion, post a comment below!
Hope you guys enjoyed it… And I’ll see you guys next time! ;D
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017