Matrices and 2-D traversal

A grid of rows and columns, also called a matrix, is stored in Python as a list of rows. Most grid problems come down to visiting the cells in the right order, and to keeping indexes inside the grid.

A list of rows

grid = [[1, 2, 3, 4, 5],
        [6, 7, 8, 9, 10],
        [11, 12, 13, 14, 15],
        [16, 17, 18, 19, 20]]
R = len(grid)          # rows: 4
C = len(grid[0])       # columns: 5
grid[2][3]             # row 2, column 3: 14

grid[r] is row r, itself a list. grid[r][c] is the cell in row r and column c. Always the row first. Mixing up r and c, or R and C, is the most common grid bug. It hides on square grids, so test on a grid that is not square.

Orders of traversal

Traversal means visiting every cell once. Step through three common orders:

Each order visits all R × C cells once, so each is O(R × C). The spiral needs the most care. It keeps four limits and moves one inwards after each side. The two checks in the middle of the loop matter when one row or one column is left over.

Here is one side, the top row, walked from left to right. Then the top limit moves down one row:

for c in range(left, right + 1):
    visit(top, c)
top += 1

The other three sides work the same way: the right column downwards (then right moves left), the bottom row from right to left (then bottom moves up), and the left column upwards (then left moves right). Repeat while top is at most bottom and left is at most right. Before the bottom row, check again that top is still at most bottom; before the left column, check that left is still at most right. Without these checks a single leftover row or column is visited twice. Writing the whole loop is ARRS-P4.

Neighbours and the edges

Many problems look at the four cells next to (r, c): up, down, left and right. Keep the four moves in a list, and check the limits before you read a cell:

MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dr, dc in MOVES:
    nr, nc = r + dr, c + dc
    if 0 <= nr < R and 0 <= nc < C:
        ...  # grid[nr][nc] is a real neighbour

Moving through a grid cell by cell like this is a graph search. The GRPH station builds on it with breadth-first and depth-first search.

Turning and flipping

Rotating a square grid 90° clockwise sends cell (r, c) to (c, n − 1 − r). In Python:

rotated = [list(row) for row in zip(*grid[::-1])]
transposed = [list(col) for col in zip(*grid)]   # rows become columns

zip(*grid) pairs up the first items of every row, then the second items, and so on, which gives the columns. Both lines build a new grid in O(R × C) time and space. Doing it in place, with swaps, is a good exercise in index arithmetic.

Now try ARRS-P4, The spiral timetable.