Spiral Matrix in C++

Spiral Matrix in C++ (LeetCode 54: Spiral Matrix) is one of the most foundational and frequently asked 2D array manipulation and boundary-tracking problems featured in technical interviews at top technology firms such as Amazon, Microsoft, Apple, Google, Meta, and Bloomberg. Given a 2D matrix of dimensions M × N, the objective is to traverse and return all elements in clockwise spiral order starting from the top-left cell (0, 0). While conceptually simple, writing a bug-free implementation without off-by-one errors or duplicate boundary scans requires mastering the 4-Boundary Layer Peeling Invariant. In this comprehensive masterclass, we will deconstruct the problem from first principles: covering the O(M × N) Direction Vector Visited Grid Simulation, In-Place Sentinel State Marking, and the Optimal 4-Boundary Layer Peeling Algorithm running in strict O(M × N) time and O(1) auxiliary space. We will also examine row-major cache stride penalties, generalize to Spiral Matrix II & III, benchmark on a 4,000,000-cell matrix, and provide interactive “Try it yourself” challenges after every section.

🔹 Problem Geometry & The 4-Boundary Invariant

Consider a 3 × 4 matrix of integers:

Matrix Coordinates (M = 3 rows, N = 4 cols):
Col:       0     1     2     3
Row 0:  [  1,    2,    3,    4  ]
Row 1:  [  5,    6,    7,    8  ]
Row 2:  [  9,   10,   11,   12  ]

Clockwise Spiral Traversal Path:
1 → 2 → 3 → 4 → 8 → 12 → 11 → 10 → 9 → 5 → 6 → 7
Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Visualizing the spiral traversal reveals that the path continuously shrinks the active unvisited rectangular bounding box:

Initial Bounding Box:
top = 0, bottom = M - 1 (2), left = 0, right = N - 1 (3)

Phase 1: Traverse Left → Right along 'top'    (Elements: 1, 2, 3, 4)  → ++top
Phase 2: Traverse Top → Bottom along 'right'  (Elements: 8, 12)       → --right
Phase 3: Traverse Right → Left along 'bottom' (Elements: 11, 10, 9)   → --bottom
Phase 4: Traverse Bottom → Top along 'left'   (Element:  5)           → ++left

Inner Sub-Matrix Bounding Box:
top = 1, bottom = 1, left = 1, right = 2
Traverse Left → Right along 'top' (Elements: 6, 7) → Finished!

From this geometric mental model, we derive the critical boundary invariants:

• Total Number of Rings: An M × N matrix consists of exactly ⌈min(M, N) / 2⌉ concentric rectangular layers (rings).
• The Degenerate Sub-Matrix Guard (Crucial Edge Cases):
  • When M and N are unequal (non-square), the innermost layer may reduce to a single horizontal row or a single vertical column.
  • After traversing Left → Right (Phase 1) and Top → Bottom (Phase 2), we must check if (top ≤ bottom) before traversing Right → Left to prevent scanning a single row in reverse.
  • Similarly, we must check if (left ≤ right) before traversing Bottom → Top to prevent scanning a single column twice.

Try it yourself

• What happens if you omit the top ≤ bottom guard on a single-row matrix [[1, 2, 3, 4]]? (Answer: The row is traversed left-to-right, and then incorrectly traversed right-to-left!).
• What is the spiral order of a 1 × 1 matrix [[42]]?

🔹 Approach 1: Direction Vector Visited Grid Simulation (O(M × N) Space)

Intuition & Reasoning: Model the traversal as a robotic agent moving on a 2D grid. We maintain direction delta arrays dr = {0, 1, 0, -1} and dc = {1, 0, -1, 0} representing four directions (0: Right, 1: Down, 2: Left, 3: Up). We use a 2D boolean array visited[M][N]. At each step, if the next cell is out of bounds or already visited, we rotate the direction 90° clockwise: dir = (dir + 1) % 4.

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// Approach 1: Direction Vector Visited Grid Simulation
// Time Complexity: O(M * N), Space Complexity: O(M * N) auxiliary
vector<int> spiral_order_simulation(const vector<vector<int>>& mat) {
    if (mat.empty() || mat[0].empty()) return {};

    const int m = static_cast<int>(mat.size());
    const int n = static_cast<int>(mat[0].size());
    const int total = m * n;

    vector<int> result;
    result.reserve(total);

    vector<vector<bool>> visited(m, vector<bool>(n, false));

    // Direction deltas: Right (0), Down (1), Left (2), Up (3)
    const int dr[4] = {0, 1, 0, -1};
    const int dc[4] = {1, 0, -1, 0};
    int dir = 0;

    int r = 0, c = 0;
    for (int i = 0; i < total; ++i) {
        result.push_back(mat[r][c]);
        visited[r][c] = true;

        // Calculate candidate next cell
        int next_r = r + dr[dir];
        int next_c = c + dc[dir];

        // Check if candidate next cell is valid and unvisited
        if (next_r >= 0 && next_r < m && next_c >= 0 && next_c < n && !visited[next_r][next_c]) {
            r = next_r;
            c = next_c;
        } else {
            // Rotate 90 degrees clockwise
            dir = (dir + 1) % 4;
            r += dr[dir];
            c += dc[dir];
        }
    }

    return result;
}

int main() {
    vector<vector<int>> mat1 = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    vector<int> expected1 = {1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7};

    cout << "--- Approach 1: Visited Simulation ---\n";
    vector<int> res1 = spiral_order_simulation(mat1);
    for (int x : res1) cout << x << " ";
    cout << "\n";

    assert(res1 == expected1);
    cout << "All assertions passed successfully!\n";
    return 0;
}

Output

--- Approach 1: Visited Simulation ---
1 2 3 4 8 12 11 10 9 5 6 7 
All assertions passed successfully!

Complexity Analysis

• Time Complexity (TC): O(M × N): Every one of the M × N cells is visited exactly once.
• Space Complexity (SC): O(M × N): Allocates an M × N boolean matrix for tracking visited states.
• Bottleneck: Allocating M × N booleans creates memory allocator pressure and causes cache misses due to vector-of-vectors heap fragmentation.

Try it yourself

• How would you flatten the visited matrix into a 1D vector to improve cache locality?
• Can this approach be executed if the grid is infinite and boundaries are obstacles?

🔹 Approach 2: In-Place Sentinel Value Marking (O(1) Auxiliary Space)

Intuition & Reasoning: If we are allowed to mutate the input matrix, we can eliminate the visited array by overwriting visited cells with a special sentinel value such as 101 (if matrix values are bounded in [-100, 100]) or INT_MIN.

#include <iostream>
#include <vector>
#include <climits>
#include <cassert>

using namespace std;

// Approach 2: In-Place Sentinel Marking (Mutates Input)
// Time Complexity: O(M * N), Space Complexity: O(1) auxiliary
vector<int> spiral_order_sentinel(vector<vector<int>>& mat) {
    if (mat.empty() || mat[0].empty()) return {};

    const int m = static_cast<int>(mat.size());
    const int n = static_cast<int>(mat[0].size());
    const int total = m * n;
    const int SENTINEL = INT_MIN;

    vector<int> result;
    result.reserve(total);

    const int dr[4] = {0, 1, 0, -1};
    const int dc[4] = {1, 0, -1, 0};
    int dir = 0;

    int r = 0, c = 0;
    for (int i = 0; i < total; ++i) {
        result.push_back(mat[r][c]);
        mat[r][c] = SENTINEL; // Mark cell in-place

        int next_r = r + dr[dir];
        int next_c = c + dc[dir];

        if (next_r >= 0 && next_r < m && next_c >= 0 && next_c < n && mat[next_r][next_c] != SENTINEL) {
            r = next_r;
            c = next_c;
        } else {
            dir = (dir + 1) % 4;
            r += dr[dir];
            c += dc[dir];
        }
    }

    return result;
}

int main() {
    vector<vector<int>> mat1 = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    cout << "--- Approach 2: In-Place Sentinel Marking ---\n";
    vector<int> res = spiral_order_sentinel(mat1);
    for (int x : res) cout << x << " ";
    cout << "\n";
    return 0;
}

Complexity Analysis

• Time Complexity (TC): O(M × N): Visits each cell once.
• Space Complexity (SC): O(1) auxiliary, Operates directly on the input matrix.
• Major Drawback: Destructive modification makes it unsuitable for read-only (const) matrices or concurrent shared access.

🔹 Approach 3: Optimal 4-Boundary Layer Peeling Algorithm (O(M × N) Time, O(1) Space)

Intuition & Invariants: We maintain four boundary pointers (top, bottom, left, right). In each loop iteration, we peel off one complete outer layer of the matrix in four sequential steps:

1. Left → Right: Iterate col from left to right along row 'top'. Then ++top.
2. Top → Bottom: Iterate row from top to bottom along col 'right'. Then --right.
3. Right → Left: (Guard: top <= bottom) Iterate col from right to left along row 'bottom'. Then --bottom.
4. Bottom → Top: (Guard: left <= right) Iterate row from bottom to top along col 'left'. Then ++left.

Loop Condition: while (top <= bottom && left <= right)

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// Approach 3: Optimal 4-Boundary Layer Peeling
// Time Complexity: O(M * N), Space Complexity: O(1) auxiliary
vector<int> spiral_order_optimal(const vector<vector<int>>& mat) {
    if (mat.empty() || mat[0].empty()) return {};

    const int m = static_cast<int>(mat.size());
    const int n = static_cast<int>(mat[0].size());

    vector<int> result;
    result.reserve(m * n);

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

    while (top <= bottom && left <= right) {
        // Step 1: Traverse Left → Right along row 'top'
        for (int c = left; c <= right; ++c) {
            result.push_back(mat[top][c]);
        }
        ++top; // Shrink top boundary

        // Step 2: Traverse Top → Bottom along col 'right'
        for (int r = top; r <= bottom; ++r) {
            result.push_back(mat[r][right]);
        }
        --right; // Shrink right boundary

        // Step 3: Traverse Right → Left along row 'bottom'
        if (top <= bottom) {
            for (int c = right; c >= left; --c) {
                result.push_back(mat[bottom][c]);
            }
            --bottom; // Shrink bottom boundary
        }

        // Step 4: Traverse Bottom → Top along col 'left'
        if (left <= right) {
            for (int r = bottom; r >= top; --r) {
                result.push_back(mat[r][left]);
            }
            ++left; // Shrink left boundary
        }
    }

    return result;
}

int main() {
    vector<vector<int>> mat1 = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12}
    };
    vector<vector<int>> mat2 = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    vector<vector<int>> mat3 = {{1, 2, 3, 4}}; // Single row
    vector<vector<int>> mat4 = {{1}, {2}, {3}}; // Single column

    cout << "--- Approach 3: Optimal 4-Boundary Layer Peeling ---\n";
    vector<int> r1 = spiral_order_optimal(mat1);
    vector<int> r2 = spiral_order_optimal(mat2);
    vector<int> r3 = spiral_order_optimal(mat3);
    vector<int> r4 = spiral_order_optimal(mat4);

    assert((r1 == vector<int>{1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7}));
    assert((r2 == vector<int>{1, 2, 3, 6, 9, 8, 7, 4, 5}));
    assert((r3 == vector<int>{1, 2, 3, 4}));
    assert((r4 == vector<int>{1, 2, 3}));
    cout << "All edge-case assertions passed successfully!\n";
    return 0;
}

Output

--- Approach 3: Optimal 4-Boundary Layer Peeling ---
All edge-case assertions passed successfully!

Step by Step Layer Peeling Trace

Tracing spiral_order_optimal on mat1 (3 × 4):

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

Iteration 1 (Outer Ring):
- Sweep 1 (Left → Right on row 0): Push mat[0][0..3] → [1, 2, 3, 4]. Update top = 1.
- Sweep 2 (Top → Bottom on col 3): Push mat[1..2][3] → [8, 12]. Update right = 2.
- Sweep 3 (Right → Left on row 2, top(1) <= bottom(2)): Push mat[2][2..0] → [11, 10, 9]. Update bottom = 1.
- Sweep 4 (Bottom → Top on col 0, left(0) <= right(2)): Push mat[1][0] → [5]. Update left = 1.

Iteration 2 (Inner Ring):
- State: top = 1, bottom = 1, left = 1, right = 2
- Sweep 1 (Left → Right on row 1): Push mat[1][1..2] → [6, 7]. Update top = 2.
- Sweep 2 (Top → Bottom on col 2): Loop skipped (top=2 > bottom=1). Update right = 1.
- Sweep 3: Guard top(2) <= bottom(1) is FALSE.
- Sweep 4: Guard left(1) <= right(1) is TRUE, but bottom(1) < top(2), loop skipped.

Termination: top(2) > bottom(1).
Result: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]!

Complexity Analysis

• Time Complexity (TC): O(M × N): Every element in the M × N matrix is pushed to result exactly once in continuous sweeps.
• Space Complexity (SC): O(1) auxiliary, Uses only four integer pointers (top, bottom, left, right) with zero auxiliary memory allocations.

Try it yourself

• Test the algorithm on a 4 × 1 single-column matrix. Does it correctly push elements from top to bottom without duplicates?
• How would you reverse the traversal to run in counter-clockwise spiral order?

🔹 Advanced Systems Topic: Row-Major Stride Cache Penalties

In C++, 2D matrices are laid out in Row-Major Order. Horizontal traversals (Left → Right and Right → Left) access contiguous cache lines, yielding near 100% L1 cache hit rates. However, vertical traversals (Top → Bottom and Bottom → Top) jump across memory with stride N × sizeof(int). For large matrices where N exceeds the L1 cache size (32 KB), vertical sweeps cause cache line misses on every single access.

🔹 Lab: High Performance Benchmark Across 4,000,000 Cells (2,000 × 2,000 Matrix)

The following benchmark executable measures memory traversal efficiency on a 2,000 × 2,000 matrix (4,000,000 integers) using std::chrono::high_resolution_clock:

#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

vector<int> bench_sim(const vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size(), total = m * n;
    vector<int> res; res.reserve(total);
    vector<vector<bool>> vis(m, vector<bool>(n, false));
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}, dir = 0, r = 0, c = 0;
    for (int i = 0; i < total; ++i) {
        res.push_back(mat[r][c]);
        vis[r][c] = true;
        int nr = r + dr[dir], nc = c + dc[dir];
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && !vis[nr][nc]) { r = nr; c = nc; }
        else { dir = (dir + 1) % 4; r += dr[dir]; c += dc[dir]; }
    }
    return res;
}

vector<int> bench_opt(const vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    vector<int> res; res.reserve(m * n);
    int top = 0, bottom = m - 1, left = 0, right = n - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; ++c) res.push_back(mat[top][c]);
        ++top;
        for (int r = top; r <= bottom; ++r) res.push_back(mat[r][right]);
        --right;
        if (top <= bottom) {
            for (int c = right; c >= left; --c) res.push_back(mat[bottom][c]);
            --bottom;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; --r) res.push_back(mat[r][left]);
            ++left;
        }
    }
    return res;
}

int main() {
    const int M = 2000;
    const int N = 2000;
    cout << "Allocating 2000x2000 (4,000,000 cells) matrix...\n";

    vector<vector<int>> mat(M, vector<int>(N, 1));

    auto t0 = high_resolution_clock::now();
    auto r1 = bench_sim(mat);
    auto t1 = high_resolution_clock::now();
    cout << "1. Visited Simulation:     " << duration_cast<milliseconds>(t1 - t0).count() << " ms (Size: " << r1.size() << ")\n";

    auto t2 = high_resolution_clock::now();
    auto r2 = bench_opt(mat);
    auto t3 = high_resolution_clock::now();
    cout << "2. Optimal Layer Peeling:  " << duration_cast<milliseconds>(t3 - t2).count() << " ms (Size: " << r2.size() << ")\n";

    return 0;
}

Benchmark Results

Allocating 2000x2000 (4,000,000 cells) matrix...
1. Visited Simulation:     98 ms (Size: 4000000)
2. Optimal Layer Peeling:  24 ms (Size: 4000000)  ← 4x FASTER with 0 B auxiliary memory!

🔹 Comparison Matrix of All Approaches

┌───────────────────────────────────────┬──────────────────┬──────────────────┬─────────────────────────────┬───────────────────────────┐
│ Approach                              │ Time Complexity  │ Space Complexity │ Mutates Input Matrix?       │ Edge-Case Safety          │
├───────────────────────────────────────┼──────────────────┼──────────────────┼─────────────────────────────┼───────────────────────────┤
│ 1. Direction Vector Simulation        │ O(M * N)         │ O(M * N)         │ No                          │ Handles any shape         │
│ 2. In-Place Sentinel State Marking    │ O(M * N)         │ O(1) auxiliary   │ Yes (Destructive)           │ Values must fit sentinel  │
│ 3. Optimal 4-Boundary Layer Peeling   │ O(M * N)         │ O(1) auxiliary   │ No (Read-Only safe)         │ Safe via boundary guards  │
└───────────────────────────────────────┴──────────────────┴──────────────────┴─────────────────────────────┴───────────────────────────┘

🔹 Frequently Asked Questions (FAQs)

Q1: Why are the boundary check guards (if (top ≤ bottom) and if (left ≤ right)) strictly necessary?
In non-square matrices (e.g. 1 × 4 or 3 × 1), after incrementing top or decrementing right, the matrix bounds may cross (top > bottom or left > right). Without these conditional guards, the reverse sweeps (Right → Left or Bottom → Top) would execute on already processed rows or columns, generating duplicate elements.

Q2: How do we solve Spiral Matrix II (LeetCode 59: Generating an N × N spiral matrix)?
Use the exact same 4-boundary pointer mechanism, but instead of reading from a matrix and pushing to a vector, maintain a counter val = 1 and write mat[r][c] = val++ during the four directional sweeps.

Q3: How does reserving vector capacity optimize runtime in C++?
Calling result.reserve(m * n) performs a single upfront memory allocation for all M × N elements, completely preventing costly dynamic reallocations and memory copies during push_back.

Q4: Can this algorithm handle empty matrices?
Yes. The guard if (mat.empty() || mat[0].empty()) return {}; immediately returns an empty vector, preventing invalid memory accesses.

Q5: What is the maximum number of layer peelings in an M × N matrix?
The total number of concentric layers is ⌈min(M, N) / 2⌉. For example, a 10 × 10 matrix has 5 layers; a 3 × 8 matrix has 2 layers.

Q6: Why is the 4-boundary method 4x faster than simulation in benchmarks?
The 4-boundary method executes tightly rolled for loops that enable compiler auto-vectorization and predictable sequential branch jumps. In contrast, direction-vector simulation evaluates boundary checks and rotational modulo arithmetic (% 4) on every single cell access.

Q7: How do we handle Spiral Matrix III (walking outside matrix boundaries)?
In Spiral Matrix III, step lengths increase every two direction changes (1, 1, 2, 2, 3, 3, …). We maintain coordinates and only push elements to the result vector when the coordinates lie inside the valid matrix bounding box.

Q8: What is the impact of compiler optimization on this loop?
At -O3, GCC and Clang unroll the inner boundary loops and vectorize the horizontal sweeps using SIMD instructions, maximizing memory bus bandwidth.

🔹 Wrapping Up

Traversing a Spiral Matrix in C++ is an essential exercise in boundary invariant management. By utilizing the 4-Boundary Layer Peeling Algorithm, we eliminate duplicate scans and achieve an optimal O(M × N) time and O(1) auxiliary space complexity. Broaden your 2D matrix engineering skills with our guides on Row with Maximum 1’s, Matrix Median, and Rotate Image (90 Degrees Clockwise).