pattern heroPT–23LeetCode Extension

Matrix traversal

Treat the grid as row and column coordinates and find the formula for where a cell goes. Then walking or rotating it is one pass over the cells by that formula, with no extra copies of the grid.

Variant
P10 Matrix traversalSpiral · 1×

Example problem: read the 3 × 4 matrix [[2, 7, 4, 9], [6, 0, 5, 3], [8, 11, 1, 10]] in spiral order, clockwise from the top-left corner.

012301227496053811110result
not read yetjust addedin the resultthe answer

Start with an empty result

result = []top = –bottom = –left = –right = –
01/27
restart · back · play · step
Speed
1function spiral(m):
2 result = []
3 top, bottom, left, right = edges of m
4 while top <= bottom and left <= right:
5 add top row, left to right
6 top = top + 1
7 add right column, top to bottom
8 right = right - 1
9 if top <= bottom and left <= right:
10 add bottom row, right to left
11 bottom = bottom - 1
12 add left column, bottom to top
13 left = left + 1
14 return result

← → step · space play/pause

How to recognise

a 2D grid walked in an unusual order (spiral, diagonals, layers), turned or flipped, or changed in place with O(1) extra memory: rotate, set zeroes, Game of Life, a Sudoku check.

How to solve problems like this

  1. Write down what changes with each step: which index moves and which stays fixed.
  2. Keep the part still to do as simple bounds: four boundaries for a spiral, a layer number for rings.
  3. After each side or pass, shrink the bounds, and check they have not crossed before the next one.
  4. Test a 1 × n and an n × 1 matrix: off-by-one errors show up there first.

Variant: Rotate

The same, but the grid is rotated in place. A rotation splits into two mirror flips, and each flip is just swapping cells in pairs, so no second grid is needed.

  1. Write where a cell goes as a formula, then find flips that build it: transpose, reverse rows, reverse columns.
  2. Swap pairs so that every pair is visited once: in a transpose, only cells right of the diagonal.
  3. To mark rows and columns in place (set matrix zeroes), use the first row and first column as the markers, and remember separately whether they had a zero themselves.
  4. When every cell needs the old values of its neighbours (Game of Life), keep old and new state in the same cell: 2 = was alive, now dead; 3 = was dead, now alive. Decode it in a second pass.

Where it's used

  • Images in memory. An uncompressed image is usually stored as one long line of pixels, row after row. The pixel in row y and column x sits at y × width + x.
  • NumPy. NumPy keeps a table as one line of numbers plus two steps: how far to jump to the next row and to the next column. Transposing just swaps the steps; no data is copied.
  • Rotating photos. jpegtran turns a JPEG by 90° without losing quality: it transposes and flips the blocks the picture is made of instead of compressing it again.