Spiral Matrix

MEDIUM✓ CHIP-TIMEDLC #54 — FULL STATEMENT ↗

The drill: Read a grid's values off in a clockwise spiral, starting from the top-left corner and winding inward — right across the top, down the right side, left across the bottom, up the left side, then repeat one ring smaller.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid of numbers arrives, not necessarily square, and the task is to read every one of its values off in a single order: clockwise, spiraling in from the top-left corner.

That reading walks right across the top row, down the right column, left across the bottom row, and up the left column, then repeats one ring further inward, until every cell has been visited exactly once.

The result is a flat list of the grid's values in that spiral order — nothing is skipped and nothing is revisited, even when the grid is taller than it is wide or the other way around.

EX 01

matrix = [[1]]

→ [1]

1X1, A SINGLE CELL

EX 02

matrix = [[1, 2], [3, 4]]

→ [1, 2, 4, 3]

SMALLEST SQUARE

EX 03

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

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

3X3, ONE FULL RING PLUS CENTER

grids run up to a few hundred rows and columns
cell values are integers, positive, negative, or zero
rows and columns need not match — rectangular grids are expected
every cell appears in the output exactly once

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A cell should never be visited twice, so the walk needs to know what's already been read. What's the simplest thing that remembers 'been here'?

HINT 2 THE STRUCTURE

The spiral isn't really tracking cells at all — it's tracking four shrinking edges. Once the top edge is fully read it never gets read again, so that boundary can just move inward for good.

HINT 3 ONE STEP FROM THE ANSWER

Keep top, bottom, left and right boundaries. Sweep the top row left-to-right and push top down, the right column top-to-bottom and pull right in, then (if a row remains) the bottom row right-to-left and pull bottom up, then (if a column remains) the left column bottom-to-top and push left in — repeat until the boundaries cross.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE SHRINKING RINGPATTERN · BOUNDARY SPIRALmatrix = [[1,2,3],[4,5,6],[7,8,9]]

STEP 1

Four boundaries frame the grid: top=0, bottom=2, left=0, right=2. Sweep each edge once, then pull it inward.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/spiral-matrix.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        result = []

        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

TIME O(ROWS·COLS)SPACE O(1) EXTRAPYTHON · RACE PACE · 26 LN

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rows, cols = len(matrix), len(matrix[0])
        visited = [[False] * cols for _ in range(rows)]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up
        result = []
        r = c = d = 0

        for _ in range(rows * cols):
            result.append(matrix[r][c])
            visited[r][c] = True
            nr, nc = r + directions[d][0], c + directions[d][1]
            if not (0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]):
                d = (d + 1) % 4   # blocked or off the grid — turn clockwise
                nr, nc = r + directions[d][0], c + directions[d][1]
            r, c = nr, nc

        return result

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)PYTHON · TRAINING PACE · 18 LN

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[] result = new int[rows * cols];
        int idx = 0;
        int top = 0, bottom = rows - 1;
        int left = 0, right = cols - 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;
    }
}

TIME O(ROWS·COLS)SPACE O(1) EXTRAJAVA · RACE PACE · 37 LN

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int[] result = new int[rows * cols];
        int r = 0, c = 0, d = 0;

        for (int i = 0; i < rows * cols; i++) {
            result[i] = matrix[r][c];
            visited[r][c] = true;
            int nr = r + directions[d][0];
            int nc = c + directions[d][1];
            if (!(nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc])) {
                d = (d + 1) % 4;
                nr = r + directions[d][0];
                nc = c + directions[d][1];
            }
            r = nr;
            c = nc;
        }

        return result;
    }
}

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)JAVA · TRAINING PACE · 25 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED