Blind Plus 100 Visualized

#68 · Math & Geometry

Rotate Image

Rotate an n × n matrix 90 degrees clockwise, in place (this version also returns the matrix so the result can be checked).

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Index mapping of a rotation

A clockwise quarter turn sends the element at (r, c) to (c, n − 1 − r). Applying it four times returns every element to where it started, so elements move in cycles of four.

Memory layout

The matrix is rows of numbers; the rotation permutes cells without changing the layout.

OperationCost
timeO(n²): every cell moves once
spaceO(1) in place, O(n²) with a copy

Transpose + reverse

Mirroring across the main diagonal swaps rows and columns; reversing each row then flips left to right. Together they equal a clockwise turn, and each step is a simple swap loop.

Memory layout

No extra storage beyond one temporary value.

OperationCost
time / spaceO(n²) / O(1)

Why it fits

  • The problem forbids a second matrix, so the permutation must be carried out by swapping cells. Cycles of length four make this possible with a single temporary variable.
  • Decomposing the rotation into reflections (transpose, then flip) trades one hard-to-see four-way swap for two easy two-way swaps.
  • The four-cycles all have a representative in one quadrant, so looping over a quadrant touches every cell exactly once.

Why alternatives degrade

Allocating a rotated copy:
It is correct but breaks the in-place requirement and uses O(n²) memory.
Swapping pairs along a single pass:
A rotation is a permutation made of cycles of length 4; swapping pairs cannot realise it without a third value.
Using linear indices:
The index arithmetic is the same mapping in disguise; it is harder to read and no faster.

Four approaches, from naive to production

1 · beginner

Copy, then write rotated

time O(n²)space O(n²)

Make a copy of the matrix and write each element of the copy to its rotated position (r, c) → (c, n − 1 − r) in the original.

vector<vector<int>> rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> copy = matrix;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            matrix[c][n - 1 - r] = copy[r][c];
        }
    }
    return matrix;
}

Flaws & bottlenecks

  • Uses a whole extra matrix, which the problem forbids.
  • Easy to get the index formula wrong (row/column swapped).
  • Copies every element twice.

Interviewer cross-questions

Why is a copy needed?

Say: Writing to (c, n − 1 − r) overwrites a cell that has not been read yet, so the original values must be kept elsewhere.

How do you derive the mapping?

Say: The first row becomes the last column, read top to bottom. Element (0, c) goes to (c, n − 1); in general (r, c) → (c, n − 1 − r).

How do you avoid the copy?

Say: Rotate groups of four cells at a time, or compose two reflections.

2 · intermediate

Transpose, then reverse each row

time O(n²)space O(1)

Swap every pair of cells mirrored across the main diagonal, then reverse each row. The result is the clockwise rotation, with no extra matrix.

vector<vector<int>> rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int r = 0; r < n; r++) {
        for (int c = r + 1; c < n; c++) {
            int tmp = matrix[r][c];
            matrix[r][c] = matrix[c][r];
            matrix[c][r] = tmp;
        }
    }
    for (auto& row : matrix) reverse(row.begin(), row.end());
    return matrix;
}

Flaws & bottlenecks

  • Makes two passes over the matrix.
  • The transpose loop must start the inner index at r + 1, or the swaps undo themselves.
  • It is a trick: the reason it works needs a short explanation.

Interviewer cross-questions

Why does transpose plus row reversal equal a clockwise turn?

Say: Transposing sends (r, c) to (c, r); reversing the row sends column index c to n − 1 − c, giving (c, n − 1 − r), the clockwise mapping.

How would you rotate counter-clockwise?

Say: Transpose and then reverse each column, or reverse each row first and then transpose.

Why start the inner loop at r + 1?

Say: Each mirror pair must be swapped once. Looping over all c would swap every pair twice and restore the original.

3 · advanced

Rotate layer by layer with four-cell cycles

time O(n²)space O(1)

Process the matrix as nested rings. For each cell on the top edge of a ring, rotate it together with its three partners on the other edges using one temporary variable.

vector<vector<int>> rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer, last = n - 1 - layer;
        for (int i = first; i < last; i++) {
            int offset = i - first;
            int 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;
        }
    }
    return matrix;
}

Flaws & bottlenecks

  • The index arithmetic (last − offset) is easy to get wrong.
  • Needs separate handling in your head for the centre cell of odd sizes (the loops simply skip it).
  • More lines than the transpose approach.

Interviewer cross-questions

Why can a single temporary variable do four moves?

Say: It is a cycle: save one value, shift the other three along the cycle, then place the saved one in the vacated cell.

Why does the inner loop stop at last, not last + 1?

Say: The cell at i = last is the first cell of the next edge (a corner), already handled as part of the cycle that started at i = first.

What about odd n?

Say: The innermost layer is a single cell that maps to itself, and Math.floor(n / 2) layers cover everything else.

4 · expert

Quadrant loop with a four-way swap

time O(n²)space O(1)

Loop over the top-left quadrant ((n + 1) / 2 rows by n / 2 columns) and rotate each cell with its three images: top-left → top-right → bottom-right → bottom-left → top-left.

vector<vector<int>> rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int r = 0; r < (n + 1) / 2; r++) {
        for (int c = 0; c < n / 2; c++) {
            int tmp = matrix[n - 1 - c][r];
            matrix[n - 1 - c][r] = matrix[n - 1 - r][n - 1 - c];
            matrix[n - 1 - r][n - 1 - c] = matrix[c][n - 1 - r];
            matrix[c][n - 1 - r] = matrix[r][c];
            matrix[r][c] = tmp;
        }
    }
    return matrix;
}

Flaws & bottlenecks

  • The two loop bounds (ceiling for rows, floor for columns) are easy to mix up.
  • Dense index expressions are hard to read and review.
  • No obvious way to generalise to rotations other than 90°.

Interviewer cross-questions

Why (n + 1) / 2 rows but n / 2 columns?

Say: For odd n the quadrant must include the middle row segment so that edge cells are not missed, but not the centre column, which would rotate the centre cell with itself and corrupt the cycle count.

How do you know every cell is visited exactly once?

Say: Each four-cycle has one member in the quadrant [0, (n+1)/2) × [0, n/2), and those members are distinct, so every cycle is processed once.

How would you rotate a rectangular matrix?

Say: It cannot be done in place by cycles of four (the shape changes). Allocate the new matrix, or use a transpose-based method that treats the storage as a flat array.

Synchronized code walkthrough

Showing: Copy, then write rotated — shares the player above; click any step to jump.

vector<vector<int>> rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> copy = matrix;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            matrix[c][n - 1 - r] = copy[r][c];
        }
    }
    return matrix;
}