Given an n × n matrix, rotate it 90 degrees clockwise. Modify the matrix itself; don't allocate another one.
Before you code
Work out where one cell goes. In a clockwise rotation, the cell at row r, column c moves to row c, column n − 1 − r. Check it on the corner (0, 0) of a 3 × 3 matrix: it moves to (0, 2), the top right.
Hints
- A rotation is two simpler moves: transpose (swap
[r][c]with[c][r]), then reverse each row. - When transposing in place, only swap cells above the diagonal (
c > r), or every pair gets swapped twice and nothing changes. - Alternative: rotate four cells at a time, from (r, c) to (c, n−1−r) to (n−1−r, n−1−c) to (n−1−c, r), working ring by ring from the outside.
Production & complexity notes
When solving Rotate image on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Index arithmetic to reinforce the underlying pattern.
What it practices
Mapping positions with index arithmetic, from Index arithmetic.