51. Spiral Matrix

Keep four walls — top, bottom, left, right. Walk along the top wall, then the right wall, then the bottom, then the left, shrinking the corresponding wall inward after each pass. Repeat until the walls cross.

Idea

A spiral is four repeating moves: go right across the top, down the right side, left across the bottom, up the left side. After completing each edge we've consumed one row or column, so we move that wall inward and continue. When the walls cross, every cell has been emitted.

Algorithm

Maintain top, bottom, left, right. While top <= bottom and left <= right:

1. Left→right across row top; then top += 1.
2. Top→bottom down column right; then right -= 1.
3. If top <= bottom: right→left across row bottom; then bottom -= 1.
4. If left <= right: bottom→top up column left; then left += 1.

The two guards in steps 3 and 4 stop a single leftover row or column from being traversed twice.

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

• Top row → 1,2,3 (top=1). Right col → 6,9 (right=1). Bottom row ← 8,7 (bottom=1). Left col ↑ 4 (left=1).
• Now top=1,bottom=1,left=1,right=1: top row → 5 (top=2). Walls cross, stop.

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

Complexity

• Time: O(m·n) — each cell emitted once.
• Space: O(1) extra (ignoring the output list).

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] result = new int[m * n];
        int idx = 0;
        int top = 0, bottom = m - 1, left = 0, right = n - 1;
        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) result[idx++] = matrix[top][c];
            top++;
            for (int r = top; r <= bottom; r++) result[idx++] = matrix[r][right];
            right--;
            if (top <= bottom) {
                for (int c = right; c >= left; c--) result[idx++] = matrix[bottom][c];
                bottom--;
            }
            if (left <= right) {
                for (int r = bottom; r >= top; r--) result[idx++] = matrix[r][left];
                left++;
            }
        }
        return result;
    }
}