Obsidian Notes

Rotate Image

5 min read

Description

Rotate Image
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].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

Approach

  • We do 2 things first we transpose the matrix then we reverse it to create the rotate image
  • first loop goes the way it does because we have to skip the diagonal
  • second loop goes this way because we only have to mirror by the diagonal so no only need half

  • ⏱ Time Complexity: O(n²)

    • Two nested loops over an n×n matrix:
    • Transpose: visits each element above the diagonal → ≈ n²/2 swaps
    • Reverse: visits half of each row → ≈ n²/2 swaps
    • Total work ∝ n².

  • 📦 Space Complexity: O(1)

    • In-place swaps only; no auxiliary arrays or recursion.
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 t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }
 
        //reverse
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int t = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = t;
            }
        }
    }
}

Approach 1: Brute Force (Using Extra Matrix)

Intuition: Allocate an additional grid. Map each element at matrix[i][j] to temp[j][n - 1 - i] (since the row becomes the column), then copy the values back.

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] temp = new int[n][n];
 
        // Step 1: Fill temporary matrix with rotated positions
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp[j][n - 1 - i] = matrix[i][j];
            }
        }
 
        // Step 2: Copy back to original matrix
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = temp[i][j];
            }
        }
    }
}
  • Time Complexity:
  • Space Complexity:

Approach 2: Optimal In-Place Solution (Transpose + Reverse)**

Intuition: Rotating a matrix clockwise by consists of two easily repeatable steps:

  1. Transpose: Swap elements across the diagonal (matrix[i][j] matrix[j][i]).
  2. Reverse Rows: Reverse elements horizontally in each row (matrix[i][j] matrix[i][n - 1 - j]).

Intuition for Inner Loop Conditions (j Loops)

Both loop conditions exist for one primary reason: to avoid swapping elements twice and undoing your work.

Transpose Loop (j = i + 1 to j < n)

  • The Problem: If j starts at 0, you swap element (0, 1) with (1, 0). Later in the outer loop, when i = 1 and j = 0, you swap (1, 0) with (0, 1) again. This puts everything back into its original position.
  • The Intuition: You only want to touch the triangle above the main diagonal (top-right).
  • Easy Rule: The diagonal elements (i == j) never move. Setting j = i + 1 ensures you only look at elements strictly to the right of the diagonal, swapping each pair exactly once.

Reverse Row Loop (j = 0 to j < n / 2)

  • The Problem: Reversing a row means swapping the left side with the right side. If you loop all the way to the end (j < n), you swap the left items to the right half, and then continue past the center to swap them right back to where they started.
  • The Intuition: You only process the left half of each row and swap it with its mirror partner on the right side (n - 1 - j).
  • Easy Rule: Meet in the middle. Stopping at n / 2 ensures you hit the center crease of the row without flipping things twice.
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
 
        // Step 1: Transpose matrix (swap matrix[i][j] with matrix[j][i])
        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;
            }
        }
 
        // Step 2: Reverse each row
        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 - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}
  • Time Complexity:
  • Space Complexity: auxiliary space

Backlinks