Saltar al contenido principal

Spiral Matrix

Given a 2D matrix, return a list containing all of its elements in spiral order.

Note: Spiral order means traversing the matrix in a clockwise spiral, starting from the top-left corner and moving right, then down, then left, then up, and repeating.

Example(s)​

Example 1:

Input: matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Explanation:
Start at top-left (1), go right: 1→2→3
Then go down: 6→9
Then go left: 8→7
Then go up: 4
Then go right: 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]
Explanation:
Right: 1→2→3→4
Down: 8→12
Left: 11→10→9
Up: 5
Right: 6→7

Example 3:

Input: matrix = [
  [1, 2],
  [3, 4]
]
Output: [1, 2, 4, 3]

Example 4:

Input: matrix = [[1]]
Output: [1]

Solution​

The solution uses boundary tracking:

  1. Define boundaries: Track top, bottom, left, right boundaries
  2. Traverse in layers: Process the outer layer, then move inward
  3. Four directions:
    • Right: from left to right along top row
    • Down: from top to bottom along right column
    • Left: from right to left along bottom row
    • Up: from bottom to top along left column
  4. Update boundaries: After each direction, update the boundary
  5. Terminate: Stop when boundaries cross

JavaScript Solution - Boundary Tracking

/**
* Traverse matrix in spiral order
* @param {number[][]} matrix - 2D matrix
* @return {number[]} - Elements in spiral order
*/
function spiralOrder(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
  return [];
}

const result = [];
let top = 0;
let bottom = matrix.length - 1;
let left = 0;
let right = matrix[0].length - 1;

while (top <= bottom && left <= right) {
  // Traverse right along top row
  for (let i = left; i <= right; i++) {
    result.push(matrix[top][i]);
  }
  top++; // Move top boundary down
  
  // Traverse down along right column
  for (let i = top; i <= bottom; i++) {
    result.push(matrix[i][right]);
  }
  right--; // Move right boundary left
  
  // Traverse left along bottom row (if still valid)
  if (top <= bottom) {
    for (let i = right; i >= left; i--) {
      result.push(matrix[bottom][i]);
    }
    bottom--; // Move bottom boundary up
  }
  
  // Traverse up along left column (if still valid)
  if (left <= right) {
    for (let i = bottom; i >= top; i--) {
      result.push(matrix[i][left]);
    }
    left++; // Move left boundary right
  }
}

return result;
}

// Test cases
const matrix1 = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
console.log('Example 1:', spiralOrder(matrix1)); 
// [1, 2, 3, 6, 9, 8, 7, 4, 5]

const matrix2 = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
];
console.log('Example 2:', spiralOrder(matrix2)); 
// [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

const matrix3 = [
[1, 2],
[3, 4]
];
console.log('Example 3:', spiralOrder(matrix3)); 
// [1, 2, 4, 3]

const matrix4 = [[1]];
console.log('Example 4:', spiralOrder(matrix4)); 
// [1]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Direction-Based)​

Here's a direction-based approach using a direction vector:

/**
 * Direction-based approach
 */
function spiralOrderDirection(matrix) {
  if (!matrix || matrix.length === 0) return [];
  
  const result = [];
  const rows = matrix.length;
  const cols = matrix[0].length;
  const visited = Array(rows).fill().map(() => Array(cols).fill(false));
  
  // Directions: right, down, left, up
  const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  let dir = 0; // Start with right
  let row = 0, col = 0;
  
  for (let i = 0; i < rows * cols; i++) {
    result.push(matrix[row][col]);
    visited[row][col] = true;
    
    // Calculate next position
    const nextRow = row + directions[dir][0];
    const nextCol = col + directions[dir][1];
    
    // Check if we need to change direction
    if (
      nextRow < 0 || nextRow >= rows ||
      nextCol < 0 || nextCol >= cols ||
      visited[nextRow][nextCol]
    ) {
      // Change direction (right -> down -> left -> up -> right)
      dir = (dir + 1) % 4;
    }
    
    // Move to next position
    row += directions[dir][0];
    col += directions[dir][1];
  }
  
  return result;
}

Complexity​

  • Time Complexity: O(m × n) - Where m is the number of rows and n is the number of columns. We visit each cell exactly once.
  • Space Complexity: O(1) - For the boundary tracking approach, we only use a constant amount of extra space (excluding the output array). For the direction-based approach, it's O(m × n) for the visited array.

Approach​

The solution uses boundary tracking:

  1. Initialize boundaries:

    • top = 0, bottom = rows - 1
    • left = 0, right = cols - 1

  2. Traverse in four directions:

    • Right: From left to right along top row, then top++
    • Down: From top to bottom along right column, then right--
    • Left: From right to left along bottom row, then bottom--
    • Up: From bottom to top along left column, then left++

  3. Boundary checks: Before traversing left and up, check if boundaries are still valid

  4. Termination: Stop when top > bottom or left > right

Key Insights​

  • Boundary tracking: Maintain four boundaries that shrink as we traverse
  • Layer by layer: Process outer layer, then move inward
  • Four directions: Always traverse in the same order (right, down, left, up)
  • Boundary validation: Check boundaries before left and up to avoid duplicates
  • Single pass: Each element is visited exactly once

Step-by-Step Example​

Let's trace through Example 1: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Initial: top=0, bottom=2, left=0, right=2

Iteration 1:
  Right: left=0 to right=2
    result = [1, 2, 3]
    top = 1
  
  Down: top=1 to bottom=2
    result = [1, 2, 3, 6, 9]
    right = 1
  
  Left: right=1 to left=0 (top=1 <= bottom=2 ✓)
    result = [1, 2, 3, 6, 9, 8, 7]
    bottom = 1
  
  Up: bottom=1 to top=1 (left=0 <= right=1 ✓)
    result = [1, 2, 3, 6, 9, 8, 7, 4]
    left = 1

Iteration 2:
  Right: left=1 to right=1
    result = [1, 2, 3, 6, 9, 8, 7, 4, 5]
    top = 2
  
  Check: top=2 > bottom=1 → break

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

Visual Representation​

Matrix:        Spiral traversal:
[1, 2, 3]      → → →
[4, 5, 6]      →     ↓
[7, 8, 9]      ← ← ← ↑

Step 1: Right  → 1, 2, 3
Step 2: Down    → 6, 9
Step 3: Left    → 8, 7
Step 4: Up      → 4
Step 5: Right   → 5

Edge Cases​

  • Empty matrix: Return []
  • Single row: [[1, 2, 3]] → [1, 2, 3]
  • Single column: [[1], [2], [3]] → [1, 2, 3]
  • Single element: [[1]] → [1]
  • Rectangular matrix: Works for any m × n matrix
  • 1×n or n×1: Handled correctly

Important Notes​

  • Boundary checks: The checks if (top <= bottom) and if (left <= right) are crucial to avoid processing the same row/column twice
  • Order matters: Always traverse in the order: right → down → left → up
  • Boundary updates: Update boundaries after each direction
  • Rectangular matrices: Works for both square and rectangular matrices
  • Spiral Matrix II: Generate a matrix in spiral order
  • Spiral Matrix III: Spiral traversal starting from a specific position
  • Rotate Image: Rotate matrix 90 degrees (related concept)
  • Set Matrix Zeroes: Matrix manipulation problem

Takeaways​

  • Boundary tracking is the most efficient approach (O(1) space)
  • Four directions in fixed order: right, down, left, up
  • Boundary validation prevents duplicate processing
  • Layer-by-layer approach processes outer layer first
  • Works for any size matrix (square or rectangular)