48. Rotate Image - Leetcode Solution

Leetcode Problem Link Code Solution Link:

💡 Step-by-Step Thought Process

Understand the problem: Rotate a square n x n matrix 90 degrees clockwise in-place.
Get the matrix dimension n (number of rows or columns).
Transpose the matrix (swap elements across the main diagonal):
- For each i from 0 to n-1, and j from i+1 to n-1, swap matrix[i][j] with matrix[j][i].
Reflect the matrix horizontally (swap elements across the vertical middle):
- For each i from 0 to n-1, and j from 0 to n/2-1, swap matrix[i][j] with matrix[i][n-j-1].

Code Solution

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        
        # Tranpose
        for i in range(n):
            for j in range(i+1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        # Reflection
        for i in range(n):
            for j in range(n // 2):
                matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]
        
        # Time: O(n^2)
        # Space: O(1)

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        // Transpose
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        
        // Reflection
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n / 2; ++j) {
                swap(matrix[i][j], matrix[i][n - j - 1]);
            }
        }
    }
};

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        
        // Reflection
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
    }
}

function rotate(matrix) {
    const n = matrix.length;
    
    // Transpose
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    
    // Reflection
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n / 2; j++) {
            [matrix[i][j], matrix[i][n - j - 1]] = [matrix[i][n - j - 1], matrix[i][j]];
        }
    }
}

Detailed Explanation

Understanding the Problem: Rotate Image

The “Rotate Image” problem requires you to rotate an n × n 2D matrix 90 degrees clockwise, in-place. This means you must rearrange the values inside the matrix without using extra space for another matrix.

For example, given:

1	2	3
4	5	6
7	8	9

The rotated matrix should be:

7	4	1
8	5	2
9	6	3

Why This Problem Matters

Matrix rotation is a core concept in geometry, image processing, and computer graphics. Solving this problem builds your understanding of 2D array manipulation, in-place transformations, and symmetry properties. In interviews, it tests your ability to reason about indexes and operate efficiently with limited memory.

Key Insight: Transpose + Reflect

The trick to solving this problem in-place lies in recognizing a two-step transformation:

Transpose the matrix: Flip it across its main diagonal (top-left to bottom-right).
Reflect the matrix horizontally: Swap elements in each row from left to right.

These two operations, when combined, result in a 90-degree clockwise rotation.

Step-by-Step Explanation

1. Transpose the Matrix

Transposing means turning all rows into columns. For every cell (i, j) above the main diagonal, we swap it with (j, i).

Loop through i = 0 to n - 1
For each i, loop j = i + 1 to n - 1
Swap matrix[i][j] and matrix[j][i]

After transposition, our example becomes:

1	4	7
2	5	8
3	6	9

2. Reflect the Matrix Horizontally

Now we reverse each row to complete the 90° rotation. This swaps the elements on the left with those on the right.

Loop through each row i = 0 to n - 1
For each row, swap elements at positions j and n - j - 1 for j = 0 to n / 2 - 1

Final rotated matrix:

7	4	1
8	5	2
9	6	3

Alternative Approach: Layer-by-Layer Rotation

Another solution involves rotating the matrix layer by layer (or ring by ring). For each square layer from the outside in:

Store the top-left element
Move bottom-left to top-left
Move bottom-right to bottom-left
Move top-right to bottom-right
Move stored top-left value to top-right

Repeat this for each layer. Though this method is more complex, it avoids transposition logic and operates purely by index manipulation.

Time and Space Complexity

Time Complexity: O(n²), since every element in the matrix is accessed and possibly swapped once.
Space Complexity: O(1), because all transformations are done in-place without allocating another matrix.

Edge Cases

1x1 matrix → stays the same after rotation
2x2 matrix → fully rotates in just four swaps
Non-square matrix → not allowed; problem assumes square matrix

Conclusion

The “Rotate Image” problem elegantly demonstrates how simple geometric operations—transpose and reflect—can yield powerful transformations. It’s a prime example of solving problems using patterns and properties rather than brute-force logic. Mastering this in-place algorithm prepares you for more advanced matrix manipulation tasks, like rotating images in-place or optimizing spatial layouts.

Get Personalized Support at AlgoMap Bootcamp 💡

AlgoMap.io

Want Help Cracking FAANG?