Spiral Matrix (LC 54)

Pattern: Layer-by-layer boundary traversal
Difficulty: Medium
Key Concept: Walk right → down → left → up along the current rectangle border, then shrink the rectangle; after each direction, check if the border collapsed to avoid duplicate visits on non-square middles.

Problem Statement

Given an m x n matrix, return all elements in spiral order (clockwise from the outside in).

Input: int[][] matrix
Output: List<Integer>

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

---

1. Algorithm & Pseudocode

Brute force

Simulate position (r,c) and direction vector; turn right on boundary or visited cell using a visited[][] — O(mn) time, O(mn) space for marks.

Optimal

Layer boundaries

top = 0, bottom = m-1, left = 0, right = n-1
while top <= bottom and left <= right:
  move along top row from left to right
  move along right col from top+1 to bottom
  if top < bottom: move along bottom from right-1 to left
  if left < right: move along left side from bottom-1 to top+1
  top++; bottom--; left++; right--

---

2. Step-by-Step Analysis (Beginner-Friendly)

• A spiral is just four straight segments per ring.
• After the top and right sides, the bottom and left may collapse to the same line (e.g., single row or single column left) — extra if guards prevent revisiting.
• Shrinking top/bottom/left/right moves you inward without a visited matrix.

---

3. The Dry Run

1  2  3  4
5  6  7  8
9 10 11 12

Ring	top,left → bottom,right	Order appended (segment by segment)
outer	(0,0)-(2,3)	1,2,3,4,8,12,11,10,9,5
inner	(1,1)-(1,2)	6,7

Full: [1,2,3,4,8,12,11,10,9,5,6,7].

Single row [[1,2,3]]: only top row + (skip bottom duplicate) + careful right column — guards ensure no 3,2,1 bounce.

---

4. Java Solution

Brute Force

import java.util.*;

class SolutionBrute {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean[][] vis = new boolean[m][n];
        List<Integer> res = new ArrayList<>();
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        int r = 0, c = 0, d = 0;

        for (int k = 0; k < m * n; k++) {
            res.add(matrix[r][c]);
            vis[r][c] = true;
            int nr = r + dirs[d][0], nc = c + dirs[d][1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || vis[nr][nc]) {
                d = (d + 1) % 4;
                nr = r + dirs[d][0];
                nc = c + dirs[d][1];
            }
            r = nr;
            c = nc;
        }
        return res;
    }
}

Time: O(mn), Space: O(mn) for vis.

Optimal

import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        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++) res.add(matrix[top][c]);
            for (int r = top + 1; r <= bottom; r++) res.add(matrix[r][right]);

            if (top < bottom) {
                for (int c = right - 1; c >= left; c--) res.add(matrix[bottom][c]);
            }
            if (left < right) {
                for (int r = bottom - 1; r > top; r--) res.add(matrix[r][left]);
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        return res;
    }
}

Time: O(mn), Space: O(1) excluding output list.

---

5. The “Java vs. Others” Edge

• ArrayList with known capacity m*n avoids reallocations: new ArrayList<>(m * n).
• Integer unboxing from matrix is automatic when adding to List<Integer>.
• Direction simulation brute is easier to bug on turns; layer method is the interview standard.

---

6. Complexity Summary

Approach	Time	Space	Notes
Simulated walk + visited	O(mn)	O(mn)	Works, more memory
Layer shrink	O(mn)	O(1) extra	Preferred

---

ASCII: Layers

+-------------+
| → → → → → ↓ |
| ↑         ↓ |
| ↑    *    ↓ |
| ↑         ↓ |
| ← ← ← ← ← ← |
+-------------+

Outer ring first, then inner rectangle (shrink top/bottom/left/right).