Spiral Matrix Traversal in DSA C

Mental Model

We walk around the edges of the matrix in a circle, moving inward layer by layer until all elements are visited.

Analogy: Imagine peeling an onion layer by layer, starting from the outer skin and moving towards the center, collecting all the layers as you go.

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

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

Visited: 1 -> 2 -> 3
Remaining matrix:
[4,5,6]
[7,8,9]

Why: Start from the top edge to collect the first layer

Step 2: Traverse right column from top to bottom (excluding already visited top row)

Visited: 1 -> 2 -> 3 -> 6 -> 9
Remaining matrix:
[4,5]
[7,8]

Why: Move down the right edge to continue the spiral

Step 3: Traverse bottom row from right to left (excluding already visited right column)

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7
Remaining matrix:
[4,5]

Why: Move left along the bottom edge to complete the outer layer

Step 4: Traverse left column from bottom to top (excluding already visited bottom and top rows)

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4
Remaining matrix:
[5]

Why: Move up the left edge to finish the outer layer

Step 5: Traverse the remaining middle element

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

Why: Center element remains, add it to complete spiral

Result:

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

Annotated Code

DSA C

#include <stdio.h>

void spiralTraversal(int rows, int cols, int matrix[rows][cols]) {
    int top = 0, bottom = rows - 1;
    int left = 0, right = cols - 1;

    while (top <= bottom && left <= right) {
        // Traverse from left to right on top row
        for (int i = left; i <= right; i++) {
            printf("%d", matrix[top][i]);
            if (!(top == bottom && i == right)) printf(" -> ");
        }
        top++;

        // Traverse from top to bottom on right column
        for (int i = top; i <= bottom; i++) {
            printf("%d", matrix[i][right]);
            if (!(i == bottom && left == right)) printf(" -> ");
        }
        right--;

        if (top <= bottom) {
            // Traverse from right to left on bottom row
            for (int i = right; i >= left; i--) {
                printf("%d", matrix[bottom][i]);
                if (!(bottom == top && i == left)) printf(" -> ");
            }
            bottom--;
        }

        if (left <= right) {
            // Traverse from bottom to top on left column
            for (int i = bottom; i >= top; i--) {
                printf("%d", matrix[i][left]);
                if (!(i == top && left == right)) printf(" -> ");
            }
            left++;
        }
    }
    printf("\n");
}

int main() {
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    spiralTraversal(3, 3, matrix);
    return 0;
}

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

continue spiral while boundaries are valid

for (int i = left; i <= right; i++) {

traverse top row left to right

top++;

move top boundary down after top row traversal

for (int i = top; i <= bottom; i++) {

traverse right column top to bottom

right--;

move right boundary left after right column traversal

if (top <= bottom) { for (int i = right; i >= left; i--) {

traverse bottom row right to left if still valid

bottom--;

move bottom boundary up after bottom row traversal

if (left <= right) { for (int i = bottom; i >= top; i--) {

traverse left column bottom to top if still valid

left++;

move left boundary right after left column traversal

Output

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

Complexity Analysis

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

Space: O(1) because traversal uses only a fixed number of variables for boundaries

vs Alternative: Compared to naive approaches that might revisit elements or use extra space, this method is efficient and uses constant extra space

Edge Cases

Empty matrix (0 rows or 0 columns)

No output is printed because the while loop condition fails immediately

DSA C

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

Single row matrix

Only the top row traversal runs, printing all elements left to right

DSA C

for (int i = left; i <= right; i++) {

Single column matrix

Only the right column traversal runs, printing all elements top to bottom

DSA C

for (int i = top; i <= bottom; i++) {

When to Use This Pattern

When you need to print or process matrix elements in a circular, inward pattern, use spiral traversal to systematically reduce boundaries and cover all elements.

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++) to move inward

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

Summary

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

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

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 from outer to inner layers

Solution

1. Step 1: Understand traversal pattern

   Spiral traversal means moving around the edges of the matrix and gradually moving inward in a circular way.

2. Step 2: Compare options

   Only Traverse the matrix in a circular pattern from outer to inner layers 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 from outer to inner layers -> Option D

4. Quick Check:

   Spiral traversal = circular outer to inner [OK]

Hint: Think of peeling an onion layer by layer [OK]

Common Mistakes:

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

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

easy

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

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

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

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

Solution

1. Step 1: Identify correct boundary initialization

   For spiral traversal, top starts at 0, bottom at last row (m-1), left at 0, right at last column (n-1).

2. Step 2: Match with options

   int top = 0, bottom = m-1, left = 0, right = n-1; matches this initialization exactly; others swap or mix row and column indices incorrectly.

3. Final Answer:

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

4. Quick Check:

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

Hint: Top and left start at 0; bottom and right at max index [OK]

Common Mistakes:

• Swapping m and n in bottom or right
• Starting top or left at max index
• Confusing row and column boundaries

3. What is the output of the following C code snippet for spiral traversal of a 3x3 matrix?

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++) printf("%d ", matrix[top][i]);
  top++;
  for(int i=top; i<=bottom; i++) printf("%d ", matrix[i][right]);
  right--;
  if(top <= bottom) {
    for(int i=right; i>=left; i--) printf("%d ", matrix[bottom][i]);
    bottom--;
  }
  if(left <= right) {
    for(int i=bottom; i>=top; i--) printf("%d ", matrix[i][left]);
    left++;
  }
}

medium

A. 1 4 7 8 9 6 3 2 5

B. 1 2 3 6 9 8 7 4 5

C. 1 2 3 4 5 6 7 8 9

D. 1 3 5 7 9 2 4 6 8

Solution

1. Step 1: Trace first outer layer traversal

   Top row left to right: 1 2 3; then right column top to bottom: 6 9; bottom row right to left: 8 7; left column bottom to top: 4.

2. Step 2: Move inward and print center

   Now top=1, bottom=1, left=1, right=1; print center element matrix[1][1] = 5.

3. Final Answer:

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

4. Quick Check:

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

Hint: Follow boundaries and print edges clockwise [OK]

Common Mistakes:

• Skipping center element
• Mixing row and column indices
• Not updating boundaries correctly

4. Find the error in this spiral traversal code snippet for a 3x3 matrix:

int top=0, bottom=2, left=0, right=2;
while(top < bottom && left < right) {
  for(int i=left; i<=right; i++) printf("%d ", matrix[top][i]);
  top++;
  for(int i=top; i<=bottom; i++) printf("%d ", matrix[i][right]);
  right--;
  for(int i=right; i>=left; i--) printf("%d ", matrix[bottom][i]);
  bottom--;
  for(int i=bottom; i>=top; i--) printf("%d ", matrix[i][left]);
  left++;
}

medium

A. The variables top and bottom are swapped

B. The for loops should use < instead of <=

C. The while loop condition should use <= instead of <

D. The matrix indices are accessed incorrectly

Solution

1. Step 1: Analyze loop condition

   The condition top < bottom && left < right stops before the center element is processed in odd-sized matrices.

2. Step 2: Correct condition for full traversal

   Using <= allows the loop to run when top equals bottom or left equals right, ensuring center elements are included.

3. Final Answer:

   The while loop condition should use <= instead of < -> Option C

4. Quick Check:

   Use <= in while condition for complete spiral [OK]

Hint: Use <= in while to include center elements [OK]

Common Mistakes:

• Stopping traversal too early
• Changing for loop bounds incorrectly
• Swapping top and bottom variables

5. Given a 4x4 matrix:

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

Write the spiral traversal output if you start from the bottom-left corner and move clockwise inward.

hard

A. 13 9 5 1 2 3 4 8 12 16 15 14 10 6 7 11

B. 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

C. 13 14 15 16 12 8 4 3 2 1 5 9 10 11 7 6

D. 16 15 14 13 9 5 1 2 3 4 8 12 11 10 6 7

Solution

1. Step 1: Understand starting point and direction

   Start at bottom-left (matrix[3][0] = 13) and move clockwise: up, right, down, left, inward.

2. Step 2: Trace spiral clockwise from bottom-left

   Up column: 13 9 5 1; right row: 2 3 4; down column: 8 12 16; left row: 15 14 10 6; then inner spiral: 7 11.

3. Final Answer:

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

4. Quick Check:

   Start bottom-left clockwise spiral = 13 9 5 1 2 3 4 8 12 16 15 14 10 6 7 11 [OK]

Hint: Change start and direction, then trace edges inward [OK]

Common Mistakes:

• Starting from top-left instead of bottom-left
• Moving counter-clockwise instead of clockwise
• Mixing row and column indices