Spiral Matrix

Given an m x n matrix, return all elements in spiral order (clockwise, starting from the top-left).

Function signature

func SpiralOrder(matrix [][]int) []int

Inputs / outputs

• matrix: 2D slice of integers.
• Return: slice of elements in spiral order.

Example

matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
Output: [1,2,3,6,9,8,7,4,5]

Constraints

• 0 <= m, n <= 1000
• m*n can be 0.

Core idea (near-solution)

Maintain four boundaries:

• top, bottom, left, right.

At each step, traverse one edge and then shrink that boundary. Stop when the boundaries cross.

Invariant: all elements outside the current boundaries have already been emitted.

Algorithm (step-by-step)

1. Initialize top = 0, bottom = m-1, left = 0, right = n-1.
2. While top <= bottom and left <= right:
   • Traverse top row left->right, then top++.
   • Traverse right column top->bottom, then right--.
   • If top <= bottom, traverse bottom row right->left, then bottom--.
   • If left <= right, traverse left column bottom->top, then left++.
3. Return the collected list.

Correctness sketch

• Invariant: all elements outside the current boundaries have already been emitted.
• Boundary/marker invariants ensure each cell is processed correctly.
• In-place encodings preserve original state until updates are finalized.
• Thus the final matrix matches the required transformation.

Trace (hand walkthrough)

Example input:
matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
Output: [1,2,3,6,9,8,7,4,5]

Walk:
- top row (r=0): 1,2,3
- right col (c=2, r=1..2): 6,9
- bottom row (r=2, c=1..0): 8,7
- left col (c=0, r=1..1): 4
- center: 5 -> [1,2,3,6,9,8,7,4,5]

Pitfalls to avoid

• Forgetting the boundary checks before traversing bottom/left edges.
• Off-by-one when the matrix has one row or one column.

Complexity

• Time: O(m*n)
• Extra space: O(1) beyond output.

Implementation notes (Go)

• Maintain top, bottom, left, right bounds.
• Check bounds before each sweep to avoid duplicates.