Spiral Traversal of a Matrix | Spiral Matrix

The Spiral Matrix problem requires visiting and collecting all elements of an $N \times M$ two-dimensional grid in a continuous, inward spiral order (moving Right $\rightarrow$ Down $\rightarrow$ Left $\rightarrow$ Up, and repeating for inner sub-matrices). Unlike problems with multiple competing algorithmic approaches (such as dynamic programming or binary search variants), this problem has a single optimal time-complexity approach: direct boundary simulation. Interviewers use this problem primarily to evaluate implementation cleanliness, index precision, boundary tracking, and the ability to prevent subtle edge-case bugs like duplicate element processing.

1. Problem Statement & Conceptual Requirements

Given an $N \times M$ matrix (where $N$ is the number of rows and $M$ is the number of columns), return an array or list containing all elements of the matrix traversed in spiral order, starting from the top-left cell $(0, 0)$.

Visual Representation of Spiral Order

Consider a $6 \times 6$ matrix where elements are numbered sequentially to illustrate the traversal path:

 1   2   3   4   5   6
20  21  22  23  24   7
19  32  33  34  25   8
18  31  36  35  26   9
17  30  29  28  27  10
16  15  14  13  12  11

The expected output order follows the numbers from $1$ through $36$:

• Outer Layer: $1 \rightarrow 2 \rightarrow \dots \rightarrow 6 \rightarrow 7 \rightarrow \dots \rightarrow 11 \rightarrow 12 \rightarrow \dots \rightarrow 16 \rightarrow 17 \rightarrow \dots \rightarrow 20$
• Second Layer: $21 \rightarrow 22 \rightarrow 23 \rightarrow 24 \rightarrow 25 \rightarrow 26 \rightarrow 27 \rightarrow 28 \rightarrow 29 \rightarrow 30 \rightarrow 31 \rightarrow 32$
• Inner Core: $33 \rightarrow 34 \rightarrow 35 \rightarrow 36$

Note: The spiral path strictly consumes the outermost unvisited perimeter before shrinking inward to process the sub-matrix.

2. Why Is This Problem Unique? (Implementation Focus)

Unlike algorithmic problems where the primary challenge lies in finding an efficient strategy (e.g., reducing $\mathcal{O}(N^2)$ to $\mathcal{O}(N \log N)$), the Spiral Matrix problem tests code architecture and boundary control:

1. Optimal Approach is Unique: There is only one optimal algorithm—visiting each cell exactly once in $\mathcal{O}(N \times M)$ time.
2. Implementation Rigor: The challenge lies in translating a spatial visual process into clean, bug-free iterative loops without introducing off-by-one errors or duplicate element visits.
3. Edge Case Resilience: Matrix dimensions are not always symmetric ($N \neq M$). Single-row matrices ($1 \times M$), single-column matrices ($N \times 1$), and odd-dimension grids require robust condition checks to avoid duplicate reads during direction switches.

3. The Core Mental Model: Four Dynamic Boundaries

To traverse a matrix spirally without using an auxiliary $N \times M$ boolean visited array (which wastes memory), maintain four dynamic boundary pointers:

• top: Points to the top-most unvisited row index (initialized to 0).
• bottom: Points to the bottom-most unvisited row index (initialized to N - 1).
• left: Points to the left-most unvisited column index (initialized to 0).
• right: Points to the right-most unvisited column index (initialized to M - 1).

As each side of the active rectangle is completely traversed, its corresponding boundary pointer is shifted inward (contracted), effectively shrinking the active search grid.

Boundary Contraction Flow

4. Deconstructing the 4-Step Traversal Cycle

Every layer of the spiral consists of four directional sweeps performed in strict order.

Step 1: Traverse Left to Right along top

• Fixed Index: Row index is fixed at top.
• Variable Index: Column index i runs from left to right.
• Action: Push matrix[top][i] into the result list.
• Boundary Shrink: Increment top++ because the entire top row is now fully processed.

Step 2: Traverse Top to Bottom along right

• Fixed Index: Column index is fixed at right.
• Variable Index: Row index i runs from top to bottom.
• Action: Push matrix[i][right] into the result list.
• Boundary Shrink: Decrement right-- because the entire right column is now fully processed.

Step 3: Traverse Right to Left along bottom

• Prerequisite Check: Before running this loop, verify if (top <= bottom). Because top was incremented in Step 1, top may now exceed bottom if the matrix originally had only 1 row or if the remaining sub-matrix has 0 rows.
• Fixed Index: Row index is fixed at bottom.
• Variable Index: Column index i runs from right down to left.
• Action: Push matrix[bottom][i] into the result list.
• Boundary Shrink: Decrement bottom-- because the bottom row is now fully processed.

Step 4: Traverse Bottom to Top along left

• Prerequisite Check: Before running this loop, verify if (left <= right). Because right was decremented in Step 2, right may now be less than left if the matrix originally had only 1 column or if the remaining sub-matrix has 0 columns.
• Fixed Index: Column index is fixed at left.
• Variable Index: Row index i runs from bottom down to top.
• Action: Push matrix[i][left] into the result list.
• Boundary Shrink: Increment left++ because the left column is now fully processed.

5. Matrix Boundary & Pointer Operations Breakdown

The following table summarizes the key properties of each traversal step within a single spiral iteration:

6. Identifying Critical Edge Cases: Single Row and Single Column Matrices

The most common bug in spiral matrix solutions occurs when handling non-square or 1D-like matrices.

Case A: Single Row Matrix ($1 \times M$)

Consider the matrix [[1, 2, 3, 4]] where $N=1, M=4$.

1. Initial pointers: top = 0, bottom = 0, left = 0, right = 3.
2. Step 1 (Right): Visits 1, 2, 3, 4. Pushes all elements.
   • Performs top++ $\rightarrow$ top becomes 1.
3. Step 2 (Down): Loop condition i from top (1) to bottom (0). 1 <= 0 is false. Does not execute.
   • Performs right-- $\rightarrow$ right becomes 2.
4. Step 3 (Left): Without the guard check if (top <= bottom), this loop would run with bottom = 0, traversing i from right (2) down to left (0), re-adding elements 3, 2, 1!
   • Fix: Check if (top <= bottom). Since 1 <= 0 is false, Step 3 is correctly skipped.

Case B: Single Column Matrix ($N \times 1$)

Consider the matrix [[1], [2], [3], [4]] where $N=4, M=1$.

1. Initial pointers: top = 0, bottom = 3, left = 0, right = 0.
2. Step 1 (Right): Visits 1. top++ $\rightarrow$ top becomes 1.
3. Step 2 (Down): Visits 2, 3, 4. right-- $\rightarrow$ right becomes -1.
4. Step 3 (Left): top (1) $\le$ bottom (3), so it runs for i = 0 down to 0 along row bottom (3). But wait! The element at (3, 0) was already visited in Step 2.
   • Fix: Step 4 checks if (left <= right). Since left (0) $\le$ right (-1) is false, Step 4 is correctly skipped, preventing duplicate processing during the upward phase.

7. Complete Algorithm Walkthrough

8. Multi-Language Clean Production Implementations

C++ Implementation

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        
        // Handle empty matrix edge case
        if (matrix.empty() || matrix[0].empty()) {
            return result;
        }
        
        int n = matrix.size();       // Number of rows
        int m = matrix[0].size();    // Number of columns
        
        int top = 0;
        int bottom = n - 1;
        int left = 0;
        int right = m - 1;
        
        while (top <= bottom && left <= right) {
            // 1. Traverse Right along current top row
            for (int i = left; i <= right; ++i) {
                result.push_back(matrix[top][i]);
            }
            top++;
            
            // 2. Traverse Down along current right column
            for (int i = top; i <= bottom; ++i) {
                result.push_back(matrix[i][right]);
            }
            right--;
            
            // 3. Traverse Left along current bottom row (if row still exists)
            if (top <= bottom) {
                for (int i = right; i >= left; --i) {
                    result.push_back(matrix[bottom][i]);
                }
                bottom--;
            }
            
            // 4. Traverse Up along current left column (if column still exists)
            if (left <= right) {
                for (int i = bottom; i >= top; --i) {
                    result.push_back(matrix[i][left]);
                }
                left++;
            }
        }
        
        return result;
    }
};

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }
        
        int n = matrix.length;
        int m = matrix[0].length;
        
        int top = 0;
        int bottom = n - 1;
        int left = 0;
        int right = m - 1;
        
        while (top <= bottom && left <= right) {
            // 1. Traverse Right
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }
            top++;
            
            // 2. Traverse Down
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;
            
            // 3. Traverse Left
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }
                bottom--;
            }
            
            // 4. Traverse Up
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }
        
        return result;
    }
}

Python Implementation

class Solution:
    def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
        if not matrix or not matrix[0]:
            return []

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

        top, bottom = 0, n - 1
        left, right = 0, m - 1
        result = []

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

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

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

            # 4. Traverse Up
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1

        return result

9. Complexity Analysis & Space Trade-offs

Time Complexity: $\mathcal{O}(N \times M)$

• Reasoning: The nested loop system visits every cell in the grid exactly once. There are a total of $N \times M$ elements in the matrix.
• Per-Element Operations: Each element insertion into the output array requires $\mathcal{O}(1)$ basic operations.
• Total Computational Cost: $\mathcal{O}(N \times M)$ time.

Space Complexity: $\mathcal{O}(1)$ Auxiliary Space

• Auxiliary Space: Excluding the memory required to store the returned answer, the algorithm only uses 4 pointer variables (top, bottom, left, right) and a few loop counter variables (i). Thus, auxiliary space is $\mathcal{O}(1)$.
• Output Space: Returning the dynamic array of elements requires $\mathcal{O}(N \times M)$ memory.

10. Common Pitfalls & Interview Debugging Checklist

When implementing this algorithm under time pressure, watch out for these frequent mistakes:

1. Forgetting Inner Guards (top <= bottom & left <= right):

   • Symptom: Output contains duplicate elements or dynamic indexing goes out of bounds on non-square matrices ($1 \times M$ or $N \times 1$).
   • Fix: Always wrap Step 3 in if (top <= bottom) and Step 4 in if (left <= right).

2. Incorrect Pointer Mutators:

   • Symptom: Infinite loops or skipped rows/columns.
   • Fix: Verify that moving Right increments top++, moving Down decrements right--, moving Left decrements bottom--, and moving Up increments left++.

3. Off-by-One Loop Bounds:

   • Symptom: Skipping corner elements or running out-of-bounds.
   • Fix: Ensure loop boundaries include endpoints (e.g., i <= right or range(left, right + 1)).

4. Matrix Dimensions Confusion:

   • Symptom: IndexOutOfBoundsException when accessing non-square matrices.
   • Fix: Remember $N = \text{matrix.length}$ (rows) and $M = \text{matrix}[0].\text{length}$ (columns). Row index operates within $[0, N-1]$ and column index operates within $[0, M-1]$.

Summary and Key Takeaways

• Core Strategy: Maintain four boundary pointers (top, bottom, left, right) that dynamically shrink the active grid perimeter inward.
• Traversal Sequence: Always follow the fixed 4-step order: Right $\rightarrow$ Down $\rightarrow$ Left $\rightarrow$ Up.
• Pointer Updates:
  • After traversing Right, execute top++.
  • After traversing Down, execute right--.
  • After traversing Left, execute bottom--.
  • After traversing Up, execute left++.
• Edge-Case Safety: Mandatory checks if (top <= bottom) before traversing Left and if (left <= right) before traversing Up prevent duplicate prints on $1 \times M$ and $N \times 1$ matrices.
• Time Complexity: Optimal $\mathcal{O}(N \times M)$ since every matrix element is processed exactly once.
• Space Complexity: $\mathcal{O}(1)$ auxiliary memory required beyond the result storage space.