Spiral Matrix Traversal in DSA Javascript - 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.

function spiralTraversal(matrix) {
  const result = [];
  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 collects elements of a 2D matrix in a spiral order starting from the top-left corner.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing each element of the matrix exactly once.
• How many times: Each element is visited once through nested 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
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 n squared.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the total number of elements in the matrix.

Common Mistake

[X] Wrong: "The spiral traversal takes more time than just visiting all elements once because of the loops inside loops."

[OK] Correct: Even though there are nested loops, each element is visited only once, so the total steps equal the number of elements.

Interview Connect

Understanding this helps you explain how to handle matrix traversal efficiently, a common task in coding challenges and real projects.

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 row by row from top to bottom

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

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

D. Traverse the matrix diagonally from top-left to bottom-right

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 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 B

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 traversal
• Ignoring the inward movement after outer layer

2. Which of the following is the correct way to initialize variables for spiral traversal boundaries in JavaScript?

easy

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

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

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

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

Solution

1. Step 1: Understand matrix indexing

   Matrix indices start at 0, so top and left start at 0, bottom and right at length - 1.

2. Step 2: Check options

   let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1; correctly sets boundaries using zero-based indexing. Others use incorrect start or end values.

3. Final Answer:

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

4. Quick Check:

   Zero-based indexing for boundaries [OK]

Hint: Remember arrays start at 0 in JavaScript [OK]

Common Mistakes:

• Starting indices at 1 instead of 0
• Using length instead of length - 1 for boundaries
• Setting negative indices incorrectly

3. What is the output of the following code?

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

function spiralTraversal(mat) {
  const result = [];
  let top = 0, bottom = mat.length - 1;
  let left = 0, right = mat[0].length - 1;

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

console.log(spiralTraversal(matrix));

medium

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

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

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

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

Solution

1. Step 1: Traverse top row left to right

   Elements: 1, 2, 3

2. Step 2: Traverse right column top to bottom

   Elements: 6, 9

3. Step 3: Traverse bottom row right to left

   Elements: 8, 7

4. Step 4: Traverse left column bottom to top

   Elements: 4

5. Step 5: Traverse inner matrix

   Element: 5

6. Final Answer:

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

7. Quick Check:

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

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

Common Mistakes:

• Mixing order of bottom row traversal
• Skipping the inner element 5
• Incorrect boundary updates causing repeats

4. Identify the error in this spiral traversal code snippet:

function spiral(mat) {
  let top = 0, bottom = mat.length - 1;
  let left = 0, right = mat[0].length - 1;
  const res = [];

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

medium

A. The while loop condition should be <= instead of < to include single rows or columns

B. The for loops should use < instead of <= to avoid index errors

C. The variables top and bottom are swapped incorrectly

D. The result array is not initialized properly

Solution

1. Step 1: Analyze loop condition

   The condition 'top < bottom && left < right' skips the case when top equals bottom or left equals right, missing last row or column.

2. Step 2: Correct condition

   Changing to 'top <= bottom && left <= right' ensures all rows and columns are included in traversal.

3. Final Answer:

   The while loop condition should be <= instead of < to include single rows or columns -> Option A

4. Quick Check:

   Use <= to cover all layers [OK]

Hint: Use <= in loop condition to cover all matrix layers [OK]

Common Mistakes:

• Using < causes missing last row or column
• Changing for loop bounds incorrectly
• Swapping top and bottom variables

5. Given a rectangular matrix of size 3x4:

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

What is the 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, 7, 6]

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

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

Solution

1. Step 1: Traverse top row left to right

   Elements: 1, 2, 3, 4

2. Step 2: Traverse right column top to bottom

   Elements: 8, 12

3. Step 3: Traverse bottom row right to left

   Elements: 11, 10, 9

4. Step 4: Traverse left column bottom to top

   Element: 5

5. Step 5: Traverse inner row left to right

   Elements: 6, 7

6. Final Answer:

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

7. Quick Check:

   Follow edges clockwise, then inner row [OK]

Hint: Remember to handle rectangular shapes carefully [OK]

Common Mistakes:

• Mixing order of inner elements
• Skipping last inner row
• Confusing left column traversal order