Skip to content

Volume ITechnology

4.28.2 — Spiral Matrix ​

LeetCode 54 · Medium

The problem ​

Return every element of the matrix in spiral order.

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

The matrix may be rectangular, not just square.

Restating the Problem: You are given a 2D matrix (rows and columns). Imagine you are walking through the matrix starting from the top-left, going right. When you hit an edge or a cell you've already visited, you turn right. You continue spiraling inward until you've visited every single cell. You need to return the elements in the order you visited them.

  • Constraints to note: The matrix dimensions m and n are up to 10. Again, small inputs, but the challenge is purely implementation.
  • Edge cases: A matrix with a single row ([1, 2, 3]), or a single column.

The brute force, and where it wastes work ​

There isn't a traditional "brute force vs optimized" trade-off here because the task requires visiting every cell exactly once, which inherently takes O(m \times n) time. Any correct simulation is essentially optimal in time complexity. However, a naive simulation might use a visited matrix of size m \times n (taking extra space) and turn right whenever it hits an edge or a visited cell. The boundary-shrinking method is much more space-efficient.

The pattern ​

Track four boundaries — top, bottom, left, right — and peel one edge at a time, shrinking the boundary you just consumed.

→ → →       walk the TOP row,    then top++
↑     ↓     walk the RIGHT col,  then right--
↑     ↓     walk the BOTTOM row, then bottom--
← ← ←       walk the LEFT col,   then left++

Repeat until the boundaries cross.

The difficulty is entirely in the boundary checks, not the idea. On a matrix with one row left, the bottom pass would walk the same row again backwards; on one column left, the left pass would repeat it. Both need guarding.

The two guards ​

After the top row and the right column are consumed, check before doing the other two:

  • Before the bottom row: only if top <= bottom. A single remaining row was already taken by the top pass.
  • Before the left column: only if left <= right. A single remaining column was already taken by the right pass.

Miss these and elements are emitted twice — and it only shows up on rectangular matrices or at the very centre, which is why this problem catches people who tested on a 3×3.

The solution ​

python
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:  # (1)
            return []

        top, bottom = 0, len(matrix) - 1  # (2)
        left, right = 0, len(matrix[0]) - 1  # (3)
        result = []

        while top <= bottom and left <= right:  # (4)
            for c in range(left, right + 1):          # (5) top row, left to right
                result.append(matrix[top][c])
            top += 1  # (6)

            for r in range(top, bottom + 1):          # (7) right column, top to bottom
                result.append(matrix[r][right])
            right -= 1  # (8)

            if top <= bottom:                         # (9) guard: rows remain
                for c in range(right, left - 1, -1):  # bottom row, right to left
                    result.append(matrix[bottom][c])
                bottom -= 1

            if left <= right:                         # (10) guard: columns remain
                for r in range(bottom, top - 1, -1):  # left column, bottom to top
                    result.append(matrix[r][left])
                left += 1

        return result
ts
function spiralOrder(matrix: number[][]): number[] {
  if (!matrix.length) return [];  // (1)

  let top = 0, bottom = matrix.length - 1;  // (2)
  let left = 0, right = matrix[0].length - 1;  // (3)
  const result: number[] = [];

  while (top <= bottom && left <= right) {  // (4)
    for (let c = left; c <= right; c++) result.push(matrix[top][c]);  // (5)
    top++;  // (6)

    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);  // (7)
    right--;  // (8)

    if (top <= bottom) {  // (9)
      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
      bottom--;
    }

    if (left <= right) {  // (10)
      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
      left++;
    }
  }

  return result;
}

Line by line ​

Keep four walls: the top row, bottom row, left column and right column that have not been read yet. Each lap reads the outer ring and moves every wall inward by one.

(1) An empty grid gives an empty list.

(2) The top and bottom unread rows.

(3) The left and right unread columns.

(4) Keep going while there is at least one unread cell, meaning the walls have not crossed.

(5) Read the top row, left to right, then

(6) move the top wall down. That row is done.

(7) Read the right column, top to bottom, then

(8) move the right wall left.

(9) Read the bottom row, right to left, only if a row is still left. In a grid with one row, step (5) already read it. Without this check, it would be read again backwards.

(10) Read the left column, bottom to top, only if a column is still left. Same reason, for a grid with one column.

Code Walkthrough:

  • Initialization: We establish four boundaries: top, bottom, left, and right, representing the unvisited core of the matrix. We also initialize a result array.
  • Loop Condition (top <= bottom and left <= right): We continue peeling layers as long as there is an unvisited core.
  • Peeling the Top: We loop from left to right along the top row. Once done, we increment top because that row is consumed.
  • Peeling the Right: We loop from top to bottom along the right column. Once done, we decrement right.
  • Peeling the Bottom (with Guard): If top <= bottom (meaning we still have rows left), we loop from right down to left along the bottom row, then decrement bottom.
  • Peeling the Left (with Guard): If left <= right (meaning columns remain), we loop from bottom up to top along the left column, then increment left.
  • Return: We return the result.

The boundary is shrunk immediately after each pass, so the next pass starts from the correct place. Doing all four passes and then adjusting all four boundaries produces overlaps.

The top and right passes need no guard, because the outer while has just confirmed both boundaries are valid.

The bottom and left passes do, because top++ and right-- may have crossed the boundaries in the meantime.

The 1×3 case ​

[[1,2,3]] — this is the input that exposes a missing guard.

  • top and bottom are both 0; left 0, right 2.
  • Top pass emits 1, 2, 3. top becomes 1.
  • Right pass: range(1, 1) is empty, so nothing. right becomes 1.
  • Bottom guard: top (1) <= bottom (0) is false → skipped. Without this guard it would emit 2, 1 again.
  • Left guard: left (0) <= right (1) is true, but the loop range(0, 0, -1) is empty.

Result [1,2,3] ✓. Test your solution on a single row and a single column before you say you are done.

Edge cases ​

  • One row. Read left to right. The checks in lines (9) and (10) stop it being read again.
  • One column. Read top to bottom.
  • A single cell. Read once.

Complexity ​

O(mn) time — every element is emitted once. O(1) extra space beyond the output.

  • Time Complexity: O(mn). We touch every element in the m \times n matrix exactly once.
  • Space Complexity: O(1). We only use four integer pointers (top, bottom, left, right) and loop variables. The result array is required for the output, so it's not counted as extra auxiliary space.

The direction-vector alternative ​

A different formulation: keep a direction vector and turn right whenever the next cell is out of bounds or already visited.

python
directions = [(0,1), (1,0), (0,-1), (-1,0)]      # right, down, left, up
d = 0
r = c = 0
for _ in range(rows * cols):
    result.append(matrix[r][c])
    matrix[r][c] = None                           # mark visited
    nr, nc = r + directions[d][0], c + directions[d][1]
    if not (0 <= nr < rows and 0 <= nc < cols) or matrix[nr][nc] is None:
        d = (d + 1) % 4                           # turn right
        nr, nc = r + directions[d][0], c + directions[d][1]
    r, c = nr, nc

(d + 1) % 4 cycling through four direction vectors is a genuinely useful idiom — it appears in robot-simulation problems and grid walks throughout this book.

It needs to mark visited cells, which either mutates the input or costs O(mn) space. The boundary version is cleaner here, but the direction-vector idea is the one that transfers.

Where this goes next ​

  • Spiral Matrix II — fill an n × n matrix with 1 to n² in spiral order. Same loop, writing instead of reading.
  • Spiral Matrix III — spiral outwards from a point, possibly leaving the grid. The direction-vector form is the natural fit, with the step length growing 1, 1, 2, 2, 3, 3, …
  • Rotate Image — a different traversal of the same grid. 4.28.1.

What the interviewer will push on ​

"Where are the guards and why?" Before the bottom and left passes, because a single remaining row or column has already been consumed.

"Test it on a 1×n matrix." Do this unprompted; it is the case the problem is designed around.

"Why shrink the boundary immediately?" So the next pass starts in the right place.

"What if the matrix is empty?" The early return, and note that matrix[0] would throw without it.

"Is there another formulation?" Direction vectors with (d + 1) % 4, at the cost of marking visited cells.

One thing to volunteer: walk the 1×3 case out loud before writing code. It shows you know where the bug lives rather than discovering it from a failing test.

Next: 4.28.3 Set Matrix Zeroes — in-place again, using the matrix itself as scratch space.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet