4.3 Spiral Matrix

4.3.1 Problem Metadata

4.3.2 Description

Given an m x n matrix, return all elements in spiral order.

4.3.3 Examples

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

4.3.4 Constraints

  • 1 <= m, n <= 10

4.3.5 Solution - Boundary Simulation

4.3.5.1 Walkthrough

Maintain four boundaries (top, bottom, left, right). Traverse in the order: top row → right column → bottom row → left column, shrinking the corresponding boundary after each pass. Stop when pointers cross.

4.3.5.2 Analysis

  • Time Complexity: O(m * n)
  • Space Complexity: O(1) (excluding output)

4.3.5.3 Implementation Steps

  1. Initialize top = 0, bottom = m-1, left = 0, right = n-1.
  2. While top <= bottom and left <= right:
    • Traverse top row left→right, increment top.
    • Traverse right column top→bottom, decrement right.
    • If top <= bottom, traverse bottom row right→left, decrement bottom.
    • If left <= right, traverse left column bottom→top, increment left.

4.3.5.4 Code - Java

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix.length == 0) {
        return result;
    }

    // Define top, bottom, left, right boundaries (border cells)
    int top = 0;
    int bottom = matrix.length - 1;
    int left = 0;
    int right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        // Traverse top-most row (left to right)
        for (int col = left; col <= right; col++) {
            result.add(matrix[top][col]);
        }
        top++;

        // Traverse right-most column (top to bottom)
        for (int row = top; row <= bottom; row++) {
            result.add(matrix[row][right]);
        }
        right--;

        // Traverse bottom-most row (right to left)
        // Check to avoid duplicate row traversal
        if (top <= bottom) {
            for (int col = right; col >= left; col--) {
                result.add(matrix[bottom][col]);
            }
            bottom--;
        }

        // Traverse left-most column (bottom to top)
        // Check to avoid duplicate column traversal
        if (left <= right) {
            for (int row = bottom; row >= top; row--) {
                result.add(matrix[row][left]);
            }
            left++;
        }
    }

    return result;
}

4.3.5.5 Code - Golang

func spiralOrder(matrix [][]int) []int {
    result := make([]int, 0)

    // Define top, bottom, left, right boundaries (border cells)
    t := 0
    b := len(matrix) - 1
    l := 0
    r := len(matrix[0]) - 1

    for t <= b && l <= r {
        // Traverse top-most row (left to right)
        for j := l; j <= r; j++ {
            result = append(result, matrix[t][j])
        }
        t++

        // Traverse right-most column (top to bottom)
        for i := t; i <= b; i++ {
            result = append(result, matrix[i][r])
        }
        r--

        // Traverse bottom-most row (right to left)
        // Check to avoid duplicate row traversal
        if t <= b {
            for j := r; j >= l; j-- {
                result = append(result, matrix[b][j])
            }
            b--
        }

        // Traverse left-most column (bottom to top)
        // Check to avoid duplicate column traversal
        if l <= r {
            for i := b; i >= t; i-- {
                result = append(result, matrix[i][l])
            }
            l++
        }
    }

    return result
}