parikshan

rotate-image

Difficulty: Medium  ·  Topic: Math, Matrix & Heaps  ·  Practice it on parikshan: /practice/rotate-image/start

The story

A user opens a photo in Apple Photos that was taken sideways. They tap "Rotate Right". The app must rotate every pixel of the image 90 degrees clockwise. The image is 4032 by 4032 on a recent iPhone, so allocating a second buffer of equal size doubles peak memory at the moment the user is least patient. Same problem in Lightroom for raw images, in Figma for canvas rotations, in TikTok's video editor for in-feed adjustments.

That is rotate-image. The operation is conceptually trivial, but doing it in place, in linear cells with constant extra memory, is one of those problems where the right decomposition makes a frustrating index puzzle into two clean passes.

What's actually being asked

You are given an n x n integer matrix representing an image. Rotate it 90 degrees clockwise in place. The output is the rotated matrix, printed row by row.

The naive approach

Allocate a fresh n x n matrix out. For each (i, j), set out[j][n-1-i] = mat[i][j]. Copy out back into mat. Time O(n^2), space O(n^2). Correct, but the spec asks for in place because the production use case (a photo editor on a phone) cannot afford the doubled memory at peak.

The key insight

A 90-degree clockwise rotation sends the cell at row i, column j to row j, column n-1-i. Doing that map directly with one buffer requires rotating four cells at a time (the four corners of each ring), which is correct but error-prone. The cleaner trick is to factor the rotation into two simpler operations, each of which is in place.

Decomposition: transpose, then reverse each row.

  • The transpose swaps mat[i][j] with mat[j][i] for every i < j. After this, the original rows are columns.
  • Reversing each row then sends mat[j][i] to mat[j][n-1-i]. That is exactly the rotation map.

Why this works: the rotation map (i, j) -> (j, n-1-i) decomposes as a composition of (i, j) -> (j, i) (transpose) and (j, i) -> (j, n-1-i) (row reverse). Both primitives are in place, both are linear in the matrix size, and the composition is exactly the 90-degree clockwise rotation.

There are two related rotations you can build from the same primitives. 180 degrees is reverse rows then reverse the order of rows (or just reverse the flat array). 90 counter-clockwise is transpose, then reverse the order of rows (or reverse rows then transpose, depending on which side of the equation you compose on).

Step-by-step approach

  1. Transpose in place. For i from 0 to n - 1, for j from i + 1 to n - 1, swap mat[i][j] with mat[j][i]. Note the j > i bound: it swaps each pair exactly once. If you wrote j from 0 to n - 1, every pair would be swapped twice, leaving the matrix unchanged.
  2. Reverse each row. For each row i, reverse mat[i] in place.
  3. Return / print the matrix.

Worked example

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

After transpose (swap mat[0][1] with mat[1][0], mat[0][2] with mat[2][0], mat[1][2] with mat[2][1]):

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

After reversing each row:

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

That is the expected 90-degree clockwise rotation. Trace the corners: the original top-left 1 is now top-right; the original top-right 3 is now bottom-right; the original bottom-right 9 is now bottom-left; the original bottom-left 7 is now top-left. Clockwise.

Why the decomposition is the right answer

The alternative is the four-cell rotation: for each ring, hold the top-left cell in a temporary, then rotate four cells around the ring in one chain of assignments. It is also O(n^2) time and O(1) extra space, but the index arithmetic is painful:

mat[i][j] <- mat[n-1-j][i]
mat[n-1-j][i] <- mat[n-1-i][n-1-j]
mat[n-1-i][n-1-j] <- mat[j][n-1-i]
mat[j][n-1-i] <- saved

Anyone reviewing this has to verify four index formulas and the loop bounds (i in [0, n/2), j in [i, n-1-i), which is itself subtle). The transpose-then-reverse decomposition has obvious correctness from the index map, two trivial sub-passes, and reviews itself in twenty seconds. Ship the decomposition.

Complexity

  • Time: O(n^2). The transpose visits n * (n - 1) / 2 pairs; row reversal does n * n / 2 swaps. Both linear in matrix cells.
  • Space: O(1) extra. Both sub-passes are in place; only a constant number of swap temporaries are needed.

Common pitfalls

  • Transposing twice: the j loop bound is i + 1 to n - 1, not 0 to n - 1. The latter swaps every pair twice, leaving mat unchanged. A 3x3 input that comes back unchanged is the symptom.
  • Forgetting the row reverse: gives the transpose, not the rotation. The matrix looks rotated in some sense but the columns are wrong.
  • Reversing first, then transposing: gives a 90-degree counter-clockwise rotation, the opposite direction. Mathematically equivalent if you also negate the rotation angle, but not what the spec asks.
  • Mixing in-place and copy semantics: writing mat = [row[::-1] for row in zip(*mat)] works in Python but allocates a new matrix. The spec asks for in place, so do the swaps explicitly.

Where this shows up in the enterprise

  • Apple Photos, Google Photos, Adobe Lightroom: in-place rotation in the image editor when the user taps "Rotate". The decomposition is what keeps peak memory near 1x image size instead of 2x.
  • Figma, Sketch, Adobe XD: rotating layers and design components. The math is the same; the surrounding code handles bounding boxes and snapping.
  • NumPy and TensorFlow: np.rot90 and tf.image.rot90 are implemented as transpose plus reverse. Read the source; the decomposition is right there.
  • Game engines (Unity, Unreal): tile-based level rotation in 2D games. The pattern matters for procedural-generation tooling that flips and rotates pre-authored chunks.
  • Medical imaging (DICOM viewers at Siemens Healthineers, GE Healthcare): rotating CT and MRI slices for radiologist viewing angles. In-place rotation matters because the slices are large (512x512x16-bit) and there are hundreds of them.
  • Satellite imagery at Planet Labs and Maxar: orienting captured tiles to a common north-up frame before stitching.

The decomposition pattern (factor a hard transformation into a composition of easy ones) recurs throughout linear algebra and graphics. Rotate-image is the smallest possible introduction to it.

Variants you'll see elsewhere

  • Rotate 90 counter-clockwise: reverse each row first, then transpose. Or equivalently, transpose first, then reverse each column (which is the same as reversing the order of rows).
  • Rotate 180: reverse each row, then reverse the order of rows. Or treat the matrix as a flat list and reverse it.
  • Transpose only: the first half of the rotation, useful on its own for matrix multiplication setup.
  • Reflect (horizontal or vertical flip): just one of the two primitives. Horizontal flip is row reverse; vertical flip is row-order reverse.
  • Spiral matrix: walks the matrix in spiral order using the same index intuition but different boundaries. See [[spiral-matrix]].

Once you have the rotation, the other seven of the eight rigid 2D transformations (the dihedral group of the square) are compositions of transpose and the two flips.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

  1. The editor evaluates against public examples and dynamic private tests generated per session. The dynamic suite includes 1x1 (which is unchanged), 2x2 (the smallest non-trivial case), and 100x100 (the upper bound) to verify both correctness and O(1) extra space.
  2. Hints are graduated. The first asks where mat[0][0] ends up. The third reveals the transpose-then-reverse decomposition. The fourth gives the implementation skeleton.
  3. The AI assistant can Explain, Review, Find Bugs, Add Comments, or Optimise at integrity costs in exam mode, free in practice. Use it to verify your transpose loop bounds and to ask why j runs from i + 1 and not from 0.
  4. The dispute flow lets you escalate a contested verdict to a human reviewer.

If you can ship the two-pass solution and articulate why both passes are individually in place, the pattern is yours. Target: three minutes in exam mode.

In the AI-integrated workspace

When you write image-processing or layer-manipulation code at work, an agent will produce most of it. Your edge is:

  1. Recognising the decomposition opportunity when a colleague describes a complex matrix transformation. Reflections, rotations, and shears all factor into simpler primitives.
  2. Telling the agent precisely: "rotate clockwise via transpose then row-reverse, in place." That single instruction blocks the agent from producing the four-cell version with brittle index arithmetic.
  3. Verifying that the transpose loop bound is j > i, not j > 0. The transpose-twice bug is the most common AI failure on this problem.
  4. Stress-testing on 2x2 and on a non-symmetric input like [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. The non-symmetric case reveals direction errors that a symmetric matrix would hide.

Engineers who can name the decomposition are the ones who keep image-processing code maintainable. Engineers who reach for the four-cell version are the ones who get paged when somebody tweaks the index arithmetic.

rotate-image