Spiral Matrix Traversal in DSA C++ - Time & Space Complexity

Time Complexity: Spiral Matrix Traversal

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to traverse a matrix in a spiral way grows as the matrix size increases.

How does the number of steps change when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void spiralTraversal(int matrix[][N], int rows, int cols) {
    int top = 0, bottom = rows - 1;
    int left = 0, right = cols - 1;
    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++;
        }
    }
}
    

This code prints all elements of a matrix in a spiral order, moving layer by layer from outside to inside.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each element of the matrix exactly once.
• How many times: Each element is visited once in the loops inside the while loop.

How Execution Grows With Input

As the matrix size grows, the number of elements to visit grows too.

Input Size (n x n)	Approx. Operations (visits)
10 x 10	100
100 x 100	10,000
1000 x 1000	1,000,000

Pattern observation: The operations grow roughly with the total number of elements, which is the square of the matrix dimension.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows directly with the total number of elements in the matrix, visiting each once.

Common Mistake

[X] Wrong: "The spiral traversal takes more time than just scanning row by row because it has multiple loops inside."

[OK] Correct: Even though there are multiple loops, each element is visited only once, so the total work is still proportional to the number of elements.

Interview Connect

Understanding how spiral traversal scales helps you explain your approach clearly and shows you can analyze how your code behaves with bigger inputs.

Self-Check

"What if the matrix is not rectangular but jagged (rows have different lengths)? How would the time complexity change?"

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