Rotate Image

MEDIUM✓ CHIP-TIMEDLC #48 — FULL STATEMENT ↗

The drill: Turn an n×n matrix a quarter-turn clockwise without allocating a second matrix — the rotation has to happen inside the grid you were given.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A square n×n grid of numbers arrives, and the task is to turn its whole layout a quarter turn clockwise — the value that was in the top-left corner ends up in the top-right, and so on around.

The rotation has to happen inside the very same grid object that was handed in; no second grid gets returned or swapped in as the answer, and nothing outside that grid's own cells may be used to hold the picture while it turns.

Every cell keeps its value, just relocated to its rotated position — row r's values end up filling column n−1−r, read top to bottom.

EX 01

matrix = [[1, 2], [3, 4]]

→ [[3, 1], [4, 2]]

EX 02

matrix = [[1]]

→ [[1]]

1×1 IS A NO-OP

EX 03

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

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

grid sides run from a single cell up to a few hundred
cell values are integers, positive, negative, or zero
the grid is always square, rows equal to columns
rotation is performed in place, on the given grid itself

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A clockwise quarter-turn sends row r to column n−1−r. With a scratch matrix that is one loop; the constraint is doing it in place.

HINT 2 THE STRUCTURE

Two reflections compose into a rotation. Which two reflections are trivial to do in place?

HINT 3 ONE STEP FROM THE ANSWER

Transpose (swap across the main diagonal), then reverse every row. Both are plain in-place swaps.

COACH'S BOARD — THE PATTERN, STEP BY STEP

TRANSPOSE + REVERSEPATTERN · TWO IN-PLACE REFLECTIONSmatrix = [[1,2,3],[4,5,6],[7,8,9]]

STEP 1

3×3 grid. Two in-place reflections compose into a quarter turn: transpose across the diagonal, then reverse every row.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/rotate-image.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for r in range(n):
            for c in range(r + 1, n):
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
        for row in matrix:
            row.reverse()

TIME O(N²)SPACE O(1)PYTHON · RACE PACE · 8 LN

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        rotated = [[matrix[n - 1 - c][r] for c in range(n)] for r in range(n)]
        for r in range(n):
            for c in range(n):
                matrix[r][c] = rotated[r][c]

TIME O(N²)SPACE O(N²)PYTHON · TRAINING PACE · 7 LN

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        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 (int[] row : matrix) {
            for (int i = 0, j = n - 1; i < j; i++, j--) {
                int tmp = row[i];
                row[i] = row[j];
                row[j] = tmp;
            }
        }
    }
}

TIME O(N²)SPACE O(1)JAVA · RACE PACE · 19 LN

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] rotated = new int[n][n];
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                rotated[c][n - 1 - r] = matrix[r][c];
            }
        }
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                matrix[r][c] = rotated[r][c];
            }
        }
    }
}

TIME O(N²)SPACE O(N²)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED