parikshan

spiral-matrix

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

The story

A graphics engineer at Adobe is implementing a "ripple" effect for Photoshop. The effect emanates from the centre of an image outward, but the pipeline works inside out: it processes pixels in concentric rings so the per-ring cost can be parallelised. The same pattern shows up in Figma's layer-bounds calculation, in MapReduce shuffles that read keys in a ring-by-ring order to balance worker load, and in the physical layout of CCD sensors that read pixels in a serpentine spiral.

That is spiral-matrix. It asks you to visit every cell of a 2-D grid in spiral order, starting at the top-left corner and walking clockwise: across the top row, down the right column, across the bottom row, up the left column, then inward by one layer and repeat.

What's actually being asked

Given an r x c matrix of integers, return every element in spiral order on a single line, space-separated. The walk starts at (0, 0) and turns clockwise; each cell is visited exactly once.

The naive approach

Direction-vector simulation: keep a visited boolean matrix, start at (0, 0) facing right, and at each step look at the next cell in the current direction. If it is out of bounds or already visited, turn clockwise; otherwise step into it. Continue until you have collected r * c cells. Works, costs O(r * c) time and O(r * c) extra memory for the visited array, and is fiddlier to debug than the layer walk because the turn logic is more code.

The key insight

A spiral is layers of rings. Each ring has four sides: a top row walked left-to-right, a right column walked top-to-bottom, a bottom row walked right-to-left, and a left column walked bottom-to-top. After walking a side, that side no longer belongs to any inner ring, so you move the corresponding boundary inward.

Tracking four boundaries top, bottom, left, right (all inclusive) reduces the problem to four straight-line walks in a loop, with two careful checks for the case when a ring collapses to a single row or column before all four sides are walked.

Step-by-step approach

  1. Initialise top = 0, bottom = r - 1, left = 0, right = c - 1. Output list result = [].
  2. While top <= bottom and left <= right:
    • Walk j from left to right at row top. Append matrix[top][j]. Then top += 1.
    • Walk i from top to bottom at column right. Append matrix[i][right]. Then right -= 1.
    • If top <= bottom, walk j from right down to left at row bottom. Append matrix[bottom][j]. Then bottom -= 1.
    • If left <= right, walk i from bottom down to top at column left. Append matrix[i][left]. Then left += 1.
  3. Return result.

The two guard checks before the third and fourth walks are essential. After incrementing top and decrementing right, the ring might have collapsed to a single row (if top > bottom) or a single column (if left > right). Without the guards, the bottom row or left column gets re-emitted, producing duplicates.

Worked example

matrix = [[1, 2, 3, 4],
          [5, 6, 7, 8],
          [9, 10, 11, 12]]
  • Start: top=0, bottom=2, left=0, right=3.
  • Top row: 1, 2, 3, 4. top=1.
  • Right column from row 1 to 2: 8, 12. right=2.
  • Check top <= bottom (1 <= 2): yes. Bottom row from col 2 to 0: 11, 10, 9. bottom=1.
  • Check left <= right (0 <= 2): yes. Left column from row 1 to 1: 5. left=1.
  • Loop again: top=1, bottom=1, left=1, right=2.
  • Top row from col 1 to 2: 6, 7. top=2.
  • Check loop condition: top=2 > bottom=1, exit.
  • Result: 1 2 3 4 8 12 11 10 9 5 6 7. Matches the spec.

Now the collapsed-ring case:

matrix = [[1, 2, 3, 4, 5]]   # 1 x 5
  • top=0, bottom=0, left=0, right=4.
  • Top row: 1, 2, 3, 4, 5. top=1.
  • Right column from row 1 to 0: empty loop (1 > 0). right=3.
  • Check top <= bottom: 1 <= 0 is false. Skip bottom row.
  • Check left <= right: 0 <= 3 is true. Left column from row 0 to 1: but bottom is now 0 and top is 1, so the loop range(bottom, top - 1, -1) is range(0, 0, -1) which is empty. left=1.
  • Loop condition: top=1 > bottom=0, exit.

Result: 1 2 3 4 5. The guards prevent re-emitting any cell.

Complexity

  • Time: O(r * c), each cell appended exactly once.
  • Space: O(1) beyond the output list, which is necessarily O(r * c).

The four-boundary version uses no visited matrix and is the tightest possible solution by space.

Why guards on the inner two walks

Consider a 2 x 5 matrix. After walking the top row (left-to-right, 5 cells) and the right column (top-to-bottom, 1 more cell), the ring has top=1, bottom=1, left=0, right=3. The bottom row walk now runs right-to-left at row 1, visiting 4 cells. After that, bottom -= 1 makes bottom = 0. The left column walk then runs from bottom=0 down to top=1, which is the wrong direction; the loop body never executes. The guard if left <= right is technically true (0 <= 3) but the range itself is empty, so nothing breaks.

The dangerous case is when the matrix is exactly one row tall. After the top-row walk, top = 1 and bottom = 0. The right-column walk runs an empty range. Without the if top <= bottom guard, the bottom-row walk would run at row bottom = 0, revisiting every cell of the top row in reverse. Test it with a 1 x N input and you will see the bug instantly.

This is the matrix-walk lesson that transfers everywhere: when boundaries can collapse, guard the dependent walks.

Common pitfalls

  • Skipping the guards: re-emits cells in non-square matrices. Always test with 1xN and Mx1 inputs.
  • Using range(left, right) instead of range(left, right + 1): the boundaries are inclusive. The off-by-one drops the last cell of each side.
  • Mixing (row, col) and (x, y) conventions: x usually means the horizontal axis, which is the column index. AI agents are particularly bad at this; pick (row, col) and never write (x, y) again.
  • Using a visited matrix when you do not need to: correct but wastes O(r * c) memory. The four-boundary walk is the standard.

Where this shows up in the enterprise

  • Adobe Photoshop, Lightroom: ripple, vignette, and radial-blur filters process pixels ring-by-ring around a centre point. Spiral order is the access pattern.
  • Figma and Canva: bounding-box redraw and dirty-rectangle tracking walk regions in ring order to coalesce updates.
  • NVIDIA CUDA programming: tiled matrix processing on GPUs often uses a spiral or Morton-order traversal to maximise cache locality across thread blocks.
  • MapReduce at Google and Hadoop: shuffle phases that read intermediate keys in a ring-by-ring fashion balance load across reducers more evenly than row-major reads.
  • Astronomy at the JPL: CCD sensor pixel-readout algorithms scan in spiral patterns to minimise dark-current accumulation differences across the chip.
  • Robotics path planning: spiral search patterns are the default coverage strategy when a robot has no prior map.

The pattern is universal: any problem that asks for ring-by-ring traversal, layer-by-layer processing, or boundary-walk iteration is the same shape as spiral-matrix.

Variants you'll see elsewhere

  • spiral-matrix-ii: fill an n x n matrix with 1..n^2 in spiral order. Same boundary walk, but you write instead of read.
  • spiral-matrix-iii: walk starting from an arbitrary cell with a fixed clockwise direction sequence. Direction-vector simulation is cleaner here.
  • rotate-image: in-place 90-degree rotation. Uses the same (i, j) -> (j, n-1-i) index map that underlies the spiral order. See [[rotate-image]].
  • set-matrix-zeroes: traverses the matrix in row-major order with marker cells. Different pattern, but the discipline of separating the read pass from the write pass transfers.

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 suite for spiral-matrix covers 1xN, Mx1, square, and rectangular cases, plus a maximum 100x100 input to test asymptotic correctness.
  2. Hints are graduated. The first nudges you to think about peeling rings. The second introduces the four boundaries. The fourth is the full skeleton including the two guard checks that catch the collapse case.
  3. The AI assistant can Explain, Review, Find Bugs, Add Comments, or Optimise for small integrity costs in exam mode and free in practice. Ask it to verify your guards by tracing a 1x5 matrix.
  4. The dispute flow lets you escalate a contested verdict to a human reviewer.

If you can ship a four-boundary walk with both guards, traced through 1xN and Mx1 inputs in your head, the pattern is yours.

In the AI-integrated workspace

In your future work, an agent will write the matrix walks for you. Your job is to:

  1. Recognise the ring-walk pattern when a colleague describes processing an image in layers, balancing a shuffle by rotational order, or scanning a tile in spiral order for cache locality.
  2. Tell the agent precisely: "four boundaries top/bottom/left/right, inclusive, with guards before the third and fourth side walks."
  3. Read the agent's code and always test on a non-square matrix, ideally 3 x 4. Agents trained on square examples reliably produce code that breaks on 3 x 4 because the collapse-guard is missing. The primer for this cluster explicitly calls this out.
  4. Watch for (row, col) versus (x, y) confusion. The fastest way to spot it is to ask the agent which axis x refers to, then to look at the output for a 1xN input.

Engineers who can spot the missing guard within two seconds of reading the code save the team a debugging session. Engineers who cannot eventually merge a four-boundary walk that silently re-emits cells on every non-square input.