Top Interview 150

The Spiral Matrix problem is a common challenge involving matrix traversal. Let’s break down LeetCode 54: Spiral Matrix and implement a solution that works for any m×n matrix.

🚀 Problem Description

Given an m×n matrix, traverse it in spiral order and return the elements in a single array.

💡 Examples

Example 1

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]  
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Example 2

Input: matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]  
Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Constraints

• 1≤m,n≤10
• −100≤matrix[i][j]≤100

🏆 JavaScript Solution

We solve this problem by defining four boundaries (top, bottom, left, and right) that shrink as we traverse the matrix in spiral order.

Implementation

var spiralOrder = function(matrix) {
    const result = [];
    let top = 0;
    let bottom = matrix.length - 1;
    let left = 0;
    let 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;
};

🔍 How It Works

1. Define Boundaries:

   • top: Tracks the topmost row.
   • bottom: Tracks the bottommost row.
   • left: Tracks the leftmost column.
   • right: Tracks the rightmost column.

2. Traverse in Spiral Order:

   • Left to Right: Traverse the top row, then increment top.
   • Top to Bottom: Traverse the rightmost column, then decrement right.
   • Right to Left: Traverse the bottom row (if it exists), then decrement bottom.
   • Bottom to Top: Traverse the leftmost column (if it exists), then increment left.

3. Check for Overlap:

   • Ensure the boundaries (top, bottom, left, right) do not overlap before processing each direction.

🔑 Complexity Analysis

• Time Complexity: O(m⋅n), where m is the number of rows and n is the number of columns.

  • Each element is processed once.

• Space Complexity: O(1), excluding the space required for the output array.

📋 Dry Run

Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

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

✨ Pro Tips for Interviews

1. Clarify Constraints:

   • Ask if the input matrix can be empty.
   • Confirm if non-rectangular matrices are possible (unlikely, but good to clarify).

2. Discuss Edge Cases:

   • Single-row matrix: [[1, 2, 3]].
   • Single-column matrix: [[1], [2], [3]].
   • Smallest possible matrix: [[1]].

3. Highlight Efficiency:

   • Explain why the shrinking boundary approach is O(m⋅n).

📚 Learn More

Check out the full explanation and code walkthrough on my previous Dev.to post:
👉 Valid Sudoku - JavaScript Solution

What’s your preferred method to solve this problem? Let’s discuss! 🚀