You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
Constraints:
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000The Rotate Image problem asks you to rotate an n x n matrix by 90 degrees clockwise in-place. Since modifying the matrix without using extra space is required, the key idea is to transform the matrix step by step rather than creating a new one.
A common and efficient strategy is a two-step transformation. First, transpose the matrix (swap matrix[i][j] with matrix[j][i]), which converts rows into columns. Then, reverse each row to achieve the final 90° clockwise rotation. This approach works because the transpose reflects the matrix across its diagonal, and the row reversal aligns elements into their rotated positions.
Another conceptual approach is the layer-by-layer rotation, where elements are rotated in groups of four while traversing each square layer of the matrix from the outside inward.
Both approaches visit each element a constant number of times, leading to O(n²) time complexity while maintaining O(1) extra space due to in-place operations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Transpose + Reverse Rows | O(n²) | O(1) |
| Layer-by-Layer Rotation | O(n²) | O(1) |
take U forward
This approach utilizes two main operations. First, we transpose the matrix, which means flipping it over its diagonal. In other words, swap matrix[i][j] with matrix[j][i]. After transposing the matrix, we reverse each row. This combination results in a 90-degree clockwise rotation.
Time Complexity: O(n^2) - Because we loop through each element once.
Space Complexity: O(1) - No extra space is used, operations are in-place.
1#include <stdio.h>
2
3void rotate(int matrix[][3], int n) {
4 for (int i = 0; i < n; i++) {
5 for (int j = i; j < n; j++) {
6 int temp = matrix[i][j];
7 matrix[i][j] = matrix[j][i];
8 matrix[j][i] = temp;
9 }
10 }
11 for (int i = 0; i < n; i++) {
12 for (int j = 0; j < n/2; j++) {
13 int temp = matrix[i][j];
14 matrix[i][j] = matrix[i][n-j-1];
15 matrix[i][n-j-1] = temp;
16 }
17 }
18}
19
20int main() {
21 int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
22 rotate(matrix, 3);
23 for (int i = 0; i < 3; i++) {
24 for (int j = 0; j < 3; j++) {
25 printf("%d ", matrix[i][j]);
26 }
27 printf("\n");
28 }
29 return 0;
30}The code first transposes the given matrix in place using two nested loops. Then, for each row, it reverses the elements to achieve a 90-degree clockwise rotation.
This approach rotates the matrix layer by layer or ring by ring. Start from the outer layer and move to the inner layer, rotating elements by moving them in groups of four. This involves swapping the elements in four-step rotations.
Time Complexity: O(n^2) - Each individual element is moved once.
Space Complexity: O(1) - Done entirely in place, without additional memory.
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Rotate Image is a popular medium-level matrix problem frequently asked in coding interviews, including FAANG-style interviews. It tests understanding of matrix transformations and in-place operations.
The optimal approach is to transpose the matrix and then reverse each row. This method rotates the matrix 90 degrees clockwise in-place while keeping the time complexity O(n^2) and space complexity O(1).
Transposing swaps rows and columns across the main diagonal, which reorganizes the matrix structure. After transposition, reversing each row aligns elements into their correct rotated positions.
The problem primarily uses matrix manipulation and array indexing. Understanding 2D arrays and in-place element swapping is essential to efficiently rotate the matrix.
The C solution processes the matrix in concentric layers, shifting each element appropriately to its new position during the 90-degree rotation.