[LeetCode] 54. Spiral Matrix

Table of Contents

Description

Given an $m \times n$ matrix, return its elements in spiral order.

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]

Approach

To traverse a matrix in spiral order, we can use four pointers to track the current boundaries: top, bottom, left, and right. We iterate over the matrix in layers, moving right, down, left, and up, shrinking the boundaries after each direction until all elements are visited.

Solution

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
  const m = matrix[0].length;
  const n = matrix.length;
  let result = [];

  for (let top = 0, right = m - 1, bottom = n - 1, left = 0; ; ) {
    // Traverse from left to right
    for (let i = left; i <= right; i++) result.push(matrix[top][i]);
    top++;
    if (top > bottom) break;

    // Traverse from top to bottom
    for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
    right--;
    if (left > right) break;

    // Traverse from right to left
    for (let i = right; i >= left; i--) result.push(matrix[bottom][i]);
    bottom--;

    if (top > bottom) break;

    // Traverse from bottom to top
    for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
    left++;
    if (left > right) break;
  }

  return result;
};

Complexity Analysis

Time Complexity

The time complexity is $O(m \times n)$, where $m$ is the number of rows and $n$ is the number of columns. Each element is visited exactly once.

Space Complexity

The space complexity is $O(1)$ for extra variables, but $O(m \times n)$ is needed for the output array.