Spiral Matrix Traversal in DSA Typescript - Time & Space Complexity

Time Complexity: Spiral Matrix Traversal

O(m * n)

Understanding Time Complexity

We want to understand how the time needed to read all elements in a matrix in spiral order 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.

function spiralOrder(matrix: number[][]): number[] {
  const result: number[] = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    for (let i = left; i <= right; i++) result.push(matrix[top][i]);
    top++;
    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
    right--;
    if (top <= bottom) {
      for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
      bottom--;
    }
    if (left <= right) {
      for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
      left++;
    }
  }
  return result;
}
    

This code reads 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: The loops that traverse the matrix edges in each spiral layer.
• How many times: Each element of the matrix is visited exactly once as the loops move inward.

How Execution Grows With Input

As the matrix size grows, the number of elements to visit grows too, and the loops cover all elements once.

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

Pattern observation: The operations grow roughly proportional to the total number of elements, so if the matrix size doubles, the operations roughly quadruple.

Final Time Complexity

Time Complexity: O(m * n)

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

Common Mistake

[X] Wrong: "The loops inside loops mean the time is squared or worse, like O(n²) always."

[OK] Correct: Although there are nested loops, each element is visited only once in total, so the time grows linearly with the number of elements, not squared.

Interview Connect

Understanding how to analyze traversal of 2D structures like matrices is a key skill that shows you can reason about loops and data size clearly.

Self-Check

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

Practice

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

easy

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

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

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

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 first, 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 this circular, inward movement. Others describe linear or diagonal traversals.

3. Final Answer:

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

4. Quick Check:

   Spiral traversal = circular inward movement [OK]

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

Common Mistakes:

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

2. Which of the following TypeScript code snippets correctly initializes variables for spiral traversal boundaries?

easy

A. let top = -1, bottom = matrix.length - 1, left = -1, right = matrix[0].length - 1;

B. let top = 1, bottom = matrix.length, left = 1, right = matrix[0].length;

C. let top = 0, bottom = matrix.length, left = 0, right = matrix[0].length;

D. let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;

Solution

1. Step 1: Identify correct boundary initialization

   Top and left start at 0 (first row and column). Bottom and right are last indices, so length - 1.

2. Step 2: Check options

   let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1; correctly sets top=0, bottom=rows-1, left=0, right=cols-1. Others have off-by-one or negative values.

3. Final Answer:

   let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1; -> Option D

4. Quick Check:

   Boundaries start at 0 and end at length-1 [OK]

Hint: Remember array indices start at 0 [OK]

Common Mistakes:

• Using length instead of length - 1 for boundaries
• Starting top or left at 1 instead of 0
• Using negative indices incorrectly

3. Given a rectangular matrix with 3 rows and 5 columns, how many elements will be printed after a complete spiral traversal?

easy

A. 15

B. 8

C. 12

D. 10

Solution

1. Step 1: Calculate total elements in matrix

   Number of elements = rows x columns = 3 x 5 = 15.

2. Step 2: Understand spiral traversal covers all elements

   Spiral traversal visits every element exactly once, so all 15 elements are printed.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Total elements = rows x columns = 15 [OK]

Hint: Spiral prints all elements once [OK]

Common Mistakes:

• Confusing spiral length with perimeter
• Counting only outer layer elements
• Ignoring rectangular shape

4. What is the output of the following TypeScript code for spiral traversal?

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

function spiralOrder(matrix: number[][]): number[] {
  const result: number[] = [];
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    for (let i = left; i <= right; i++) result.push(matrix[top][i]);
    top++;
    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
    right--;
    if (top <= bottom) {
      for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
      bottom--;
    }
    if (left <= right) {
      for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
      left++;
    }
  }
  return result;
}

console.log(spiralOrder(matrix));

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. [9, 8, 7, 4, 1, 2, 3, 6, 5]

Solution

1. Step 1: Trace the spiral traversal on the matrix

   Start top row left to right: 1,2,3
   Right column top to bottom: 6,9
   Bottom row right to left: 8,7
   Left column bottom to top: 4
   Now inner layer: 5

2. Step 2: Combine all elements in order

   Result array: [1,2,3,6,9,8,7,4,5]

3. Final Answer:

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

4. Quick Check:

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

Hint: Visualize peeling matrix edges in order [OK]

Common Mistakes:

• Reading rows only left to right
• Skipping inner elements
• Mixing traversal directions

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

while (top < bottom && left < right) {
  for (let i = left; i <= right; i++) result.push(matrix[top][i]);
  top++;
  for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
  right--;
  for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
  bottom--;
  for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
  left++;
}

medium

A. The for loops should use < instead of <= to avoid index out of bounds

B. The variables top, bottom, left, right are not initialized

C. The while loop condition should use <= instead of < to include last row and column

D. The result array is not declared before the loop

Solution

1. Step 1: Analyze the while loop condition

   Using < excludes the last row and column when top == bottom or left == right, missing elements.

2. Step 2: Correct the condition

   Change while (top < bottom && left < right) to while (top <= bottom && left <= right) to include all layers.

3. Final Answer:

   The while loop condition should use <= instead of < to include last row and column -> Option C

4. Quick Check:

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

Hint: Use <= to include boundary rows and columns [OK]

Common Mistakes:

• Using < excludes last layer elements
• Not updating boundaries inside loop
• Forgetting to check conditions before loops