Read a grid in spiral order by walking four walls: across the top, down the right, back along the bottom, up the left, then shrink inward.
▼The problem
LeetCode 54 (Medium). Given an m × n matrix, return all of its elements in spiral order: clockwise around the outside from the top-left corner, then inward, ring by ring.
Examples (LeetCode's): [[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5] (walked in scene 6) and [[1,2,3,4],[5,6,7,8],[9,10,11,12]] → [1,2,3,4,8,12,11,10,9,5,6,7] (its second ring is a single row, which is what the two guards are for).
The solution
def spiral_order(matrix):
res = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for c in range(left, right + 1):
res.append(matrix[top][c])
top += 1
for r in range(top, bottom + 1):
res.append(matrix[r][right])
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
res.append(matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
res.append(matrix[r][left])
left += 1
return resTranscript
Spiral Matrix. Given an M by N grid, return every number in spiral order: clockwise around the edge from the top left, then inward, ring by ring.
One to nine in a three by three grid gives one, two, three, six, nine, eight, seven, four, five. Three rows of one to twelve go around the edge, then end on five, six, seven.
The simple way drives like a robot mower: go straight, and turn right at the edge or a mowed cell. It works, but a second grid marks every visited cell: M times N extra space.
The key idea: four shrinking boundaries. Mow the top row left to right, then top moves down. Mow the right column down, then right moves in. Then the bottom row leftward and the left column upward, each pulling its boundary in. Repeat while top is at most bottom, and left at most right.
In code, two checks guard the bottom row and left column: if the last ring is one row or column, they stop us mowing it twice.
Walk one to nine. Top row: one, two, three, and top moves down. Right column: six, nine. Bottom row: eight, seven. Left column: four. The last ring is just five. In three rows of four, the second ring is one row: six, seven. Top has passed bottom, so the check skips the bottom row: six isn't read twice.
Each cell is mowed once: order M times N time, and four boundaries, so constant extra space.
Mow the edge, pull it in, repeat. That's Spiral Matrix.