Spiral traversal of a Python grid

Why this matters

Some jobs read a grid in an order that is not row by row. A game might light up the tiles of a board from the outside in. A drawing program might paint a frame, then the frame inside it. Interviewers use spiral order to test loop control, because the loop has to stop at exactly the right moment. One wrong number in a loop bound gives a missing value or a value printed twice.

This lesson builds the method one step at a time. The two-dimensional arrays lesson of this module shows spiral order in a short section. Here you will learn why the four boundaries move the way they do, see what breaks when a check is missing, and write a program that fills a grid in a spiral instead of reading one.

Words you need first

A matrix is a grid of values with rows and columns. In Python you store one as a list of lists. The first pair of brackets picks the row and the second picks the column. grid[2][1] is row 2, column 1.

Counting starts at 0. Row 0 is the top row, and column 0 is the left column.

A boundary is a row or column number that marks an edge of the part you have not visited yet. There are four.

• top is the first row that is still unvisited.
• bottom is the last row that is still unvisited.
• left is the first column that is still unvisited.
• right is the last column that is still unvisited.

The unvisited part is always a rectangle. Its top left corner is at (top, left), and its bottom right corner is at (bottom, right). Both edges count as part of the rectangle. At the start the rectangle is the whole grid, so top is 0, bottom is the last row index, left is 0, and right is the last column index.

A rectangle with top equal to bottom still has one row. A rectangle with top greater than bottom has no rows at all, and the loop must stop.

The idea: peel one ring at a time

Imagine the grid as a set of rings, like the rings of a tree trunk, with the outer ring on the outside. A spiral reads the outer ring in full, then moves inward and reads the next ring. Each ring is one row thinner at the top and bottom, and one column thinner at the left and right.

Reading one ring takes four trips, one for each side.

1. Along the top, from left to right, left to right.
2. Down the right side, from top to bottom, top to bottom.
3. Back along the bottom, from right to left, right to left.
4. Up the left side, from bottom to top, bottom to top.

After each trip you move the matching boundary one step inward. The top trip moves top down by one, so the top row is never read again. The right trip moves right left by one, the bottom trip moves bottom up by one, and the left trip moves left right by one.

Notice that the right trip starts at top, which was already moved down. The corner cell at the end of the top row was read by the top trip, so the right trip must not read it a second time.

Worked example 1: a 3 by 3 grid

Here is a small grid. Read it as three rows of three values.

1 2 3
4 5 6
7 8 9

Start with top 0, bottom 2, left 0 and right 2. The table shows each trip. The last column shows the boundaries after the trip finishes.

After step 4 the rectangle has shrunk to the single centre cell, which holds 5. Step 5 reads it, and top moves to 2. Now top is greater than bottom, so the rectangle is empty and the loop stops. The full order is 1, 2, 3, 6, 9, 8, 7, 4, 5.

The program

The function below has the spiral method. It returns the values in spiral order as a list. A Python list grows as you add items, so it is a good fit when you do not know the final count in advance.

Output:

square: [1, 2, 3, 6, 9, 8, 7, 4, 5]
wide:   [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
row:    [1, 2, 3]
column: [1, 2, 3]
empty:  []

The wide grid has 3 rows and 4 columns, so it is not square. The rectangle shrinks by one row at the top and bottom, and by one column at the left and right, which is why the method works on any shape. A single row and a single column both come out in order, because one of the trips reads everything and the other trips find nothing left to read.

The empty grid has no rows at all. The first check in the function returns an empty list before it touches grid[0]. Without that check, grid[0] would raise an IndexError.

The range range(right, left - 1, -1) counts down from right to left and includes left. A range never includes its stop value, which is why the stop is left - 1.

Worked example 2: why the two checks are needed

The bottom trip and the left trip each have an if check in front of them. Remove the checks and read what happens on a single row.

Take the grid [[1, 2, 3]]. It has one row, so top and bottom both start at 0. After the top trip, top becomes 1, but bottom is still 0. The unvisited part now has no rows, because top is below bottom.

The right trip runs next, but it has no rows to read, so it does nothing. right becomes 1. Without the bottom check, the bottom trip still runs. It reads the columns from right down to left, which means row 0 again, and it adds 2 and 1 a second time. Here is the output of the version without the two checks, run on the single row and on the 3 by 3 grid:

one row: [1, 2, 3, 2, 1]
square:  [1, 2, 3, 6, 9, 8, 7, 4, 5]

The square still comes out right, which is why this bug is easy to miss. The bug shows up only when a row or a column is left alone after the earlier trips.

The rules are simple. The bottom trip may run only when top is less than or equal to bottom, which means at least one row is still unvisited. The left trip may run only when left is less than or equal to right, which means at least one column is still unvisited. The while loop checks both boundaries too, so the loop ends when the rectangle is empty.

Worked example 3: filling a grid in a spiral

Reading a spiral is one direction of the problem. The other direction is writing. Suppose you need an n by n grid filled with the numbers 1 to n times n, placed in spiral order. The grid for n equal to 4 should look like this:

 1  2  3  4
12 13 14  5
11 16 15  6
10  9  8  7

The loop skeleton is the same as the reading version. The only change is that each trip writes a number into the grid. The variable value holds the next number to write. Each write is followed by value += 1, so each cell gets a new number.

Output:

[1, 2, 3, 4]
[12, 13, 14, 5]
[11, 16, 15, 6]
[10, 9, 8, 7]
[[1]]
[[1, 2, 3], [8, 9, 4], [7, 6, 5]]

The grid of size 4 matches the picture above. The grid of size 1 is a single cell that gets the value 1, because the top trip fills it and every later trip finds nothing left to do. The grid of size 3 shows that the number 9 lands in the centre, after the spiral has gone around the outside.

The line grid = [[0] * n for _ in range(n)] makes n separate rows. Writing [[0] * n] * n would make n references to one row, and changing one cell would change it in every row at once.

Worked example 4: a grid with an even size

The 3 by 3 grid has one centre cell, so the last trip reads a single value. A 4 by 4 grid does not have a centre cell, and its last ring is a 2 by 2 block. Fill a 4 by 4 grid with the values 1 to 16 in row order:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

Start with top 0, bottom 3, left 0 and right 3.

Step 8 needs a closer look. Its check left <= right passes, because left is 1 and right is 1. The loop inside the trip then has no rows to read, since it runs from bottom, which is 1, up to top, which is 2. The next check at the top of the while loop sees that top is greater than bottom and stops. No special code is needed for the last step, because the loop checks handle it.

Running spiral on the 4 by 4 grid from 1 to 16 prints this order:

[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

The 4 by 4 grid is read in two rings. The outer ring has 12 cells, and the inner ring has the last four, 6, 7, 11 and 10.

Checking the method on many shapes

A spiral is correct when it reads every cell exactly once. You can test that without working out each answer by hand. Build a grid of each shape, fill every cell with a number that is different from the others, run the spiral, and check that the output has one value per cell. The program below tries every shape from 1 by 1 up to 5 by 5.

Output:

shapes passed: 25 of 25

The grid is filled with 1 up to rows times cols, so a correct spiral returns those same numbers in some order. The check sorts the output and compares it with 1, 2, 3 and so on. A missing cell makes the output too short. A repeated cell makes the sorted list differ from 1 to n. Either one prints a failed line with the output, which makes the bug easy to find.

Any task that treats a grid as nested rings, read from the outside in, uses the same four trips as this lesson. The shapes change, but the boundaries and the checks do not.

Common mistakes

1. Using the row count as the column limit. A grid has a row count and a column count, and they are often different. The function has to take the width from the first row, len(grid[0]). Here is a bug that uses len(grid) for the right boundary, run on a 2 by 4 grid.

Output:

[1, 2, 6, 5]

There is no error message, so the wrong answer is easy to miss. The function reads only columns 0 and 1, and the values 3, 4, 7 and 8 are never visited. Run the same function on a 4 by 2 grid, and it reads a column that does not exist. The row grid[0] has two columns, and the loop asks for column 2, so Python stops with this error:

Traceback (most recent call last):
  File "main.py", line 22, in <module>
    print(bad_right([[1, 2], [3, 4], [5, 6], [7, 8]]))
          ~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "main.py", line 7, in bad_right
    order.append(grid[top][c])
                 ~~~~~~~~~^^^
IndexError: list index out of range

The fix is to read the width from len(grid[0]), as the function in this lesson does.

2. Leaving out the two checks. The symptom is a value printed twice. On a single row, the output [1, 2, 3, 2, 1] shows the values 2 and 1 read a second time. The fix is the two if checks shown in worked example 2.

3. Using a strict comparison in the loop. Some people write top < bottom and left < right in the while line, because it looks like the loop should stop when the rectangle is small. It stops too early. Run on the 3 by 3 grid, the strict version misses the centre value:

Output:

strict square: [1, 2, 3, 6, 9, 8, 7, 4]
strict row: []

The value 5 is missing. When the rectangle is a single row or a single column, top equals bottom or left equals right, and the strict check ends the loop before that last cell is read. On a single row the output is empty. The fix is <= in both places.

4. Reading grid[0] before checking that the grid has rows. An empty grid written as [] has length 0, so grid[0] does not exist. Python stops the program with IndexError: list index out of range. The check if len(grid) == 0 must come before the line that reads len(grid[0]).

5. Forgetting to move a boundary. The function in this lesson moves right in the line right -= 1. If that line is missing, the right boundary stays where it was, so the next ring reads the same columns again. Here is the square grid run with right -= 1 removed:

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

The output has 11 values for a grid of 9 cells, which is the first sign of this bug. The 9 appears twice, because the bottom trip reads row 2 from column 2 and the right trip already read that cell. The 6 appears twice too, because the next ring's top trip reads row 1 from column 1 to column 2, and column 2 was already read. The count check in the section above catches this mistake, because the count is 11 instead of 9.

Practice

Try each one before you read the answer. Save each program as main.py and run it with python3 main.py.

1. Trace the spiral by hand on the grid [[1, 2, 3], [4, 5, 6]]. Write the values in the order they are visited.

Show the answer

The order is 1, 2, 3, 6, 5, 4. The top trip reads 1, 2, 3, and top becomes 1. The right trip reads row 1 at column 2, which is 6. Then right becomes 1. The bottom trip reads row 1 from column 1 back to column 0, which gives 5 and then 4. The left trip has no rows left between bottom and top, so it reads nothing. The function returns [1, 2, 3, 6, 5, 4].

2. The grid has rows 1 to 4, 5 to 8, 9 to 12 and 13 to 16, one row after another. Write the spiral order, then find the sum of all the values you visit.

Show the answer

The order is 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10. The sum is 136, which is the sum of the numbers 1 to 16. Every cell is visited exactly once, so the total is the same as adding every cell in the grid, whatever order the spiral uses.

3. Predict the output of spiral for three grids. The first has one cell holding 7. The second has zero rows, so it is []. The third has three rows, where the rows are 1 and 2, 3 and 4, and 5 and 6.

Show the answer

The output is [7] for the single cell, because the top trip reads it and every other trip finds nothing to read. The output is [] for the grid with zero rows, because the first check returns an empty list. The output for the 3 by 2 grid is [1, 2, 4, 6, 5, 3]. The top trip reads 1 and 2, and top becomes 1. The right trip reads rows 1 and 2 of column 1, which gives 4 and 6, and right becomes 0. The bottom trip reads the single cell at row 2, column 0, which is 5, and bottom becomes 1. The left trip reads row 1 of column 0, which is 3. Check that your prediction matches before you move on.

4. Write a function sum_spiral(grid) that returns the sum of the values in spiral order. Use spiral from this lesson.

Show the answer

def sum_spiral(grid):
    total = 0
    for value in spiral(grid):
        total += value
    return total

The loop takes each value from the list in order and adds it to total. Python also has sum(spiral(grid)), which does the same work in one call. Calling sum_spiral on the grid from exercise 2 gives 136.

Summary

• A spiral keeps four boundaries, top, bottom, left and right, and moves one step inward after each side.
• The top side is read left to right, the right side top to bottom, the bottom side right to left, and the left side bottom to top.
• The loop runs while top <= bottom and left <= right, so an empty rectangle ends it.
• The bottom and left trips need their own checks, or a single row or column is read twice.
• The column limit comes from len(grid[0]), not from the number of rows.
• The same four boundaries can fill a grid in spiral order, as in the generate example.