Spiral Grid Walk
Problem
Read every cell of a rectangular grid in a single inward spiral: across the top row, down the right column, back along the bottom row, up the left column, then repeat on whatever rectangle is left. Return the values in the order they are visited. The grid may have any width and height, including a single row or a single column.
Examples
Input: [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]Input: [[1, 2],
[3, 4],
[5, 6]]
Output: [1, 2, 4, 6, 5, 3]
Why: a tall grid spirals just the sameInput: [[7]]
Output: [7]
Why: edge case, a single cell is a complete spiral on its ownHints
0 / 3
Tracking a heading and turning whenever you hit a cell you already read works, but there is a simpler description of where the spiral is still allowed to go.
The unread part of the grid is always a rectangle. Describe it with four edges and notice that finishing one side moves exactly one edge inward.
Keep a top, bottom, left and right boundary. Walk the top row and raise the top edge, the right column and pull the right edge in, then the bottom row and the left column with their own edges. Before walking the bottom row or the left column, check that the rectangle still has a row or a column left, or a thin leftover strip gets read twice.
Solution
The unread region is always a rectangle, so four boundaries describe it completely and each finished side moves one boundary inward. Walking top, right, bottom and left in that order while shrinking after each side reproduces the spiral without any visited marks. The two guards before the bottom row and the left column matter only at the very end, when the rectangle has collapsed to a single row or column that would otherwise be read twice. Time is O(rows times cols) since each cell is read once, and space is O(1) beyond the output.
def spiral_walk(grid):
if not grid or not grid[0]:
return []
top, bottom, left, right = 0, len(grid) - 1, 0, len(grid[0]) - 1
out = []
while top <= bottom and left <= right:
for c in range(left, right + 1): out.append(grid[top][c])
top += 1
for r in range(top, bottom + 1): out.append(grid[r][right])
right -= 1
if top <= bottom: # a flat leftover row must not repeat
for c in range(right, left - 1, -1): out.append(grid[bottom][c])
bottom -= 1
if left <= right: # a thin leftover column must not repeat
for r in range(bottom, top - 1, -1): out.append(grid[r][left])
left += 1
return out
print(spiral_walk([[1, 2, 3], [4, 5, 6], [7, 8, 9]])) # -> [1, 2, 3, 6, 9, 8, 7, 4, 5]
print(spiral_walk([[1, 2], [3, 4], [5, 6]])) # -> [1, 2, 4, 6, 5, 3]
print(spiral_walk([[7]])) # -> [7]Stuck on the idea rather than the code? Spiral Order covers it.