A picker walks a rectangular shelf clockwise from the top-left, peels the outer ring, then the next ring, until the last cell. The first simulator painted a visited[][] the size of the warehouse map and turned right whenever the next step was out of bounds or already painted. Correct. The map was the memory bill. The four walls of the remaining rectangle already know which cells have not been walked.

Spiral Matrix asks for the cells in clockwise spiral order. An array of rows is the shelf. You do not need a second grid of booleans. You need top, bottom, left, and right, and you close them after each side.

The problem

Given an m × n int[][] matrix, return a list of every value in clockwise spiral order, starting at the top-left cell. Walk right, then down, then left, then up, then inward.

9 1 4
2 8 5
7 3 6

top=0 bottom=2 left=0 right=2
top  L→R:  9, 1, 4     top → 1
right T→B: 5, 6        right → 1
bottom R→L: 3, 7       bottom → 1
left  B→T: 2           left → 1

top=1 bottom=1 left=1 right=1
top  L→R:  8           top → 2
right empty; bottom and left skipped (bounds crossed)

result: 9, 1, 4, 5, 6, 3, 7, 2, 8

[9, 1, 4]  →  9, 1, 4     one row: bottom and left walks are skipped

Note: A one-row or one-column matrix is still a spiral: the remaining strip is walked once. The extra if after shrinking top / right is what stops a second pass over that strip.

Paint a visited matrix and turn right

Start at (0, 0), facing right. After each cell, try the next step in the current direction. If that step is off the board or already visited, rotate clockwise and step. Stop after m * n cells. Correct. Extra O(mn) booleans.

List<Integer> spiralVisited(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    boolean[][] seen = new boolean[m][n];
    int[] dr = {0, 1, 0, -1};
    int[] dc = {1, 0, -1, 0};
    List<Integer> out = new ArrayList<>();
    int r = 0;
    int c = 0;
    int dir = 0;
    for (int k = 0; k < m * n; k++) {
        out.add(matrix[r][c]);
        seen[r][c] = true;
        int nr = r + dr[dir];
        int nc = c + dc[dir];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) {
            dir = (dir + 1) % 4;
            nr = r + dr[dir];
            nc = c + dc[dir];
        }
        r = nr;
        c = nc;
    }
    return out;
}

The direction arrays are the honest simulation. The visit grid is the part you can drop: the four walls already know which cells remain.

Shrink the four walls

Hold top, bottom, left, right. Walk the top side left to right, then bump top. Walk the right side top to bottom, then bump right. If a row remains, walk the bottom side right to left and bump bottom. If a column remains, walk the left side bottom to top and bump left. Repeat while top <= bottom and left <= right.

The Java is that peel:

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

Time is O(mn) — each cell is written once. Extra space is O(1) besides the output list; four integers, no visit grid.

Note: Guard the bottom and left walks. After top++ and right--, a single remaining row or column has already been consumed by the first two sides. Without the ifs you walk it again, backwards.

What interviewers usually poke next

  • 1 × n and n × 1. Walk the 3×3 first, then a [9, 1, 4] row and a column [9, 2, 7]. The guards are the whole point of those cases.
  • Counterclockwise / start elsewhere. Same four walls, different side order. Do not reuse this clockwise peel without renaming the first walk.
  • Generate a spiral into an empty matrix. Inverse problem: write 1 … n² by the same bounds. Same walls, write instead of read.
  • Empty or null. The prompt usually promises m, n >= 1. Production would reject a null; at the board, ask.

You are done with this problem when you can peel the 3×3 on a whiteboard with four bounds, and you can say out loud why a visit grid is the honest brute and why the bottom and left sides sit behind an if.