4.2 Rotate Image

4.2.1 Problem Metadata

4.2.2 Description

Rotate an n x n matrix by 90 degrees clockwise in place (without allocating another matrix).

4.2.3 Examples

Input:
[1,2,3]
[4,5,6]
[7,8,9]

Output:
[7,4,1]
[8,5,2]
[9,6,3]

4.2.4 Constraints

  • 1 <= n <= 20

4.2.5 Solution - Transpose + Reverse

4.2.5.1 Walkthrough

The rotation can be decomposed into two steps:

  1. Transpose the matrix along the main diagonal (swap matrix[i][j] with matrix[j][i] for j < i).
  2. Reverse each row (swap columns symmetrically around the vertical midline).

This achieves the 90-degree rotation in-place.

4.2.5.2 Analysis

  • Time Complexity: O(n²)
  • Space Complexity: O(1)

4.2.5.3 Implementation Steps

  1. For each i, j < i, swap matrix[i][j] with matrix[j][i].
  2. For each row, swap matrix[row][left] with matrix[row][right] while moving inward.

4.2.5.4 Code - Java

public void rotate(int[][] matrix) {
    int n = matrix.length;

    // Step 1: Transpose the matrix along the main diagonal
    // Swap matrix[i][j] with matrix[j][i] for all i < j
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }

    // Step 2: Reverse each row (swap columns around the vertical midline)
    for (int row = 0; row < n; row++) {
        int left = 0, right = n - 1;

        // Use two pointers to swap matrix[i][l] with matrix[i][r]        
        while (left < right) {
            int tmp = matrix[row][left];
            matrix[row][left] = matrix[row][right];
            matrix[row][right] = tmp;
            left++;
            right--;
        }
    }
}

4.2.5.5 Code - Golang

func rotate(matrix [][]int) {
    n := len(matrix)

    // Step 1: Transpose the matrix along the main diagonal
    // Swap matrix[i][j] with matrix[j][i] for all i < j
    for i := 0; i < n; i++ {
        // Start j from i+1 to avoid double swapping (upper triangle only)
        for j := i + 1; j < n; j++ {
            temp := matrix[i][j]
            matrix[i][j] = matrix[j][i]
            matrix[j][i] = temp
        }
    }

    // Step 2: Reverse each row (swap columns around the vertical midline)
    for i := 0; i < n; i++ {
        l := 0
        r := n - 1

        // Use two pointers to swap matrix[i][l] with matrix[i][r]
        for l < r {
            temp := matrix[i][l]
            matrix[i][l] = matrix[i][r]
            matrix[i][r] = temp

            l++
            r--
        }
    }
}