Katkat
Back

Traverse a Matrix in Clockwise Spiral Order

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Traverse a rectangular matrix in clockwise spiral order without modifying the input. Learn the four-boundary technique and the guards that prevent duplicate visits on the final row or column.

Implement spiral_order(matrix) for a rectangular matrix.

Return all values in clockwise spiral order, beginning at the top-left corner and first moving right. An empty matrix returns an empty list. The input is not modified.

For example, [[1,2,3],[4,5,6],[7,8,9]] returns [1,2,3,6,9,8,7,4,5].

Target O(rows * columns) time and auxiliary space beyond the returned list that does not grow with the matrix dimensions.

Discussion Extensions

  • How would the traversal order change for a counterclockwise spiral?
  • How would you reuse the boundary framework to fill an n by n matrix in spiral order?

Hints

Hint 1

Maintain four live boundaries: Track the top, bottom, left, and right edges of the unvisited rectangle, shrinking one boundary after traversing each side.

Hint 2

Guard the final two sides: Before traversing right-to-left or bottom-to-top, verify that both corresponding boundaries still describe an unvisited row or column. This prevents duplicate output for a single remaining row or column.