Problem Explanation

In this problem, you're given a 2D matrix representing an image that is to be rotated by 90 degrees. The aim is to not allocate a new 2D matrix for this rotation but to perform the rotation in-place.

To rotate an image by 90 degrees means that the first row of the matrix will become the last column, the second row the second to last column, and so forth. Here's a visual representation of a 90-degree rotation:

Example

Given input matrix:

1
2
31 2 3
44 5 6
57 8 9

Following 90-degree rotation, it would become

1
2
37 4 1
48 5 2
59 6 3

Solution Explanation

The solution employs two steps to achieve the final result. First, the entire matrix is reversed starting from the first row to the last one. Second, the matrix is transposed, implying that rows and columns are swapped, or in another term, the matrix is reflected along its main diagonal line.

Approach

1. Reverse the given matrix. After reversing the matrix, it looks like this for the above example:

1
2
37 8 9
44 5 6
51 2 3

2. Then swap the elements along the main diagonal of the matrix.

1
2
37 4 1
48 5 2
59 6 3

So in this solution, the standard library function swap was used to exchange the elements, and the reverse was used to reverse the order of the rows of the matrix.

Solution

Python

1
2python
3class Solution:
4    def rotate(self, matrix):
5        matrix.reverse()
6        for i in range(len(matrix)):
7            for j in range(i+1, len(matrix)):
8                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Java

1
2java
3public class Solution {
4    public void rotate(int[][] matrix) {
5        int n = matrix.length;
6        for (int i = 0; i < n / 2; i++) {
7            int[] temp = matrix[i];
8            matrix[i] = matrix[n - 1 - i];
9            matrix[n - i - 1] = temp;
10        }
11        for (int i = 0; i < n; i++)
12            for (int j = i + 1; j < n; j++) {
13                int t = matrix[i][j];
14                matrix[i][j] = matrix[j][i];
15                matrix[j][i] = t;
16            }
17    }
18}

JavaScript

1
2javascript
3var rotate = function(matrix) {
4    matrix.reverse();
5    for (let i = 0; i < matrix.length; i++) {
6        for (let j = i+1; j < matrix[i].length; j++) {
7            let temp = matrix[i][j];
8            matrix[i][j] = matrix[j][i];
9            matrix[j][i] = temp;
10        }
11    }
12};

C++

1
2C++
3class Solution {
4public:
5    void rotate(vector<vector<int>>& matrix) {
6        reverse(matrix.begin(), matrix.end());
7        for (int i = 0; i < matrix.size(); i++) {
8            for (int j = i+1; j < matrix[i].size(); j++) {
9                swap(matrix[i][j], matrix[j][i]);
10            }
11        }
12    }
13};

C#

1
2C#
3public class Solution {
4    public void Rotate(int[][] matrix) {
5        Array.Reverse(matrix);
6        for (int i = 0; i < matrix.Length; i++) {
7            for (int j = i+1; j < matrix.Length; j++) {
8                int tmp = matrix[i][j];
9                matrix[i][j] = matrix[j][i];
10                matrix[j][i] = tmp;
11            }
12        }
13    }
14}

Note

In all these solutions the given matrix is reversed to get the appropriate row positions for the 90-degree rotation. Then, by swapping elements diagonally, we achieve the necessary column positions. It is done in-place without the need for an additional matrix.# Time Complexity

The time complexity of this solution is $O(n^2)$ where $n$ is the number of rows or columns for the given square matrix. This is because we have to go through each element in the matrix at least once.

Space Complexity

The space complexity is $O(1)$ since no extra space i.e., no new data structures are allocated, and the rotation is done in-place.

In conclusion, the methods of reversing and swapping elements along the diagonal line get the matrix rotated clockwise by 90 degrees. As an important note, this method works only with square matrices, where the number of rows equals the number of columns. Also, our approach is efficient in terms of space since the operation is done without allocating an extra matrix to store the rotated information. As per the time complexity, our approach takes quadratic time which is the best we can achieve because visiting all the elements of a matrix requires quadratic time.