Spiral Matrix

Q: What is the time and space complexity of Spiral Matrix?

Both approaches read each value once, so the time is O(m × n) , and no solution can do better because the answer contains every value. Peeling layers with four bounds uses O(1) extra memory besides the answer. The turn-when-blocked walk uses an O(m × n) grid to remember which cells it has read.

MediumMath and simulation Arrays and strings

+10

You get a matrix of integers with m rows and n columns, given as a list of rows. Return all of its values in spiral order.

Start at the top-left corner and go right along the top row, then down the right column, left along the bottom row and up the left column. Keep circling inward clockwise until every value has been read exactly once.

Function

spiralOrder(matrix: integer-2d-array) → integer-array

matrixinteger-2d-array: the grid of integers, as a list of rows of equal length
Returnsinteger-array: every value of the matrix in clockwise spiral order, starting at the top-left corner

Constraints

1 ≤ m, n ≤ 80, where m = matrix.length and n = matrix[i].length
Every row has the same length n.
-100 ≤ matrix[i][j] ≤ 100

Examples

Input: matrix = [[1, 2, 3], [10, 11, 4], [9, 12, 5], [8, 7, 6]]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Explanation: The values count up along the spiral. The outer ring reads 1, 2, 3 along the top, 4, 5, 6 down the right, 7, 8 back along the bottom and 9, 10 up the left. The inner layer is a single column, read once from top to bottom: 11, 12.

Input: matrix = [[7, 1, 5, 3], [2, 9, -4, 6], [8, 0, 4, -1]]
Output: [7, 1, 5, 3, 6, -1, 4, 0, 8, 2, 9, -4]
Explanation: The outer ring gives 7, 1, 5, 3, then 6, -1 down the right side, 4, 0, 8 back along the bottom and 2 up the left. What remains is the single row 9, -4, read once from left to right.

+15 hidden tests on Submit

Follow-up

Can you return the values in counterclockwise order instead, starting at the top-left corner and going down the left column first?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

There is no clever math here; the problem is bookkeeping, and the bookkeeping is where solutions break. Each corner has to be read once, not twice, and the innermost layer can be a single row or a single column, where a full lap would walk over the same values again. You can walk like a robot that turns right whenever it is blocked and remembers which cells it has read. Or you can peel the matrix one ring at a time with four shrinking bounds, which needs no extra memory.

Walk and turn right when blocked

Intuition

Picture a walker on the top-left cell, facing right. It reads the cell it stands on, then tries to step forward. If that step would leave the matrix or land on a cell it has already read, it turns right (right, down, left, up, then right again) and steps that way instead. That rule draws the spiral: the edges of the matrix stop the first lap, and the cells read so far act as walls for every lap after it.

Keep the direction as an index d into two small arrays, dr = [0, 1, 0, -1] and dc = [1, 0, -1, 0], so a right turn is d = (d+1) % 4. Keep a boolean grid seen the size of the matrix. In the first example the walker reads 1, 2, 3, meets the right edge and turns down for 4, 5, 6, turns left for 7, 8 and up for 9, 10. Above 10 sits the 1, already read, so it turns right onto 11. Right of 11 is the 4, read, so it turns down onto 12.

Run the loop exactly m × n times, once per cell, and you never need to detect the end. After the last read the walker may face a wall, but it never steps again. Every cell is read once, so the time is O(m × n). The seen grid costs O(m × n) extra memory, which the next approach removes.

Algorithm

Start at row 0, column 0, facing right, with an all false seen grid.
Repeat m × n times: append the current value and mark its cell as seen.
Compute the next cell in the current direction. If it is outside the matrix or already seen, turn right and compute it again.
Move to that cell.
Return the values in the order you appended them.

def spiralOrder(matrix):
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    # Directions in clockwise order: right, down, left, up.
    dr = [0, 1, 0, -1]
    dc = [1, 0, -1, 0]
    r = c = d = 0
    result = []
    for _ in range(rows * cols):
        result.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + dr[d], c + dc[d]
        # Blocked by the edge or by a cell already read: turn right.
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
    return result

Peel the layers with four bounds

Intuition

The spiral is a set of nested rings. Describe the current ring with four bounds: rows top to bottom, columns left to right. One lap reads the top row from left to right, the right column from top+1 down to bottom, the bottom row from right-1 back to left, and the left column from bottom-1 up to top+1. Each side starts one cell past the end of the side before it, so every corner is read exactly once. Then move all four bounds one step inward and repeat while top ≤ bottom and left ≤ right.

The trap is a ring that is only one row or one column thick, where the way back runs over cells already read. In the second example, after the outer ring the bounds are top = bottom = 1, left = 1 and right = 2: the single row 9, -4. The top row reads both values and the right column has nothing below top. But the bottom row is that same row, and walking it back would add 9 a second time. So walk the bottom row and the left column only when top < bottom and left < right. The third example is the mirror case: in the single column 4, 1, 7, walking back up the left column would read 1 again.

Every value is read once, so the time is O(m × n), the least possible since the answer holds every value. Beyond the answer, the memory is four integers.

Algorithm

Set top = 0, bottom = m-1, left = 0, right = n-1.
While top ≤ bottom and left ≤ right, read the top row from left to right and the right column from top+1 to bottom.
If top < bottom and left < right, read the bottom row from right-1 to left and the left column from bottom-1 to top+1.
Add one to top and left, subtract one from bottom and right.
Return the values in the order you read them.

def spiralOrder(matrix):
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    result = []
    while top <= bottom and left <= right:
        # Top row, left to right, then right column, top to bottom.
        for c in range(left, right + 1):
            result.append(matrix[top][c])
        for r in range(top + 1, bottom + 1):
            result.append(matrix[r][right])
        # A layer one row or one column thick has no way back:
        # walking back would read the same cells again.
        if top < bottom and left < right:
            # Bottom row, right to left, then left column, bottom to top.
            for c in range(right - 1, left - 1, -1):
                result.append(matrix[bottom][c])
            for r in range(bottom - 1, top, -1):
                result.append(matrix[r][left])
        # Step in to the next layer.
        top += 1
        bottom -= 1
        left += 1
        right -= 1
    return result

Pitfalls and edge cases

The loops are short, so the bugs sit at the corners and in the last layer.

Reading the last layer twice when it is one row or one column. Without the top < bottom and left < right check, the second example ends 9, -4, 9 and the third reads 4, 1, 7, 1.
Reading a corner twice. If every side runs from its own first cell to its own last cell, each corner is read by two sides. Start each side one cell after the previous side ended.
Looping while top < bottom instead of top ≤ bottom. That stops before the middle of an odd square: in a 3 × 3 matrix the center value is never read.
Mixing up rows and columns on a matrix that is not square. Using matrix.length for both bounds works on every square test and fails on a 3 × 4 one.
Forgetting the thin inputs: one row, one column, one cell. Each is a single layer that never reaches the bottom row or the left column.
In R, a:b counts down when a > b, so an empty range such as 3:2 gives 3, 2 instead of nothing; guard it or use seq_len. In Lua and R, rows and columns start at 1.

Frequently asked questions4

What is the time and space complexity of Spiral Matrix?

Both approaches read each value once, so the time is O(m × n), and no solution can do better because the answer contains every value. Peeling layers with four bounds uses O(1) extra memory besides the answer. The turn-when-blocked walk uses an O(m × n) grid to remember which cells it has read.

How do you avoid reading a value twice in a spiral traversal?

Two places cause repeats. At the corners, start each side one cell after the previous side ended, so each corner belongs to one side only. In the last layer, read the bottom row and the left column only when the layer has more than one row and more than one column, since otherwise the way back runs over cells you have already read.

How do you fill a matrix in spiral order instead of reading one?

Use the same four bounds and the same four sides, but write instead of read. Keep a counter that starts at 1 and store it into each cell as you pass, adding one each time. For an n × n matrix the counter ends at n², and the first example above is what that produces for a 4 × 3 grid.

Why does turning right when blocked produce a spiral?

On the first lap the walker turns at the four edges of the matrix. On every later lap the cells read before act as the walls, so each lap turns one cell before the ring it walked last time. That keeps every lap inside the previous one, which is the spiral. The walker never needs to know which layer it is in, only whether the next cell is free.

Python

def spiralOrder(matrix):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

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

Expected

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