Spiral Matrix medium

Problem Statement

Given an m x n matrix, return all elements of the matrix 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]

Steps

The spiral traversal can be achieved by simulating the movement of a boundary. We'll use four pointers: top, bottom, left, and right to define the current boundary of the untraversed matrix. In each iteration, we traverse one layer of the matrix.

1. Initialization: Initialize top = 0, bottom = m - 1, left = 0, right = n - 1. Initialize an empty array result to store the spiral order traversal.

2. Iteration: While left <= right and top <= bottom:

   • Traverse Right: Traverse from left to right adding elements to result.
   • Traverse Down: Traverse from top + 1 to bottom adding elements to result.
   • Traverse Left: Traverse from right - 1 to left (if top < bottom and left < right) adding elements to result.
   • Traverse Up: Traverse from bottom - 1 to top + 1 (if top < bottom and left < right) adding elements to result.
   • Update Boundaries: Move the boundaries inwards: top++, bottom--, left++, right--.

3. Return Result: Return the result array.

Explanation

The algorithm systematically shrinks the boundary of the matrix in each iteration. By traversing the right, bottom, left, and top edges successively, it guarantees a spiral traversal. The condition checks (top < bottom and left < right) in the left and up traversals are necessary to prevent duplicates or out-of-bounds access when the matrix has only one row or one column remaining.

Code

function spiralOrder(matrix: number[][]): number[] {
    const m = matrix.length;
    const n = matrix[0].length;
    const result: number[] = [];
    let top = 0, bottom = m - 1, left = 0, right = n - 1;

    while (left <= right && top <= bottom) {
        // Traverse Right
        for (let i = left; i <= right; i++) {
            result.push(matrix[top][i]);
        }
        top++;

        // Traverse Down
        for (let i = top; i <= bottom; i++) {
            result.push(matrix[i][right]);
        }
        right--;

        if (top <= bottom && left <= right) { // Prevent duplicate traversal for single row/column
            // Traverse Left
            for (let i = right; i >= left; i--) {
                result.push(matrix[bottom][i]);
            }
            bottom--;

            // Traverse Up
            for (let i = bottom; i >= top; i--) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }

    return result;
}

Complexity

• Time Complexity: O(m * n), where 'm' and 'n' are the dimensions of the matrix. We visit each element exactly once.
• Space Complexity: O(m * n) in the worst case (when the matrix is a single row or column), to store the result array. In most cases, it will be less, but still proportional to the number of elements.