Given an m x n matrix, return all elements of the matrix in spiral order.

Examples

Example 1:

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

Example 2:

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

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

Thinking Process

There are two main approaches to solve this problem:

  1. Boundary Tracking: Use four boundaries (top, bottom, left, right) and traverse in spiral order
  2. Direction Simulation: Use direction vectors and mark visited cells to simulate spiral movement
Grid traversal BFS/DFS flood from each cell

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Row/column traversal O(nm) O(1) Simulation, spiral
BFS/DFS on grid O(nm) O(nm) Islands, shortest path
Matrix as graph (this problem) O(nm) O(nm) 4/8-directional neighbors
Transpose / rotate O(nm) O(1) In-place rotation tricks

Solution

class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        result = []
        rows, cols = len(matrix), len(matrix[0])
        up, left = 0, 0
        down, right = rows - 1, cols - 1
        while len(result) < rows * cols:
            # Traverse right along top row
            for col in range(left, right + 1):
                result.append(matrix[up][col])
            # Traverse down along right column
            for row in range(up + 1, down + 1):
                result.append(matrix[row][right])
            # Traverse left along bottom row (if not same as top)
            if up != down:
                for col in range(right - 1, left - 1, -1):
                    result.append(matrix[down][col])
            # Traverse up along left column (if not same as right)
            if left != right:
                for row in range(down - 1, up, -1):
                    result.append(matrix[row][left])
            # Move boundaries inward
            left += 1
            right -= 1
            up += 1
            down -= 1
        return result

Solution Explanation

Approach: Matrix as graph (this problem)

Key idea: There are two main approaches to solve this problem:

How the code works:

  1. Boundary Tracking: Use four boundaries (top, bottom, left, right) and traverse in spiral order
  2. Direction Simulation: Use direction vectors and mark visited cells to simulate spiral movement

Walkthrough — input matrix = [[1,2,3],[4,5,6],[7,8,9]], expected output [1,2,3,6,9,8,7,4,5]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Common Mistakes

  4. Off-by-one errors in boundary conditions
  5. Not handling single row/column cases properly
  6. Incorrect boundary updates after each spiral
  7. Missing edge cases for 1x1 matrices

References

Key Takeaways

  1. Boundary Management: Track four boundaries and move them inward after each complete spiral
  2. Edge Cases: Handle single row/column matrices with conditional checks
  3. Direction Changes: Use direction vectors to simulate spiral movement
  4. Visited Marking: Mark cells as visited to avoid revisiting them