1 / 1
07A/191
Rotate matrix by 90 degrees
Problem Statement

Given an N x N 2D integer matrix, rotate it by 90 degrees clockwise. The rotation must be done in-place, meaning the input matrix itself should be modified directly. Do not use another 2D matrix for the final optimal solution.

Examples

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

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

Explanation: The first column becomes the first row, the second column becomes the second row, and so on.

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]]

Explanation: Every element moves from position (i, j) to (j, n - i - 1), giving a 90 degree clockwise rotation.

Custom Notes
  • Memory hook: Clockwise rotation = transpose + reverse every row.
  • Formula hook: old position (i, j) goes to new position (j, n - i - 1).
  • Mistake to avoid: Do not reverse columns after transpose; that gives anti-clockwise rotation.
  • Mistake to avoid: During transpose, start j from i + 1, otherwise you may swap elements twice.
  • Better than brute force because it avoids O(N²) extra space and satisfies the in-place condition.
Brute Force Approach : TC: O(N²), SC: O(N²)
1 / 3

Algorithm: Use an extra matrix and place every element directly at its rotated position.

Pseudo:

  • Create a new N x N matrix called rotated.
  • Traverse every cell (i, j) of the original matrix.
  • Put matrix[i][j] at rotated[j][n - i - 1].
  • Copy rotated back into matrix if the original matrix must be modified.

Time: O(N²)

Space: O(N²)

Why mention it: This is the easiest baseline and helps understand the position-mapping formula.

Better Approach : TC: O(N²), SC: O(1)
2 / 3

Algorithm: Rotate the matrix layer by layer using four-way swaps.

Pseudo:

  • Treat the matrix as square layers from outside to inside.
  • For each layer, move elements in groups of four.
  • Store one value temporarily.
  • Move left to top, bottom to left, right to bottom, and top to right.
  • Continue until all layers are rotated.

Time: O(N²)

Space: O(1)

Interview line: This is in-place, but the index handling is more error-prone than transpose plus reverse.

Optimal Approach : TC: O(N²), SC: O(1)
3 / 3

Algorithm: First transpose the matrix, then reverse every row.

Pseudo:

  • Transpose the matrix by swapping matrix[i][j] with matrix[j][i] for j > i.
  • After transposition, reverse each row.
  • The matrix is now rotated 90 degrees clockwise.

Time: O(N²)

Space: O(1)

Key insight: Transpose converts rows into columns, and reversing each row fixes the order for clockwise rotation.

PCode
1 / 3
START
n = matrix.size
rotated = new n x n matrix

FOR i = 0 TO n - 1
    FOR j = 0 TO n - 1
        rotated[j][n - i - 1] = matrix[i][j]
    END FOR
END FOR

FOR i = 0 TO n - 1
    FOR j = 0 TO n - 1
        matrix[i][j] = rotated[i][j]
    END FOR
END FOR
END
PCode
2 / 3
START
n = matrix.size

FOR layer = 0 TO n / 2 - 1
    first = layer
    last = n - 1 - layer

    FOR i = first TO last - 1
        offset = i - first

        top = matrix[first][i]

        matrix[first][i] = matrix[last - offset][first]
        matrix[last - offset][first] = matrix[last][last - offset]
        matrix[last][last - offset] = matrix[i][last]
        matrix[i][last] = top
    END FOR
END FOR
END
PCode
3 / 3
START
n = matrix.size

FOR i = 0 TO n - 1
    FOR j = i + 1 TO n - 1
        SWAP matrix[i][j] WITH matrix[j][i]
    END FOR
END FOR

FOR i = 0 TO n - 1
    REVERSE matrix[i]
END FOR
END