Spiral Matrix Traversal in DSA C++

Mental Model

We move around the edges of the matrix in a circle, peeling off one layer at a time until all elements are visited.

Analogy: Imagine peeling an onion layer by layer, starting from the outer skin and moving inward in a spiral path.

1 -> 2 -> 3 -> 4
↓           ↑
12         5
↓           ↑
11 10  9 -> 6
↓
7 -> 8

Dry Run Walkthrough

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

Goal: Print elements in spiral order: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5

Step 1: Traverse top row from left to right

[1, 2, 3] -> remaining matrix edges to traverse

Why: Start from the top row to begin the spiral

Step 2: Traverse right column from top+1 to bottom

1 -> 2 -> 3 -> [6, 9]

Why: Move down the right edge after top row

Step 3: Traverse bottom row from right-1 to left in reverse

1 -> 2 -> 3 -> 6 -> 9 -> [8, 7]

Why: Move left along the bottom edge

Step 4: Traverse left column from bottom-1 to top+1 in reverse

1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> [4]

Why: Move up the left edge

Step 5: Traverse the inner remaining element

1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> [5]

Why: Complete the spiral by visiting the center

Result:

1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> spiralOrder(const vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) return result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (top <= bottom && left <= right) {
        // Traverse from left to right on top row
        for (int col = left; col <= right; ++col) {
            result.push_back(matrix[top][col]);
        }
        top++;

        // Traverse from top to bottom on right column
        for (int row = top; row <= bottom; ++row) {
            result.push_back(matrix[row][right]);
        }
        right--;

        if (top <= bottom) {
            // Traverse from right to left on bottom row
            for (int col = right; col >= left; --col) {
                result.push_back(matrix[bottom][col]);
            }
            bottom--;
        }

        if (left <= right) {
            // Traverse from bottom to top on left column
            for (int row = bottom; row >= top; --row) {
                result.push_back(matrix[row][left]);
            }
            left++;
        }
    }
    return result;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    vector<int> spiral = spiralOrder(matrix);
    for (int i = 0; i < spiral.size(); ++i) {
        cout << spiral[i];
        if (i < spiral.size() - 1) cout << " -> ";
    }
    cout << "\n";
    return 0;
}

while (top <= bottom && left <= right) {

repeat spiral layers while boundaries are valid

for (int col = left; col <= right; ++col) { result.push_back(matrix[top][col]); }

traverse top row left to right

top++;

move top boundary down after top row traversal

for (int row = top; row <= bottom; ++row) { result.push_back(matrix[row][right]); }

traverse right column top to bottom

right--;

move right boundary left after right column traversal

if (top <= bottom) { for (int col = right; col >= left; --col) { result.push_back(matrix[bottom][col]); } bottom--; }

traverse bottom row right to left if still valid

if (left <= right) { for (int row = bottom; row >= top; --row) { result.push_back(matrix[row][left]); } left++; }

traverse left column bottom to top if still valid

Output

1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4 -> 5

Complexity Analysis

Time: O(m*n) because every element in the m by n matrix is visited exactly once

Space: O(m*n) for the output list storing all elements

vs Alternative: Compared to naive repeated scanning, this approach visits each element once in a controlled spiral order, avoiding revisits and extra checks

Edge Cases

empty matrix

returns empty list immediately

DSA C++

if (matrix.empty()) return result;

single row matrix

traverses left to right only

DSA C++

while (top <= bottom && left <= right)

single column matrix

traverses top to bottom only

DSA C++

while (top <= bottom && left <= right)

When to Use This Pattern

When you need to print or process matrix elements in a circular inward pattern, use spiral traversal to peel layers one by one.

Common Mistakes

Mistake: Not updating boundaries correctly causing infinite loops or repeated elements
Fix: After each edge traversal, update the corresponding boundary (top++, right--, bottom--, left++)

Mistake: Not checking boundary conditions before traversing bottom row or left column
Fix: Add checks like if (top <= bottom) and if (left <= right) before those traversals

Summary

Prints matrix elements in a spiral order starting from the top-left corner.

Use when you want to visit all elements layer by layer in a circular pattern.

The key is to keep track of four boundaries and move them inward after each edge traversal.

Practice

1. What is the main idea behind Spiral Matrix Traversal?

easy

A. Traverse only the diagonal elements of the matrix

B. Traverse the matrix row by row from top to bottom

C. Traverse the matrix column by column from left to right

D. Traverse the matrix in a circular pattern starting from the outer layer moving inward

Solution

1. Step 1: Understand traversal pattern

   Spiral traversal means moving around the edges of the matrix and then moving inward layer by layer.

2. Step 2: Compare options

   Only Traverse the matrix in a circular pattern starting from the outer layer moving inward describes moving in a circular pattern from outer to inner layers, which matches spiral traversal.

3. Final Answer:

   Traverse the matrix in a circular pattern starting from the outer layer moving inward -> Option D

4. Quick Check:

   Spiral traversal = circular outer to inner [OK]

Hint: Spiral means circle around edges then go inside [OK]

Common Mistakes:

• Confusing spiral with row-wise or column-wise traversal
• Thinking spiral means diagonal traversal
• Ignoring the inward movement after outer layer

2. Which of the following C++ code snippets correctly initializes the boundaries for spiral traversal of an m x n matrix?

easy

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

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

C. int top = 1, bottom = m, left = 1, right = n;

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

Solution

1. Step 1: Understand boundary variables

   Top and bottom represent row boundaries, left and right represent column boundaries. For an m x n matrix, top starts at 0, bottom at m-1, left at 0, right at n-1.

2. Step 2: Check each option

   int top = 0, bottom = m - 1, left = 0, right = n - 1; correctly sets top=0, bottom=m-1, left=0, right=n-1. Others have reversed or incorrect assignments.

3. Final Answer:

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

4. Quick Check:

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

Hint: Top/left start at 0; bottom/right at size minus one [OK]

Common Mistakes:

• Swapping m and n in boundary initialization
• Starting boundaries at 1 instead of 0
• Confusing row and column boundaries

3. What is the output of the following C++ code snippet for spiral traversal?

int matrix[3][3] = {
  {1, 2, 3},
  {4, 5, 6},
  {7, 8, 9}
};

int top = 0, bottom = 2, left = 0, right = 2;

while (top <= bottom && left <= right) {
  for (int i = left; i <= right; i++)
    std::cout << matrix[top][i] << " ";
  top++;
  for (int i = top; i <= bottom; i++)
    std::cout << matrix[i][right] << " ";
  right--;
  if (top <= bottom) {
    for (int i = right; i >= left; i--)
      std::cout << matrix[bottom][i] << " ";
    bottom--;
  }
  if (left <= right) {
    for (int i = bottom; i >= top; i--)
      std::cout << matrix[i][left] << " ";
    left++;
  }
}

medium

A. 1 2 3 4 5 6 7 8 9

B. 1 4 7 8 9 6 3 2 5

C. 1 2 3 6 9 8 7 4 5

D. 9 8 7 6 5 4 3 2 1

Solution

1. Step 1: Trace the spiral traversal

   First top row: 1 2 3
   Right column down: 6 9
   Bottom row left: 8 7
   Left column up: 4
   Next inner layer top row: 5

2. Step 2: Combine all elements in order

   Combined output: 1 2 3 6 9 8 7 4 5

3. Final Answer:

   1 2 3 6 9 8 7 4 5 -> Option C

4. Quick Check:

   Spiral order = 1 2 3 6 9 8 7 4 5 [OK]

Hint: Follow edges clockwise, then move inward [OK]

Common Mistakes:

• Printing rows or columns in wrong order
• Skipping inner elements like 5
• Repeating elements or missing boundaries update

4. Identify the bug in this spiral traversal code snippet:

int top = 0, bottom = m - 1, left = 0, right = n - 1;
while (top < bottom && left < right) {
  for (int i = left; i <= right; i++) cout << matrix[top][i] << " ";
  top++;
  for (int i = top; i <= bottom; i++) cout << matrix[i][right] << " ";
  right--;
  for (int i = right; i >= left; i--) cout << matrix[bottom][i] << " ";
  bottom--;
  for (int i = bottom; i >= top; i--) cout << matrix[i][left] << " ";
  left++;
}

medium

A. The while loop condition should use <= instead of < to include all layers

B. The for loops should use < instead of <= to avoid out-of-bound errors

C. The variables top, bottom, left, right are not initialized correctly

D. The code misses printing the diagonal elements

Solution

1. Step 1: Analyze loop condition

   The while loop uses 'top < bottom && left < right', which skips the last layer when top == bottom or left == right.

2. Step 2: Correct condition for full traversal

   Changing to 'top <= bottom && left <= right' ensures the last single row or column is included in traversal.

3. Final Answer:

   The while loop condition should use <= instead of < to include all layers -> Option A

4. Quick Check:

   Use <= in loop condition to cover all layers [OK]

Hint: Use <= in while condition to cover last layer [OK]

Common Mistakes:

• Using < causes missing last row or column
• Changing for loops to < causes skipping elements
• Not updating boundaries after each traversal

5. Given a non-square matrix:

int matrix[3][4] = {
  {1, 2, 3, 4},
  {5, 6, 7, 8},
  {9, 10, 11, 12}
};

Which is the correct spiral traversal output?

hard

A. 1 2 3 4 8 12 11 10 9 5 6 7

B. 1 2 3 4 8 12 11 10 9 5 6 7 0

C. 1 5 9 10 11 12 8 4 3 2 6 7

D. 1 2 3 4 8 12 11 10 9 5 7 6

Solution

1. Step 1: Trace spiral on 3x4 matrix

   Top row: 1 2 3 4
   Right column down: 8 12
   Bottom row left: 11 10 9
   Left column up: 5
   Inner top row: 6 7

2. Step 2: Combine elements in order

   Combined output: 1 2 3 4 8 12 11 10 9 5 6 7

3. Final Answer:

   1 2 3 4 8 12 11 10 9 5 6 7 -> Option A

4. Quick Check:

   Spiral order for 3x4 matrix = 1 2 3 4 8 12 11 10 9 5 6 7 [OK]

Hint: Follow edges carefully, handle rectangular shape [OK]

Common Mistakes:

• Adding extra elements like 0
• Mixing inner elements order
• Swapping 6 and 7 positions