Spiral Matrix Traversal in DSA Rust - Execution Trace

Concept Flow - Spiral Matrix Traversal

Start with matrix boundaries

↓

Traverse top row left to right

↓

Traverse right column top to bottom

↓

Traverse bottom row right to left

↓

Traverse left column bottom to top

↓

Shrink boundaries inward

↓

Repeat until boundaries cross

We move around the matrix edges in a spiral, adjusting boundaries inward after each full round.

Execution Sample

DSA Rust

fn spiral_traversal(matrix: &Vec<Vec<i32>>) -> Vec<i32> {
    let (mut top, mut bottom) = (0, matrix.len() - 1);
    let (mut left, mut right) = (0, matrix[0].len() - 1);
    let mut result = Vec::new();
    while left <= right && top <= bottom {
        for i in left..=right { result.push(matrix[top][i]); }
        top += 1;
        for i in top..=bottom { result.push(matrix[i][right]); }
        right -= 1;
        if top <= bottom {
            for i in (left..=right).rev() { result.push(matrix[bottom][i]); }
            bottom -= 1;
        }
        if left <= right {
            for i in (top..=bottom).rev() { result.push(matrix[i][left]); }
            left += 1;
        }
    }
    result
}

This code collects matrix elements in spiral order by moving along edges and shrinking boundaries.

Execution Table

Step	Operation	Top	Bottom	Left	Right	Elements Added	Result So Far	Visual State
1	Traverse top row left to right	0	2	0	2	[1, 2, 3]	[1, 2, 3]	[1, 2, 3] 4 5 6 7 8 9
2	Move top boundary down	1	2	0	2	[]	[1, 2, 3]	[1, 2, 3] 4 5 6 7 8 9
3	Traverse right column top to bottom	1	2	0	2	[6, 9]	[1, 2, 3, 6, 9]	[1, 2, 3] 4 5 6 7 8 9
4	Move right boundary left	1	2	0	1	[]	[1, 2, 3, 6, 9]	[1, 2, 3] 4 5 6 7 8 9
5	Traverse bottom row right to left	1	2	0	1	[8, 7]	[1, 2, 3, 6, 9, 8, 7]	[1, 2, 3] 4 5 6 7 8 9
6	Move bottom boundary up	1	1	0	1	[]	[1, 2, 3, 6, 9, 8, 7]	[1, 2, 3] 4 5 6 7 8 9
7	Traverse left column bottom to top	1	1	0	1	[4]	[1, 2, 3, 6, 9, 8, 7, 4]	[1, 2, 3] 4 5 6 7 8 9
8	Move left boundary right	1	1	1	1	[]	[1, 2, 3, 6, 9, 8, 7, 4]	[1, 2, 3] 4 5 6 7 8 9
9	Traverse top row left to right	1	1	1	1	[5]	[1, 2, 3, 6, 9, 8, 7, 4, 5]	[1, 2, 3] 4 5 6 7 8 9
10	Move top boundary down	2	1	1	1	[]	[1, 2, 3, 6, 9, 8, 7, 4, 5]	[1, 2, 3] 4 5 6 7 8 9
11	Check boundaries	2	1	1	1	[]	[1, 2, 3, 6, 9, 8, 7, 4, 5]	Boundaries crossed, stop

💡 Top boundary (2) > Bottom boundary (1), loop ends

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	Final
top	0	1	1	1	1	2	2
bottom	2	2	2	2	1	1	1
left	0	0	0	0	0	1	1
right	2	2	1	1	1	1	1
result	[]	[1, 2, 3]	[1, 2, 3, 6, 9]	[1, 2, 3, 6, 9, 8, 7]	[1, 2, 3, 6, 9, 8, 7, 4]	[1, 2, 3, 6, 9, 8, 7, 4, 5]	[1, 2, 3, 6, 9, 8, 7, 4, 5]

Key Moments - 3 Insights

Why do we check boundaries after each side traversal?

Because after moving boundaries inward, the top can become greater than bottom or left greater than right, which means no more elements to traverse. This is shown in step 11 where top (2) > bottom (1) stops the loop.

Why do we traverse bottom row and left column only if boundaries allow?

To avoid repeating rows or columns when the matrix has odd dimensions or when boundaries cross. See steps 5 and 7 where traversal happens only if top <= bottom and left <= right.

How does the result build up in spiral order?

Elements are added in order: top row left to right, right column top to bottom, bottom row right to left, left column bottom to top, then boundaries shrink and repeat. This is visible in the 'Elements Added' and 'Result So Far' columns.

Visual Quiz - 3 Questions

Look at the execution table, what elements are added at step 5?

A [6, 9]

B [8, 7]

C [4]

D [5]

💡 Hint

Check the 'Elements Added' column at step 5 in the execution_table.

At which step does the top boundary move down for the second time?

A Step 2

B Step 4

C Step 10

D Step 8

💡 Hint

Look at the 'Operation' and 'Top' column changes in the execution_table.

If the matrix was 1x1, how many elements would be added in the first traversal?

A 1

B 2

C 0

D None, loop never starts

💡 Hint

Consider the first traversal of the top row in the code and how boundaries are initialized.

Concept Snapshot

Spiral Matrix Traversal:
- Use four boundaries: top, bottom, left, right
- Traverse edges in order: top row, right column, bottom row, left column
- After each edge, move boundary inward
- Repeat until boundaries cross
- Collect elements in order for spiral output

Full Transcript

Spiral Matrix Traversal moves around the edges of a matrix collecting elements in a spiral order. We start with four boundaries: top, bottom, left, and right. First, we traverse the top row from left to right, then move the top boundary down. Next, we traverse the right column from top to bottom, then move the right boundary left. Then, if boundaries allow, we traverse the bottom row from right to left and move the bottom boundary up. After that, if boundaries allow, we traverse the left column from bottom to top and move the left boundary right. We repeat these steps until the top boundary crosses the bottom or the left crosses the right, meaning all elements have been visited. The result is a list of elements in spiral order.

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