Medium Boundary Walk Math & Geometry
In plain English: Walk around a matrix in a spiral from the outside in, collecting elements.
Maintain four boundaries (top, bottom, left, right). Traverse right, down, left, up, shrinking the boundary after each pass. Stop when boundaries cross.
Prompt
Given an m x n matrix, return all elements in spiral order.
Try to write it from scratch before scrolling down.
Solution
def spiral_order(matrix):
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for j in range(left, right + 1): # right
result.append(matrix[top][j])
top += 1
for i in range(top, bottom + 1): # down
result.append(matrix[i][right])
right -= 1
if top <= bottom:
for j in range(right, left - 1, -1): # left
result.append(matrix[bottom][j])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1): # up
result.append(matrix[i][left])
left += 1
return result
# Test: spiral_order([[1,2,3],[4,5,6],[7,8,9]])
# == [1,2,3,6,9,8,7,4,5]