Spiral traversal

Why this matters

A grid often has to be read in an order that is not row by row. A photo viewer might draw the outer border of an image first. A game might check the tiles around a board from the edge inward. A puzzle might ask for the values in spiral order, starting at the top left and winding toward the centre. Each of these tasks needs the same skill: moving through a two-dimensional array while keeping track of which cells are already done.

The spiral is a good practice problem for that skill. The path turns at each corner, and the length of each side changes as the walk goes on. A program that gets the turns wrong by one cell either misses values or prints some of them twice. The method in this lesson is simple once you see it: keep four numbers that mark the edges of the part of the grid still unvisited, and move each edge inward after its side has been read.

The lesson builds on the two-dimensional arrays lesson, where g[r][c] means row r, column c. It uses vector<vector<int>> for the grid. It does not repeat how to build a grid, and it does not cover rotation, which has its own earlier lesson in this module.

The idea: four walls that move inward

Think of a box of tiles with a row of tiles on each side. You walk along the top row from left to right. When you reach the end, you have finished the top row, so you never need to see it again. You step down one row and walk along the right column from top to bottom. Then you walk the bottom row from right to left, and the left column from bottom to top. After those four sides, the outer ring of tiles is done, and what is left is a smaller box in the middle. You repeat the same four walks on that smaller box.

To describe the unvisited part of the grid, the program keeps four numbers.

• top is the index of the first row that is not yet visited.
• bottom is the index of the last row that is not yet visited.
• left is the index of the first column that is not yet visited.
• right is the index of the last column that is not yet visited.

At the start, these are 0, the last row index, 0 and the last column index. For a 3-by-4 grid, that is top = 0, bottom = 2, left = 0 and right = 3. Each walk along a side uses one of these numbers as the fixed index and the other pair as the range. After the walk along the top side, top moves down by one, because that row is finished. After the right side, right moves left by one. The same happens for the bottom and the left side. The four numbers always describe a rectangle of cells that are not yet read.

The loop keeps going while the rectangle still has at least one row and one column, which is written top <= bottom and left <= right. When the rectangle becomes empty, the walk is over.

The idea is easier to see with a small example, so the next section traces one.

Worked example 1: a 3 by 4 grid by hand

Take this grid, with 3 rows and 4 columns:

 1   2   3   4
 5   6   7   8
 9  10  11  12

The start values are top = 0, bottom = 2, left = 0, right = 3. The first pass walks the four sides.

Step 1, top side. Keep top as the row index and walk the columns from left to right. That reads row 0 from column 0 to column 3, so the values are 1, 2, 3, 4. Then top becomes 1, because row 0 is finished.

Step 2, right side. Keep right as the column index and walk the rows from top to bottom. Now top is 1 and bottom is 2, so the rows are 1 and 2. The values in column 3 are 8 and 12. Then right becomes 2, because column 3 is finished.

Step 3, bottom side. The check top <= bottom is true, because 1 is not greater than 2. Walk the columns from right down to left. Now right is 2 and left is 0, so the columns are 2, 1 and 0. Row bottom, which is row 2, gives 11, 10 and 9. Then bottom becomes 1.

Step 4, left side. The check left <= right is true, because 0 is not greater than 2. Walk the rows from bottom up to top. Now bottom is 1 and top is 1, so there is one row to visit, which is row 1. Column 0 at row 1 is 5. Then left becomes 1.

The values so far are 1, 2, 3, 4, 8, 12, 11, 10, 9, 5. The rectangle that is left has top = 1, bottom = 1, left = 1 and right = 2. That is the two middle cells of row 1, which hold 6 and 7.

The second pass starts the loop again. The top side walks row 1 from column 1 to column 2, which gives 6 and 7. Then top becomes 2. The right side walks from row 2 to row 1, which is empty, so right becomes 1. The check top <= bottom is false, because 2 is greater than 1, so the bottom side is skipped. The left side check left <= right is true, but the walk from bottom up to top covers no rows, so it reads nothing. Then left becomes 2. The loop checks top <= bottom again, which is now false, so the loop ends.

The full spiral order is 1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7. Every cell appears exactly once, and the walk visits the outside first.

The program

The program below reads a grid from the input, computes its spiral order with a function, and prints the values on one line. The function takes the grid by constant reference, so it does not copy the grid. It returns a new vector with the spiral order.

Type this into the Input box:

3 4
1 2 3 4
5 6 7 8
9 10 11 12

The program prints:

1 2 3 4 8 12 11 10 9 5 6 7

The output matches the hand trace. Three details in the code need a closer look.

The first is the types. The bounds top, bottom, left and right are int, not size_t. The sizes from grid.size() and grid[0].size() are unsigned, and the bounds must be allowed to go negative. For example, after the right side of a single-column grid is walked, right can become -1. If right were unsigned, -1 would wrap around to a very large number, and the check left <= right would be true when it should be false. The cast static_cast<int>(grid.size()) converts the size once, when the bounds are set.

The second is the empty-grid guard at the top. A grid with no rows, or with rows that have no columns, has nothing to walk. Without the guard, grid[0] would be read from an empty vector, which is undefined behaviour. The guard returns an empty vector before that can happen.

The third is the two if checks in the middle of the loop. They are the subtle part of the method, and they are the reason the next section exists.

Why the guards are needed

The bottom side and the left side are walked only if a row or column is still left. Consider a grid with one row, such as 1, 2, 3 in a single line. After the top side is walked, top becomes 1 and bottom stays 0. The row that was just walked is the only row, so there is nothing left for the right side to read. The right side loop runs from row 1 to row 0, which has no steps, so it does nothing. Then right moves in.

Now the bottom side. Without a guard, the program would walk the bottom row again, from right down to left. The bottom row is row 0, which is the row that was already read. The values would be printed a second time.

The next change removes the guard on the bottom side on purpose, to show the effect. Only the if line goes, and the code inside stays the same:

for (int c = right; c >= left; c--) {
    out.push_back(grid[bottom][c]);
}
bottom--;

With that change, the 3 by 4 grid from the first example prints:

1 2 3 4 8 12 11 10 9 5 6 7 6

The extra 6 comes from the second pass. The bottom side reads row 1, which the top side had already read, so the 6 appears a second time. For a 1-by-3 grid with the guard removed, the program prints 1 2 3 2 1, which repeats the values 2 and 1 after the row has already been read. The guards stop a side from being read when no unvisited cells remain on it.

Worked example 2: a 4 by 5 grid

A larger example shows that the same four steps repeat over several rings. Take this grid, with 4 rows and 5 columns, where the values count up along each row:

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

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

The first ring is the outside edge. The top side reads row 0 and gives 1, 2, 3, 4, 5. Then top is 1. The right side reads column 4 from row 1 to row 3, which gives 10, 15 and 20. Then right is 3. The bottom side reads row 3 from column 3 down to column 0, which gives 19, 18, 17 and 16. Then bottom is 2. The left side reads column 0 from row 2 up to row 1, which gives 11 and 6. Then left is 1.

After the first ring, the values are 1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11 and 6. The unvisited rectangle has top = 1, bottom = 2, left = 1 and right = 3. That is the inner 2-by-3 block, which holds 7, 8, 9, 12, 13 and 14.

The second ring is the top side of that block. It reads row 1 from column 1 to column 3, which gives 7, 8 and 9. Then top is 2. The right side reads column 3 from row 2 to row 2, which gives 14. Then right is 2. The bottom side checks top <= bottom, which is 2 less than or equal to 2, so it is true. It reads row 2 from column 2 down to column 1, which gives 13 and 12. Then bottom is 1. The left side checks left <= right, which is 1 less than or equal to 2, so it is true. It walks column 1 from row bottom up to row top. Now bottom is 1 and top is 2, so that walk has no rows, and nothing is read. Then left is 2.

The second ring has read every cell. The rectangle now has top = 2, bottom = 1, left = 2 and right = 2, which is empty, so the loop stops. The full spiral is:

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

The second ring also shows the empty-range case. After the bottom side, bottom is 1 and top is 2, so the left side loop for (int r = bottom; r >= top; r--) starts with r = 1 and stops at once, because 1 is not at least 2. A loop whose start is already past its end runs zero times, so the left side needs no separate check on the rows.

Worked example 3: filling a grid in spiral order

A second common task is the reverse of traversal: given n, create an n by n grid and fill it with the numbers 1 to n times n in spiral order. The same four boundaries work, with one change. Instead of reading a cell, the loop writes the next number into it.

The function below creates a grid of zeros, sets the four boundaries to the full grid, and fills the sides. A counter named next holds the next value to write. Each time a cell is written, the counter goes up by one.

The program prints:

1 2 3
8 9 4
7 6 5

Read the output as a spiral. The 1 starts at the top left, the numbers go along the top, down the right side, back along the bottom, up the left side, and the 5 is the last value, in the bottom right corner. The same pattern works for any n. The next++ form writes the current value and then moves the counter, so the first write stores 1.

The fill code is the same walk as the traversal, with the read replaced by a write. This is a good sign that the four-boundary method is the right tool. If you understand one direction, the other is almost the same code.

Common mistakes

The first mistake is the missing guard that was shown above. A side is walked when its row or column has already been read, and the output contains repeated values. Its symptom is an output that has more values than the grid has cells. A quick check is to count the values printed. The count must equal rows times cols. For the 3-by-4 grid, the wrong program printed 13 values, and the correct program prints 12.

The second mistake is the wrong comparison type. This loop compiles, but -Wall prints a warning:

vector<vector<int>> grid = {{1, 2}, {3, 4}};
for (int r = 0; r < grid.size(); r++) {
    cout << grid[r][0] << '\n';
}

The compiler reports:

warn.cpp: In function ‘int main()’:
warn.cpp:7:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    7 |     for (int r = 0; r < grid.size(); r++) {
      |                     ~~^~~~~~~~~~~~~

The warning means that r is a signed int and grid.size() is an unsigned number. The fix in the traversal is to store the sizes as int once, with static_cast<int>, and to use int for every index. Or, when the index only goes up from 0, use size_t for both sides of the comparison. Pick one type for each loop and keep it.

The third mistake is a swap of the two indexes. The grid is indexed as grid[row][column], so the top side reads grid[top][c] with c as the column. Writing grid[c][top] instead reads the wrong cells, and for a non-square grid it can read outside the array. With vectors, at checks the index and throws an error when it is out of range. The following program asks for row 2 of a grid that has only 2 rows:

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<vector<int>> grid = {{1, 2, 3}, {4, 5, 6}};
    cout << grid.at(2).at(0) << '\n';
    return 0;
}

The program stops with this message:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 2) >= this->size() (which is 2)

The message names the index that failed (__n, which is 2) and the size of the vector (2). Because the grid has rows 0 and 1 only, index 2 is past the end. Reading the message this way tells you that the row index is the problem, not the column index.

The fourth mistake is to forget that each side shrinks the boundary. If top++ is removed from the first side, the top row is read again on the next ring, and the loop never shrinks the rectangle from above. On the 3 by 4 grid, the output then has 18 values instead of 12. Every side must move its boundary, and each move must happen right after the side is read.

Practice

Exercise 1

Trace the spiral order of this 2-by-2 grid by hand, without running the program:

1 2
3 4

Show the answer.

The answer is 1, 2, 4, 3. The top side reads 1 and 2, then top is 1. The right side reads column 1 from row 1, which gives 4. Then right is 0. The bottom side checks top <= bottom, which is 1 less than or equal to 1, so it reads row 1 from column 0, which gives 3. Then bottom is 0. The left side checks left <= right, which is 0 less than or equal to 0, but the rows from bottom up to top are an empty range, so nothing else is read.

Exercise 2

What does spiralOrder return for a grid with one column and five rows, with the values 1, 2, 3, 4 and 5 from top to bottom?

Show the answer.

The answer is 1, 2, 3, 4, 5. The top side reads row 0, which is 1, and top becomes 1. The right side reads column 0 from row 1 down to row 4, which gives 2, 3, 4 and 5. Then right becomes -1. The bottom side check top <= bottom is true, but its loop runs from right (-1) down to left (0), so it reads nothing. The left side check left <= right is false, so the loop ends.

Exercise 3

Change the input of the traversal program so that it reads a grid with 3 rows and 2 columns, with the values 1 2, 3 4 and 5 6. Predict the output first, then run the program with that input.

Show the answer.

The output is:

1 2 4 6 5 3

The top side reads row 0, which gives 1 and 2. The right side reads column 1 from rows 1 and 2, which gives 4 and 6. The bottom side reads row 2 from column 0, which gives 5. Then bottom is 1. The left side reads column 0 from row 1 up to row 1, which gives 3. After the left side, left is 1 and right is 0, so the loop stops. The output has six values, one for each cell.

Exercise 4

Write a function named countSpiral that takes a grid and returns how many values the spiral visits. Then state, without running the code, what it returns for a grid with r rows and c columns, where both are at least 1.

Show the answer.

The function can be a single line that uses the traversal:

int countSpiral(const vector<vector<int>>& grid) {
    return static_cast<int>(spiralOrder(grid).size());
}

For a grid with r rows and c columns, the answer is r times c. Each cell is visited exactly once, because the boundaries move inward after each side and the guards stop a side from reading a cell that was already read. The count is the same as the number of cells.

Exercise 5

Use the fill function from worked example 3 with n set to 4. Predict the grid first, then run the program and compare.

Show the answer.

The output is:

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

The first row holds 1 to 4. The last column holds 5, 6 and 7 going down. The bottom row holds 8, 9 and 10 going left. The left column holds 11 and 12 going up. The inner 2-by-2 block then holds 13, 14, 15 and 16 in spiral order, starting at the top left of the block.

Summary

• A spiral walk keeps four boundaries, top, bottom, left and right, that mark the part of the grid not yet visited.
• Each side is walked once, and its boundary moves inward right after it is walked.
• The loop runs while top <= bottom and left <= right, so it stops when no cells are left.
• The bottom side and the left side need their own checks, because a single row or column would otherwise be read twice.
• The same four boundaries work for filling a grid with numbers in spiral order.
• Use int for the boundaries, because they can go negative, and convert the sizes once with static_cast<int>.