Spiral Matrix Traversal in DSA Rust

Mental Model

We move around the edges of the matrix in a circle, peeling off layers 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 13 14 5
11 16 15 6
10 9  8  7
↑start at top-left corner

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 edges to traverse

Why: Start by moving across the top row to cover the first layer

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

Visited: 1 -> 2 -> 3 -> 6 -> 9
Remaining matrix edges to traverse

Why: Move down the right side to continue the spiral

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

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7
Remaining matrix edges to traverse

Why: Move left across the bottom row to complete the outer layer

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

Visited: 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 7 -> 4
Remaining matrix edges to traverse

Why: Move up the left side to complete the outer layer

Step 5: Traverse the inner remaining element(s) in spiral order

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

Why: Move inward and visit the center element(s)

Result:

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

Annotated Code

DSA Rust

fn spiral_traversal(matrix: Vec<Vec<i32>>) -> Vec<i32> {
    let mut result = Vec::new();
    if matrix.is_empty() || matrix[0].is_empty() {
        return result;
    }
    let (mut top, mut bottom) = (0, matrix.len() - 1);
    let (mut left, mut right) = (0, matrix[0].len() - 1);

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

        // Traverse from top to bottom on the right column
        for row in top..=bottom {
            result.push(matrix[row][right]);
        }
        if right == 0 { break; } // prevent underflow
        right = right.saturating_sub(1);

        if top <= bottom {
            // Traverse from right to left on the bottom row
            for col in (left..=right).rev() {
                result.push(matrix[bottom][col]);
            }
            if bottom == 0 { break; } // prevent underflow
            bottom = bottom.saturating_sub(1);
        }

        if left <= right {
            // Traverse from bottom to top on the left column
            for row in (top..=bottom).rev() {
                result.push(matrix[row][left]);
            }
            left += 1;
        }
    }
    result
}

fn main() {
    let matrix = vec![
        vec![1, 2, 3],
        vec![4, 5, 6],
        vec![7, 8, 9],
    ];
    let spiral = spiral_traversal(matrix);
    for (i, val) in spiral.iter().enumerate() {
        if i == spiral.len() - 1 {
            print!("{}", val);
        } else {
            print!("{} -> ", val);
        }
    }
    print!("\n");
}

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

continue looping while there are layers to traverse

for col in left..=right { result.push(matrix[top][col]); } top += 1;

traverse top row left to right, then move top boundary down

for row in top..=bottom { result.push(matrix[row][right]); } right = right.saturating_sub(1);

traverse right column top to bottom, then move right boundary left

if top <= bottom { for col in (left..=right).rev() { result.push(matrix[bottom][col]); } bottom = bottom.saturating_sub(1); }

traverse bottom row right to left if still valid, then move bottom boundary up

if left <= right { for row in (top..=bottom).rev() { result.push(matrix[row][left]); } left += 1; }

traverse left column bottom to top if still valid, then move left boundary right

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 repeated visits and extra checks

Edge Cases

empty matrix

returns empty list without error

DSA Rust

if matrix.is_empty() || matrix[0].is_empty() { return result; }

single row matrix

traverses left to right only

DSA Rust

while left <= right && top <= bottom { ... }

single column matrix

traverses top to bottom only

DSA Rust

while left <= right && top <= bottom { ... }

When to Use This Pattern

When you need to visit all elements of a matrix in a circular, inward spiral order, use the spiral traversal pattern 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, bottom, left, right) 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 those traversals

Summary

It prints all elements of a matrix in a spiral order starting from the top-left corner.

Use it when you want to read or print matrix elements layer by layer in a circular pattern.

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

Practice

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

easy

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

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

C. Traverse the matrix in a circular pattern from outer to inner layers

D. Traverse only the diagonal elements of the matrix

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 this circular, layer-by-layer movement. Others describe linear or partial traversals.

3. Final Answer:

   Traverse the matrix in a circular pattern from outer to inner layers -> Option C

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 or column-wise traversal
• Thinking only diagonals are involved
• Ignoring the inward movement after outer layer

2. Which Rust loop structure is best suited to iterate over matrix indices for spiral traversal?

easy

A. loop { ... } with break condition

B. for i in 0..n { ... }

C. while i <= n { ... }

D. match statement for index matching

Solution

1. Step 1: Identify loop types in Rust

   Rust commonly uses for i in 0..n for fixed range iteration, ideal for matrix indices.

2. Step 2: Evaluate options for spiral traversal

   for i in 0..n { ... } uses range-based for loop, perfect for controlled index traversal. while i <= n { ... } is less idiomatic. loop { ... } with break condition is infinite loop needing manual breaks. match statement for index matching is for pattern matching, not iteration.

3. Final Answer:

   for i in 0..n { ... } -> Option B

4. Quick Check:

   Range-based for loop = best for index iteration [OK]

Hint: Use for loops with ranges for matrix indices [OK]

Common Mistakes:

• Using infinite loops without proper break
• Using while loops without clear index control
• Misusing match for iteration

3. What is the output of the spiral traversal on this 3x3 matrix?

let matrix = vec![
  vec![1, 2, 3],
  vec![4, 5, 6],
  vec![7, 8, 9],
];
// Spiral traversal code prints elements in order

medium

A. [1, 2, 3, 6, 9, 8, 7, 4, 5]

B. [1, 4, 7, 8, 9, 6, 3, 2, 5]

C. [1, 2, 3, 4, 5, 6, 7, 8, 9]

D. [9, 8, 7, 6, 5, 4, 3, 2, 1]

Solution

1. Step 1: Trace spiral traversal order

   Start top row left to right: 1, 2, 3; then right column down: 6, 9; bottom row right to left: 8, 7; left column up: 4; center element: 5.

2. Step 2: Write elements in order

   Combined order is [1, 2, 3, 6, 9, 8, 7, 4, 5].

3. Final Answer:

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

4. Quick Check:

   Outer to inner spiral = [1,2,3,6,9,8,7,4,5] [OK]

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

Common Mistakes:

• Listing elements row-wise instead of spiral
• Reversing order of bottom or left edges
• Skipping center element

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

let mut top = 0;
let mut bottom = matrix.len() - 1;
let mut left = 0;
let mut right = matrix[0].len() - 1;
while top <= bottom && left <= right {
  for i in left..=right {
    print!("{} ", matrix[top][i]);
  }
  top += 1;
  for i in top..=bottom {
    print!("{} ", matrix[i][right]);
  }
  right -= 1;
  for i in (left..=right).rev() {
    print!("{} ", matrix[bottom][i]);
  }
  bottom -= 1;
  for i in (top..=bottom).rev() {
    print!("{} ", matrix[i][left]);
  }
  left += 1;
}

medium

A. The loop may print elements twice when top > bottom or left > right

B. The ranges in for loops are incorrect and cause syntax errors

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

D. The print statements use wrong matrix indices causing runtime panic

Solution

1. Step 1: Analyze loop conditions and updates

   The while loop condition is correct, but inside the loop, after updating top, bottom, left, right, the for loops still run without checking if top <= bottom or left <= right again.

2. Step 2: Identify consequence of missing checks

   This can cause the inner loops to run when top > bottom or left > right, printing elements twice or causing invalid access.

3. Final Answer:

   The loop may print elements twice when top > bottom or left > right -> Option A

4. Quick Check:

   Missing inner boundary checks = duplicate prints [OK]

Hint: Check boundaries before each edge traversal [OK]

Common Mistakes:

• Not checking boundaries inside the loop after updates
• Assuming while condition covers all cases
• Ignoring reverse ranges correctness

5. Given a rectangular matrix with dimensions 3x5, how many elements will be printed in spiral traversal, and what is the order of traversal directions?

hard

A. 15 elements; order: left to right, bottom to top, right to left, top to bottom, repeat

B. 15 elements; order: top to bottom, left to right, bottom to top, right to left, repeat

C. 8 elements; order: left to right, top to bottom, right to left, bottom to top, repeat

D. 15 elements; order: left to right, top to bottom, right to left, bottom to top, repeat

Solution

1. Step 1: Calculate total elements in 3x5 matrix

   3 rows * 5 columns = 15 elements to print in spiral traversal.

2. Step 2: Identify traversal direction order

   Spiral traversal moves: left to right (top row), top to bottom (right column), right to left (bottom row), bottom to top (left column), then repeats inward.

3. Final Answer:

   15 elements; order: left to right, top to bottom, right to left, bottom to top, repeat -> Option D

4. Quick Check:

   3*5=15; spiral directions = LR, TB, RL, BT [OK]

Hint: Count total elements; remember spiral direction cycle [OK]

Common Mistakes:

• Miscounting total elements
• Mixing up traversal direction order
• Assuming fewer elements printed