Spiral Matrix — Four-Boundary Walk Template

Spiral Matrix tests one thing: can you keep four moving boundaries straight without an off-by-one? Yes, if you write the template once and trust it.

The Problem

Given an m x n matrix, return all elements of the matrix in spiral order, starting at the top-left and going clockwise.

Example:

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

Intuition

Maintain four shrinking boundaries: top, bottom, left, right. Walk one edge at a time and contract that boundary after each edge. After the top row, top increments; after the right column, right decrements; and so on. Two guards — if top <= bottom before the bottom edge and if left <= right before the left edge — handle rectangular and odd-sized cases without double-counting cells.

Explanation with Example

matrix = [[1,2,3],[4,5,6],[7,8,9]]. Bounds: top=0, bottom=2, left=0, right=2.

• Top row: append 1, 2, 3. top=1.
• Right column: append 6, 9. right=1.
• Bottom row right-to-left: append 8, 7. bottom=1.
• Left column bottom-to-top: append 4. left=1.

Now top=1, bottom=1, left=1, right=1.

• Top row: append 5. top=2.
• Right column: nothing (top > bottom). Loop exits at next iteration.

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

matrix:           visit order (1..9):
[1 2 3]             1 -> 2 -> 3
[4 5 6]                       |
[7 8 9]                       v
                            6
boundary updates:             |
start: top=0 bot=2          v
       left=0 right=2  9 <- 8 <- 7
after top row:    top=1     |
after right col:  right=1   v
after bottom row: bot=1     4 -> 5
after left col:   left=1
inner: just 5

Code

def spiral_order(matrix):
    if not matrix:
        return []
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):
            result.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):
                result.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):
                result.append(matrix[r][left])
            left += 1
    return result

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix.length == 0) return result;
    int top = 0, bottom = matrix.length - 1;
    int left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) result.add(matrix[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
            left++;
        }
    }
    return result;
}

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if (matrix.empty()) return result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
    while (top <= bottom && left <= right) {
        for (int c = left; c <= right; c++) result.push_back(matrix[top][c]);
        top++;
        for (int r = top; r <= bottom; r++) result.push_back(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (int c = right; c >= left; c--) result.push_back(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (int r = bottom; r >= top; r--) result.push_back(matrix[r][left]);
            left++;
        }
    }
    return result;
}

Edge Cases

• Empty matrix or empty first row: return [].
• Single row: the first inner loop appends everything; the second appends nothing because top > bottom after the increment.
• Single column: symmetric to the single-row case.
• Non-square matrix like 2x4 or 4x2: the guards if top <= bottom and if left <= right prevent the final leg from double-counting cells.

Complexity Analysis

• Time: O(m*n). Every cell is visited exactly once.
• Space: O(1) extra beyond the output list.

The boundary approach beats the visited-matrix brute force in space and keeps the logic flat.

How to Explain It in an Interview

Draw the four-boundary picture. Say: “Each layer is four edges. I’ll walk them in order and shrink the corresponding boundary.” Emphasize the two guards before the third and fourth edges; they handle the rectangular cases. Walk through a 3x3 once and a 2x4 once to demonstrate that the guards matter.

Related Problems

• Spiral Matrix II (construct the spiral)
• Rotate Image (transpose + reverse)
• Spiral Matrix III (start from arbitrary cell)
• Diagonal Traverse

Wrap up

Spiral Matrix rewards a clean template and disciplined boundary updates. Write the four-boundary version a couple of times and the guards become muscle memory. Pair it with Rotate Image in a matrix-manipulation study block to lock in 2D index gymnastics.