Spiral Matrix

Problem Statement

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]

Visual:
1 → 2 → 3
        ↓
4   5   6
↑       ↓
7 ← 8 ← 9

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]

Visual:
1 → 2 → 3 → 4
            ↓
5   6   7   8
↑           ↓
9 ← 10← 11← 12

Example 3:

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

Constraints

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

Solution Approach

This problem uses a boundary-tracking approach with simulation.

Key Insight

Track four boundaries (top, bottom, left, right) and shrink them as you complete each edge!

The spiral follows a pattern: Right → Down → Left → Up, repeating until all elements are visited.

Algorithm Steps

1. Initialize boundaries:

   • top = 0 (topmost row)
   • bottom = m - 1 (bottommost row)
   • left = 0 (leftmost column)
   • right = n - 1 (rightmost column)

2. Traverse in spiral order:

   • Move Right: From left to right along top row, then increment top
   • Move Down: From top to bottom along right column, then decrement right
   • Move Left: From right to left along bottom row, then decrement bottom
   • Move Up: From bottom to top along left column, then increment left

3. Repeat while top <= bottom && left <= right

Example Walkthrough

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

Initial: top=0, bottom=2, left=0, right=2

1. Move Right (row 0, col 0→2): Add [1,2,3], top=1
2. Move Down (row 1→2, col 2): Add [6,9], right=1
3. Move Left (row 2, col 1→0): Add [8,7], bottom=1
4. Move Up (row 1→1, col 0): Add [4], left=1
5. Move Right (row 1, col 1→1): Add [5], top=2
6. Done (top > bottom)

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

Why Boundary Tracking?

By maintaining boundaries, we:

• Know exactly which cells to visit next
• Avoid revisiting cells
• Naturally handle edge cases (single row, single column, square)
• Shrink the search space progressively

Time & Space Complexity

• Time Complexity: O(m × n)

  • We visit each cell exactly once

• Space Complexity: O(1)

  • Only using a few variables (not counting output array)
  • If counting output: O(m × n)

Java Solution

import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();

        if (matrix == null || matrix.length == 0) {
            return result;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;

        while (top <= bottom && left <= right) {
            // Move right along top row
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;

            // Move down along right column
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            // Move left along bottom row (if still valid)
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }

            // Move up along left column (if still valid)
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }
}

Python Solution

def spiralOrder(matrix: List[List[int]]) -> List[int]:
    if not matrix:
        return []

    m, n = len(matrix), len(matrix[0])
    result = []

    top, bottom = 0, m - 1
    left, right = 0, n - 1

    while top <= bottom and left <= right:
        # Move right
        for i in range(left, right + 1):
            result.append(matrix[top][i])
        top += 1

        # Move down
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        # Move left (if still valid)
        if top <= bottom:
            for i in range(right, left - 1, -1):
                result.append(matrix[bottom][i])
            bottom -= 1

        # Move up (if still valid)
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1

    return result

Edge Cases

Single Row

Input: [[1,2,3,4]]
Output: [1,2,3,4]

Just move right, no down/left/up needed.

Single Column

Input: [[1],[2],[3],[4]]
Output: [1,2,3,4]

Move right (single element), then down.

Single Element

Input: [[7]]
Output: [7]

Non-Square Matrix

Input: [[1,2,3],[4,5,6]]
Output: [1,2,3,6,5,4]

Works perfectly with boundary tracking!

Related Problems

• Spiral Matrix II (LeetCode 59): Generate n×n matrix in spiral order
• Spiral Matrix III (LeetCode 885): Spiral traversal with starting position
• Rotate Image (LeetCode 48): In-place matrix rotation
• Set Matrix Zeroes (LeetCode 73): Matrix manipulation
• Diagonal Traverse (LeetCode 498): Different matrix traversal pattern

Pattern Recognition

This problem demonstrates:

• Simulation pattern
• Boundary tracking technique
• Direction-based traversal
• Matrix manipulation

Common Mistakes

1. ❌ Not checking top <= bottom before moving left
2. ❌ Not checking left <= right before moving up
3. ❌ Off-by-one errors in boundary updates
4. ❌ Incorrect loop ranges (inclusive vs exclusive)
5. ❌ Forgetting to update boundaries after each direction
6. ❌ Not handling single row/column edge cases

Tips for Interviews

• Visualize: Draw a small 3×3 or 3×4 example and trace the path
• Explain: Mention the four-direction pattern (Right→Down→Left→Up)
• Boundaries: Clearly explain when and why you update each boundary
• Edge Cases: Discuss single row, single column, empty matrix
• Code Carefully: The boundary checks before left/up movements are critical
• Pattern: This is a classic simulation problem
• Extensions: Be ready to discuss Spiral Matrix II (generation)

Follow-Up Questions

1. Q: How would you generate a spiral matrix instead of traversing one?

   • A: See Spiral Matrix II (LeetCode 59) - similar approach in reverse

2. Q: What if you start from the center and spiral outward?

   • A: Reverse the logic - start with tight boundaries and expand

3. Q: Can you do it recursively?

   • A: Yes, process outer layer then recurse on inner submatrix

4. Q: How to handle very large matrices?

   • A: Same approach works - still O(m×n) with O(1) extra space

Complexity Comparison

| Approach | Time | Space | Notes | |----------|------|-------|-------| | Boundary Tracking | O(m×n) | O(1) | Optimal, most common | | Visited Array | O(m×n) | O(m×n) | Works but uses extra space | | Recursive | O(m×n) | O(min(m,n)) | Call stack depth |

Recommendation: Boundary tracking is the standard and most efficient approach.

Visual Pattern

For a 4×4 matrix, the spiral creates concentric rectangles:

Layer 0 (outer):
* * * *
*     *
*     *
* * * *

Layer 1 (inner):
  * *
  * *

Each layer is processed clockwise: Right → Down → Left → Up.

Key Observations

1. Boundaries shrink by 1 after completing each edge
2. Direction changes happen at boundary hits
3. Loop condition top <= bottom && left <= right ensures we stop when boundaries cross
4. Conditional checks before left/up movements handle non-square matrices
5. No visited array needed - boundaries implicitly track visited cells