Problem Description

You are given a 2D matrix with m rows and n columns. Your task is to traverse the matrix in a spiral pattern and return all elements in the order they are visited.

A spiral traversal starts from the top-left corner of the matrix and moves:

• First, to the right across the top row
• Then down along the right column
• Then left across the bottom row
• Then up along the left column
• This pattern continues inward until all elements are visited

For example, given a 3×3 matrix:

1 2 3
4 5 6
7 8 9

The spiral order would be: [1, 2, 3, 6, 9, 8, 7, 4, 5]

The traversal follows the path: start at 1 → move right to 2, 3 → move down to 6, 9 → move left to 8, 7 → move up to 4 → move right to 5.

The solution uses a simulation approach with direction vectors. It maintains the current position (i, j) and tracks visited cells using a boolean matrix vis. The direction is controlled by an index k that cycles through four directions: right (0, 1), down (1, 0), left (0, -1), and up (-1, 0). When the next move would go out of bounds or hit an already visited cell, the direction changes clockwise by incrementing k. This process continues until all m × n elements are collected in the result list.

Intuition

When we think about traversing a matrix in spiral order, we can visualize it like peeling an onion layer by layer, or like walking along the walls of a rectangular room and gradually moving inward.

The key insight is that a spiral traversal follows a fixed pattern of directions: right → down → left → up, and this pattern repeats. Whenever we hit a boundary (either the edge of the matrix or a cell we've already visited), we need to turn 90 degrees clockwise.

This naturally leads us to think about using direction vectors. We can represent the four directions as coordinate changes:

• Right: (0, 1) - row stays same, column increases
• Down: (1, 0) - row increases, column stays same
• Left: (0, -1) - row stays same, column decreases
• Up: (-1, 0) - row decreases, column stays same

By storing these directions in a sequence like dirs = (0, 1, 0, -1, 0), we can cleverly access both x and y components of each direction using consecutive indices. For direction k, the row change is dirs[k] and column change is dirs[k+1].

To track our progress and know when to turn, we need to mark cells as visited. This prevents us from revisiting cells and helps us identify when we've hit the "inner wall" of previously traversed cells. When our next move would either go out of bounds or hit a visited cell, we know it's time to change direction.

The beauty of this approach is its simplicity - we just keep moving in the current direction until we can't, then rotate clockwise and continue. By doing this for exactly m × n steps, we're guaranteed to visit every cell exactly once in spiral order.

Solution Approach

The implementation uses a simulation strategy to traverse the matrix in spiral order. Here's how the solution works step by step:

1. Initialize the necessary variables:

• m, n store the dimensions of the matrix
• dirs = (0, 1, 0, -1, 0) encodes the four directions. Each pair (dirs[k], dirs[k+1]) represents a direction vector
• vis is a 2D boolean array of the same size as the matrix to track visited cells, initialized to False
• i, j represent the current position, starting at (0, 0)
• k is the direction index, starting at 0 (moving right)
• ans is the result list to store elements in spiral order

2. Main traversal loop: The loop runs exactly m × n times to visit every cell:

for _ in range(m * n):
    ans.append(matrix[i][j])  # Add current element to result
    vis[i][j] = True          # Mark current cell as visited

3. Calculate the next position:

x, y = i + dirs[k], j + dirs[k + 1]

This computes where we would move if we continue in the current direction.

4. Check if direction change is needed:

if x < 0 or x >= m or y < 0 or y >= n or vis[x][y]:
    k = (k + 1) % 4

We need to turn clockwise (change direction) if:

• The next position is out of bounds (x < 0 or x >= m or y < 0 or y >= n)
• The next position has already been visited (vis[x][y] is True)

The modulo operation (k + 1) % 4 ensures we cycle through directions 0→1→2→3→0...

5. Move to the next position:

i += dirs[k]
j += dirs[k + 1]

After potentially changing direction, we update our position using the current (possibly new) direction.

The algorithm guarantees that we visit each cell exactly once because:

• We track visited cells to avoid revisiting
• We change direction only when necessary
• The loop runs for exactly the total number of cells

Time complexity is O(m × n) as we visit each cell once, and space complexity is O(m × n) for the visited array and result list.

Example Walkthrough

Let's trace through a small 3×3 matrix to see how the spiral traversal works:

Matrix:
1 2 3
4 5 6
7 8 9

Initial Setup:

• Position: (i, j) = (0, 0)
• Direction index: k = 0 (moving right)
• dirs = (0, 1, 0, -1, 0) where direction vectors are:
  • k=0: right (0, 1)
  • k=1: down (1, 0)
  • k=2: left (0, -1)
  • k=3: up (-1, 0)
• Visited matrix: all False
• Result: []

Step 1: At (0,0), value = 1

• Add 1 to result: [1]
• Mark (0,0) as visited
• Next position: (0,0) + (0,1) = (0,1) ✓ valid
• Move to (0,1)

Step 2: At (0,1), value = 2

• Add 2 to result: [1, 2]
• Mark (0,1) as visited
• Next position: (0,1) + (0,1) = (0,2) ✓ valid
• Move to (0,2)

Step 3: At (0,2), value = 3

• Add 3 to result: [1, 2, 3]
• Mark (0,2) as visited
• Next position: (0,2) + (0,1) = (0,3) ✗ out of bounds!
• Change direction: k = 1 (now moving down)
• New next position: (0,2) + (1,0) = (1,2)
• Move to (1,2)

Step 4: At (1,2), value = 6

• Add 6 to result: [1, 2, 3, 6]
• Mark (1,2) as visited
• Next position: (1,2) + (1,0) = (2,2) ✓ valid
• Move to (2,2)

Step 5: At (2,2), value = 9

• Add 9 to result: [1, 2, 3, 6, 9]
• Mark (2,2) as visited
• Next position: (2,2) + (1,0) = (3,2) ✗ out of bounds!
• Change direction: k = 2 (now moving left)
• New next position: (2,2) + (0,-1) = (2,1)
• Move to (2,1)

Step 6: At (2,1), value = 8

• Add 8 to result: [1, 2, 3, 6, 9, 8]
• Mark (2,1) as visited
• Next position: (2,1) + (0,-1) = (2,0) ✓ valid
• Move to (2,0)

Step 7: At (2,0), value = 7

• Add 7 to result: [1, 2, 3, 6, 9, 8, 7]
• Mark (2,0) as visited
• Next position: (2,0) + (0,-1) = (2,-1) ✗ out of bounds!
• Change direction: k = 3 (now moving up)
• New next position: (2,0) + (-1,0) = (1,0)
• Move to (1,0)

Step 8: At (1,0), value = 4

• Add 4 to result: [1, 2, 3, 6, 9, 8, 7, 4]
• Mark (1,0) as visited
• Next position: (1,0) + (-1,0) = (0,0) ✗ already visited!
• Change direction: k = 0 (now moving right)
• New next position: (1,0) + (0,1) = (1,1)
• Move to (1,1)

Step 9: At (1,1), value = 5

• Add 5 to result: [1, 2, 3, 6, 9, 8, 7, 4, 5]
• Mark (1,1) as visited
• All cells visited!

Final Result: [1, 2, 3, 6, 9, 8, 7, 4, 5]

The traversal creates a clockwise spiral, changing direction whenever hitting a boundary or visited cell, ensuring every element is collected exactly once.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm visits each element in the matrix exactly once. The main loop runs m × n times (where m is the number of rows and n is the number of columns), and in each iteration, it performs constant-time operations: appending to the result list, marking the cell as visited, calculating the next position, and checking boundaries. Therefore, the overall time complexity is O(m × n).

Space Complexity: O(m × n)

The space complexity consists of two main components:

1. The vis (visited) matrix, which has the same dimensions as the input matrix, requiring O(m × n) space to track which cells have been visited.
2. The ans list, which stores all m × n elements from the matrix, also requiring O(m × n) space.

Since both components require O(m × n) space, the total space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Direction Array Indexing

A common mistake is incorrectly accessing the direction vectors when using the compressed format dirs = (0, 1, 0, -1, 0).

Pitfall Example:

# Incorrect: Using wrong indices for direction vectors
next_row = row + directions[direction_idx * 2]      # Wrong!
next_col = col + directions[direction_idx * 2 + 1]  # Wrong!

The compressed array stores directions as consecutive pairs, but the indices are [0,1], [1,2], [2,3], [3,4], not [0,1], [2,3], [4,5], [6,7].

Solution:

# Correct: Proper indexing for compressed direction array
next_row = row + directions[direction_idx]
next_col = col + directions[direction_idx + 1]

2. Updating Position Before Checking All Conditions

Pitfall Example:

for _ in range(num_rows * num_cols):
    result.append(matrix[row][col])
    visited[row][col] = True
  
    # Wrong: Update position immediately
    row += directions[direction_idx]
    col += directions[direction_idx + 1]
  
    # Then check if out of bounds (but we've already moved!)
    if row < 0 or row >= num_rows or col < 0 or col >= num_cols or visited[row][col]:
        # Try to correct by backing out and changing direction
        row -= directions[direction_idx]
        col -= directions[direction_idx + 1]
        direction_idx = (direction_idx + 1) % 4
        row += directions[direction_idx]
        col += directions[direction_idx + 1]

This approach is error-prone and can lead to accessing invalid indices.

Solution: Always calculate the next position first, validate it, then update:

# Calculate potential next position
next_row = row + directions[direction_idx]
next_col = col + directions[direction_idx + 1]

# Check if we need to turn
if (next_row < 0 or next_row >= num_rows or 
    next_col < 0 or next_col >= num_cols or 
    visited[next_row][next_col]):
    direction_idx = (direction_idx + 1) % 4

# Now safely move to the next position
row += directions[direction_idx]
col += directions[direction_idx + 1]

3. Forgetting to Handle Edge Cases

Pitfall Example: Not handling single row or single column matrices properly, or assuming the matrix is always square.

# Wrong assumption: Matrix is always square
for _ in range(num_rows * num_rows):  # Should be num_rows * num_cols!
    ...

Solution: Always use both dimensions correctly:

# Correct: Handle any m×n matrix
for _ in range(num_rows * num_cols):
    ...

4. Incorrect Visited Array Initialization

Pitfall Example:

# Wrong: Creates references to the same list
visited = [[False] * num_cols] * num_rows  # Don't do this!

# This creates num_rows references to the same list
# Modifying visited[0][0] will affect all rows!

Solution: Use list comprehension to create independent rows:

# Correct: Each row is a separate list
visited = [[False] * num_cols for _ in range(num_rows)]

5. Not Handling Empty Matrix

Pitfall Example:

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    num_rows, num_cols = len(matrix), len(matrix[0])  # IndexError if matrix is empty!

Solution: Add a guard clause:

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix or not matrix[0]:
        return []
  
    num_rows, num_cols = len(matrix), len(matrix[0])
    # ... rest of the code