54. Spiral Matrix (Medium)

Problem

Return all elements of an m × n matrix in spiral order (clockwise, starting from the top-left).

Example

• matrix = [[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5]
• matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] → [1,2,3,4,8,12,11,10,9,5,6,7]

LeetCode 54 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Visited-set DFS / walking with direction

Walk, turning when you hit a visited cell or the boundary.

Python

def spiral_order(matrix):
    if not matrix:
        return []
    rows, cols = len(matrix), len(matrix[0])    # L1: O(1)
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    result = []
    visited = [[False] * cols for _ in range(rows)]  # L2: O(m·n)
    r = c = d = 0
    for _ in range(rows * cols):                # L3: loop m·n times
        result.append(matrix[r][c])             # L4: O(1) amortized
        visited[r][c] = True                    # L5: O(1)
        dr, dc = directions[d]
        nr, nc = r + dr, c + dc
        if not (0 <= nr < rows and 0 <= nc < cols and not visited[nr][nc]):
            d = (d + 1) % 4                     # L6: O(1) turn
            dr, dc = directions[d]
            nr, nc = r + dr, c + dc
        r, c = nr, nc
    return result

TypeScript

function spiralOrder(matrix: number[][]): number[] {
    if (!matrix.length) return [];
    const rows = matrix.length, cols = matrix[0].length;    // L1: O(1)
    const dirs = [[0,1],[1,0],[0,-1],[-1,0]];
    const result: number[] = [];
    const visited = Array.from({ length: rows }, () => new Array(cols).fill(false)); // L2: O(m·n)
    let r = 0, c = 0, d = 0;
    for (let i = 0; i < rows * cols; i++) {                 // L3: loop m·n times
        result.push(matrix[r][c]);                           // L4: O(1) amortized
        visited[r][c] = true;                               // L5: O(1)
        const [dr, dc] = dirs[d];
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) {
            d = (d + 1) % 4;                                // L6: O(1) turn
        }
        r += dirs[d][0];
        c += dirs[d][1];
    }
    return result;
}

Go

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 { return []int{} }
    rows, cols := len(matrix), len(matrix[0])               // L1: O(1)
    dirs := [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
    result := []int{}
    visited := make([][]bool, rows)
    for i := range visited { visited[i] = make([]bool, cols) }  // L2: O(m·n)
    r, c, d := 0, 0, 0
    for i := 0; i < rows*cols; i++ {                        // L3: loop m·n times
        result = append(result, matrix[r][c])               // L4: O(1) amortized
        visited[r][c] = true                                // L5: O(1)
        dr, dc := dirs[d][0], dirs[d][1]
        nr, nc := r+dr, c+dc
        if nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc] {
            d = (d + 1) % 4                                 // L6: O(1) turn
        }
        r += dirs[d][0]
        c += dirs[d][1]
    }
    return result
}

Swift

final class Solution {
    func spiralOrder(_ matrix: [[Int]]) -> [Int] {
        guard !matrix.isEmpty, !matrix[0].isEmpty else { return [] }
        let rows = matrix.count, columns = matrix[0].count
        let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        var seen = Array(repeating: Array(repeating: false, count: columns), count: rows)
        var row = 0, column = 0, direction = 0
        var result: [Int] = []
        for _ in 0..<(rows * columns) {
            result.append(matrix[row][column])
            seen[row][column] = true
            let nextRow = row + directions[direction].0
            let nextColumn = column + directions[direction].1
            if nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || seen[nextRow][nextColumn] {
                direction = (direction + 1) % directions.count
            }
            row += directions[direction].0
            column += directions[direction].1
        }
        return result
    }
}

Where the time goes, line by line

Variables: m = number of rows, n = number of columns.

Line	Per-call cost	Times executed	Contribution
L2 (init visited)	$O(1)$	m·n	$O(m·n)$
L3-L6 (walk loop)	$O(1)$	m·n	$O(m·n)$ ← dominates
L4 (append)	$O(1)$ amortized	m·n	$O(m·n)$

Every cell is visited exactly once.

Complexity

• Time: $O(m · n)$, driven by L3/L4/L5/L6 (one pass over all cells).
• Space: $O(m · n)$ visited array.

Approach 2: Shrinking boundaries (canonical, optimal space)

Maintain top, bottom, left, right. Walk each layer: right along top, down along right, left along bottom, up along left. After each side, shrink the boundary.

Python

def spiral_order(matrix):
    if not matrix:
        return []
    result = []
    top, bottom = 0, len(matrix) - 1           # L1: O(1)
    left, right = 0, len(matrix[0]) - 1        # L2: O(1)

    while top <= bottom and left <= right:      # L3: outer loop, min(m,n)/2 rounds
        for c in range(left, right + 1):        # L4: walk top row
            result.append(matrix[top][c])       # L5: O(1) amortized
        top += 1                                # L6: shrink
        for r in range(top, bottom + 1):        # L7: walk right col
            result.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1):# L8: walk bottom row (fixed typo)
                result.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1):# L9: walk left col (fixed typo)
                result.append(matrix[r][left])
            left += 1
    return result

TypeScript

function spiralOrder(matrix: number[][]): number[] {
    if (!matrix.length) return [];
    const result: number[] = [];
    let top = 0, bottom = matrix.length - 1;    // L1: O(1)
    let left = 0, right = matrix[0].length - 1; // L2: O(1)

    while (top <= bottom && left <= right) {     // L3: outer loop, min(m,n)/2 rounds
        for (let c = left; c <= right; c++)      // L4: walk top row
            result.push(matrix[top][c]);         // L5: O(1) amortized
        top++;                                   // L6: shrink
        for (let r = top; r <= bottom; r++)      // L7: walk right col
            result.push(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (let c = right; c >= left; c--)  // L8: walk bottom row
                result.push(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (let r = bottom; r >= top; r--)  // L9: walk left col
                result.push(matrix[r][left]);
            left++;
        }
    }
    return result;
}

Go

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 { return []int{} }
    result := []int{}
    top, bottom := 0, len(matrix)-1              // L1: O(1)
    left, right := 0, len(matrix[0])-1           // L2: O(1)

    for top <= bottom && left <= right {          // L3: outer loop, min(m,n)/2 rounds
        for c := left; c <= right; c++ {          // L4: walk top row
            result = append(result, matrix[top][c])  // L5: O(1) amortized
        }
        top++                                     // L6: shrink
        for r := top; r <= bottom; r++ {          // L7: walk right col
            result = append(result, matrix[r][right])
        }
        right--
        if top <= bottom {
            for c := right; c >= left; c-- {      // L8: walk bottom row
                result = append(result, matrix[bottom][c])
            }
            bottom--
        }
        if left <= right {
            for r := bottom; r >= top; r-- {      // L9: walk left col
                result = append(result, matrix[r][left])
            }
            left++
        }
    }
    return result
}

Swift

final class Solution {
    func spiralOrder(_ matrix: [[Int]]) -> [Int] {
        guard !matrix.isEmpty, !matrix[0].isEmpty else { return [] }
        var top = 0, bottom = matrix.count - 1
        var left = 0, right = matrix[0].count - 1
        var result: [Int] = []
        while top <= bottom && left <= right {
            for column in left...right { result.append(matrix[top][column]) }
            top += 1
            if top > bottom { break }
            for row in top...bottom { result.append(matrix[row][right]) }
            right -= 1
            if left > right { break }
            for column in stride(from: right, through: left, by: -1) { result.append(matrix[bottom][column]) }
            bottom -= 1
            if top > bottom { break }
            for row in stride(from: bottom, through: top, by: -1) { result.append(matrix[row][left]) }
            left += 1
        }
        return result
    }
}

Where the time goes, line by line

Variables: m = number of rows, n = number of columns.

Line	Per-call cost	Times executed	Contribution
L3 (outer loop)	$O(1)$	min(m,n)/2 rounds	$O(min(m,n)$)
L4-L9 (four-side walks)	$O(1)$ per cell	m·n total	$O(m·n)$ ← dominates

All four side-walks together visit each cell exactly once across all rounds.

Complexity

• Time: $O(m · n)$, driven by L4-L9 (visiting every cell in every layer).
• Space: $O(1)$ extra.

The if top <= bottom / if left <= right guards handle the last single row or column in non-square matrices.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Recursive peel + rotate

Append the top row, then rotate the rest of the matrix 90° counterclockwise (each column becomes a row, then reverse the row order). Recurse on the rotated remainder.

Python

def spiral_order(matrix):
    if not matrix or not matrix[0]:
        return []
    result = list(matrix[0])
    rest = matrix[1:]
    if not rest:
        return result
    # Rotate rest 90° CCW: take its columns, reverse the order
    rotated = [list(col) for col in list(zip(*rest))[::-1]]
    return result + spiral_order(rotated)

Swift

final class Solution {
    func spiralOrder(_ matrix: [[Int]]) -> [Int] {
        guard !matrix.isEmpty else { return [] }
        return matrix[0] + spiralOrder(rotateCounterclockwise(Array(matrix.dropFirst())))
    }

    private func rotateCounterclockwise(_ matrix: [[Int]]) -> [[Int]] {
        guard !matrix.isEmpty, !matrix[0].isEmpty else { return [] }
        return stride(from: matrix[0].count - 1, through: 0, by: -1).map { column in
            matrix.map { row in row[column] }
        }
    }
}

The rotation lines up the next clockwise side as the new “top row,” so the same peel-the-top-row rule produces the spiral. Elegant but allocates rotated matrices at each level.

Complexity

• Time: $O(m · n)$.
• Space: $O(min(m, n)$) recursion.

Summary

Approach	Time	Space
Visited + direction	$O(m · n)$	$O(m · n)$
Shrinking boundaries	$O(m · n)$	$O(1)$
Recursive peel	$O(m · n)$	$O(min(m, n)$)

The boundary-shrink template works for Spiral Matrix II (fill), III (starting offset), and IV (multiple passes).

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_054.py and run.
# Uses the canonical implementation (Approach 2: shrinking boundaries).

def spiral_order(matrix):
    if not matrix:
        return []
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    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

def _run_tests():
    assert spiral_order([[1,2,3],[4,5,6],[7,8,9]]) == [1,2,3,6,9,8,7,4,5]
    assert spiral_order([[1,2,3,4],[5,6,7,8],[9,10,11,12]]) == [1,2,3,4,8,12,11,10,9,5,6,7]
    assert spiral_order([[1]]) == [1]                      # 1x1
    assert spiral_order([[1,2],[3,4]]) == [1,2,4,3]        # 2x2
    assert spiral_order([[1],[2],[3]]) == [1,2,3]          # single column
    assert spiral_order([[1,2,3]]) == [1,2,3]              # single row
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function spiralOrder(matrix: number[][]): number[] {
    if (!matrix.length) return [];
    const result: number[] = [];
    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;
    while (top <= bottom && left <= right) {
        for (let c = left; c <= right; c++) result.push(matrix[top][c]);
        top++;
        for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);
        right--;
        if (top <= bottom) {
            for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);
            bottom--;
        }
        if (left <= right) {
            for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);
            left++;
        }
    }
    return result;
}

console.assert(JSON.stringify(spiralOrder([[1,2,3],[4,5,6],[7,8,9]])) === JSON.stringify([1,2,3,6,9,8,7,4,5]));
console.assert(JSON.stringify(spiralOrder([[1,2,3,4],[5,6,7,8],[9,10,11,12]])) === JSON.stringify([1,2,3,4,8,12,11,10,9,5,6,7]));
console.assert(JSON.stringify(spiralOrder([[1]])) === JSON.stringify([1]));
console.assert(JSON.stringify(spiralOrder([[1,2],[3,4]])) === JSON.stringify([1,2,4,3]));
console.assert(JSON.stringify(spiralOrder([[1],[2],[3]])) === JSON.stringify([1,2,3]));
console.assert(JSON.stringify(spiralOrder([[1,2,3]])) === JSON.stringify([1,2,3]));
console.log('all tests pass');

Related data structures

• Arrays, 2D matrix traversal

Related concepts

• Simulation, the explicit state model for executing rules exactly while keeping cases organized.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.