Spiral Matrix in JavaScript: is this too complicated

In this blog post, we’ll explore how to create a spiral matrix in JavaScript. This coding challenge is an excellent way to practice working with arrays, loops, and boundary conditions, while thinking through a pattern-based algorithm.

Problem Statement

Write a function that accepts an integer N and returns an (N \times N) spiral matrix. The matrix should be filled with numbers from 1 to (N^2) in a spiral order. Here are some examples:

matrix(2);
// Output:
// [[1, 2],
//  [4, 3]]

matrix(3);
// Output:
// [[1, 2, 3],
//  [8, 9, 4],
//  [7, 6, 5]]

matrix(4);
// Output:
// [[ 1,  2,  3, 4],
//  [12, 13, 14, 5],
//  [11, 16, 15, 6],
//  [10,  9,  8, 7]]

Understanding the Problem

To solve this problem, we need to fill a matrix in a spiral order, starting from the top-left corner and moving right. When we hit a boundary, we turn downward, then left, and finally upward, repeating the process until the entire matrix is filled.

Solution Approach

1. Create an empty (N \times N) matrix: We’ll initialize a matrix filled with zeros.
2. Define boundaries for the matrix: These boundaries will help control the spiral’s direction. We’ll keep track of four boundaries: top, bottom, left, and right.
3. Fill the matrix in a spiral pattern:

• Move from left to right along the top boundary.
• Move downward along the right boundary.
• Move from right to left along the bottom boundary.
• Move upward along the left boundary.
• After completing each full spiral (four steps), we adjust the boundaries inward and continue the process.

1. Stop when the matrix is completely filled.

JavaScript Code Implementation

Here’s a step-by-step implementation in JavaScript:

function matrix(n) {
  // Step 1: Create an empty NxN matrix
  const result = Array.from({ length: n }, () => Array(n).fill(0));

  // Step 2: Initialize boundaries
  let top = 0;
  let bottom = n - 1;
  let left = 0;
  let right = n - 1;

  // Step 3: Start filling the matrix
  let num = 1; // The current number to be filled

  while (top <= bottom && left <= right) {
    // Fill the top row
    for (let i = left; i <= right; i++) {
      result[top][i] = num++;
    }
    top++; // Move the top boundary down

    // Fill the right column
    for (let i = top; i <= bottom; i++) {
      result[i][right] = num++;
    }
    right--; // Move the right boundary left

    // Fill the bottom row (if still within bounds)
    if (top <= bottom) {
      for (let i = right; i >= left; i--) {
        result[bottom][i] = num++;
      }
      bottom--; // Move the bottom boundary up
    }

    // Fill the left column (if still within bounds)
    if (left <= right) {
      for (let i = bottom; i >= top; i--) {
        result[i][left] = num++;
      }
      left++; // Move the left boundary right
    }
  }

  // Step 4: Return the filled matrix
  return result;
}

// Test cases
console.log(matrix(2));
// Output:
// [[1, 2],
//  [4, 3]]

console.log(matrix(3));
// Output:
// [[1, 2, 3],
//  [8, 9, 4],
//  [7, 6, 5]]

console.log(matrix(4));
// Output:
// [[ 1,  2,  3, 4],
//  [12, 13, 14, 5],
//  [11, 16, 15, 6],
//  [10,  9,  8, 7]]

Explanation of the Code

1. Creating the Matrix: We use Array.from to create an (N \times N) matrix filled with zeros.
2. Setting Boundaries: The variables top, bottom, left, and right represent the current boundaries for the spiral.
3. Filling in Spiral Order:

• The top row is filled from left to right.
• The right column is filled from top to bottom.
• The bottom row is filled from right to left (if still within bounds).
• The left column is filled from bottom to top (if still within bounds).
• After each direction, the corresponding boundary is adjusted inward.

1. Termination Condition: The loop continues until all elements are filled (top <= bottom and left <= right).

Performance Analysis

• Time Complexity: (O(N^2)), where (N) is the size of the matrix, because we fill each element once.
• Space Complexity: (O(N^2)), as we need space for the (N \times N) matrix.

Variations to Try

1. Counter-Clockwise Spiral: Modify the solution to fill the matrix in a counter-clockwise spiral.
2. Rectangular Spiral: Extend the solution to handle an (M \times N) rectangular matrix.
3. Spiral in Reverse Order: Start from (N^2) and count down to 1.

Key Takeaways

1. Understanding Boundaries: Keeping track of boundaries helps in controlling the flow of the algorithm.
2. Array Manipulation: Working with multi-dimensional arrays is an essential skill for many programming problems.
3. Problem Decomposition: Breaking down the problem into smaller steps (filling rows/columns) makes it manageable.

Conclusion

Creating a spiral matrix is a fun and challenging exercise that can help you practice array manipulation and boundary management in JavaScript. Try experimenting with different variations to strengthen your understanding further.