Grid Scans

What is this?

Think of painting a room. You do not wander randomly — you work the edges, then move inward, and you know at every moment which strip is finished. That discipline is what these problems need. Each is a grid walked in a particular order, holding a small invariant, with no queue and no visited set.

The three orders here — layer by layer, along one axis from the far end, and cell by cell — cover most matrix problems you will meet.

💡 Fun fact: Rotating the Box is really two problems stacked, and separating them is the whole trick. Settle the stones first, in the box's original orientation where gravity pulls right along each row — a simple write-pointer sweep. Then rotate. Trying to reason about gravity in the rotated frame means thinking about columns and falling simultaneously, and is where most implementations tie themselves in knots.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: name the order and the invariant, and the code follows. Four walls that only shrink; a write pointer that only moves toward the far end; or no order at all, when each cell can be asked its own question.

1. Four shrinking walls

top, bottom, left, right = 0, n - 1, 0, n - 1
val = 1
while top <= bottom and left <= right:
    for c in range(left, right + 1):      # → across the top
        grid[top][c] = val; val += 1
    top += 1
    for r in range(top, bottom + 1):      # ↓ down the right
        grid[r][right] = val; val += 1
    right -= 1
    if top <= bottom:                     # ← back across the bottom
        for c in range(right, left - 1, -1):
            grid[bottom][c] = val; val += 1
        bottom -= 1
    if left <= right:                     # ↑ up the left
        for r in range(bottom, top - 1, -1):
            grid[r][left] = val; val += 1
        left += 1

The two if guards before the third and fourth legs are the entire difficulty. Without them, a single remaining row is traversed left-to-right and then right-to-left, writing the same cells twice. They are only needed on the second pair of legs, because the first two always run when the outer condition holds.

2. A write pointer per row

For gravity pulling right, sweep each row right to left, keeping write at the lowest empty cell available:

row:  [ ".", "#", "*", ".", "." ]      '*' is an obstacle, '#' a stone

scan right → left:
  index 4 "." → write = 4
  index 3 "." →
  index 2 "*" → obstacle: reset write to index 1
  index 1 "#" → stone falls to write=1 (already there), write = 0
  index 0 "." →
result: [ ".", "#", "*", ".", "." ]   the stone is blocked by the obstacle

The obstacle resets the write pointer to just before itself — that is what makes stones pile up against it rather than passing through. After every row is settled, rotate the whole box 90°.

3. No order at all

For the perimeter, each land cell contributes 4 and each adjacency removes 2. Scanning only the right and down neighbours counts each shared border exactly once:

perimeter = 0
for r in range(m):
    for c in range(n):
        if grid[r][c] == 1:
            perimeter += 4
            if r + 1 < m and grid[r+1][c] == 1: perimeter -= 2
            if c + 1 < n and grid[r][c+1] == 1: perimeter -= 2

4. A 30-second worked example (perimeter)

grid          land cells: 3
1 1           adjacencies: (0,0)-(0,1) horizontal, (0,1)-(1,1) vertical → 2
0 1
              perimeter = 4x3 - 2x2 = 12 - 4 = 8

Trace the outline by hand and you will count 8 edges. Note that scanning right and down only is what stops each adjacency being counted from both sides.

5. Where you'll actually meet this

• Image and document processing. Spiral and boundary scans in convolution edge handling and in serialising 2-D buffers.
• Puzzle games. Match-3 and Tetris-style settling is per-column compaction with obstacles.
• GIS and raster analysis. Region perimeter and area from a raster grid, computed per cell rather than by tracing.
• LED and sensor arrays. Hardware addressed in spiral or serpentine order.
• Robotics coverage. Sweep patterns for cleaning or scanning a bounded area.

6. Problems in this chapter

▶ Spiral Matrix II

Fill an n × n grid with 1..n² in spiral order. Four walls that shrink, with the two guards before the return legs.
Pattern: shrinking-wall traversal. Target: O(n²) time, O(1) extra space.

▶ Rotating the Box

Stones fall to the right of their row, blocked by obstacles; then the box is rotated 90° clockwise. Settle first with a per-row write pointer, then rotate.
Pattern: row-wise compaction, then transformation. Target: O(mn) time, O(mn) for the output.

▶ Island Perimeter

Count the coastline of a single island. 4 × land − 2 × adjacent pairs, scanning right and down only.
Pattern: per-cell contribution. Target: O(mn) time, O(1) space.

7. Common pitfalls 🚫

• Missing the guards on the return legs. A single leftover row or column gets written twice, producing duplicated values.
• Settling in the rotated frame. Rotate after gravity, never before or during.
• Not resetting the write pointer at an obstacle. Stones then slide straight past it.
• Sweeping the wrong direction. Gravity pulls toward the far end, so the scan must start there and move backward.
• Counting adjacencies in all four directions. Each shared border would be counted twice; scan right and down only.
• Flood-filling for the perimeter. It works, and it costs O(mn) space for no benefit.
• Assuming a square grid. Only Spiral Matrix II is guaranteed square; the others are m × n.

8. Key takeaways

1. The order is the algorithm. Name it before writing anything.
2. Walls only shrink, and the return legs need their own guards.
3. A write pointer settles a row, resetting at every obstacle.
4. Separate settling from reorienting. Two simple passes beat one clever one.
5. Count contributions when the answer is a sum — no traversal state required.
6. Scan right and down to count each adjacency once.
7. Why interviewers like it: these are precision tests. The idea takes one sentence and the implementation has four places to be off by one.

Order: Spiral Matrix II → Rotating the Box → Island Perimeter.