Spiral Matrix

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

The time is O(m × n) , since each value is read once and the answer holds every value. Peeling layers with four bounds uses O(1) extra memory. The turn-when-blocked walk needs an O(m × n) grid of seen cells.

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

Start each side one cell after the previous side ended, so each corner belongs to one side. In a layer one row or one column thick, skip the bottom row and the left column.

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

Use the same four bounds and sides, but write instead of read. Store a counter that starts at 1 into each cell as you pass, adding one each time. For an n × n matrix the counter ends at n² .

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 to 10, and the inner layer is a single column, read once: 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, 6, -1, 4, 0, 8, 2. What remains is the single row 9, -4, read once from left to right.

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

The problem is bookkeeping. Each corner must be read once, and the innermost layer can be a single row or column, where a full lap would reread values. You can walk and turn right whenever you are blocked, or peel the matrix one ring at a time with four shrinking bounds and no extra memory.

Walk and turn right when blocked

Intuition

A walker starts on the top-left cell, facing right, and reads each cell it stands on. If the next step would leave the matrix or land on a cell already read, it turns right. The edges stop the first lap, and the cells read so far act as walls for every lap after it, so each lap stays inside the last one.

In the first example the walker reads 1 to 10 around the edge. Above 10 sits the 1, already read, so it turns onto 11, then down onto 12. Run the loop exactly m × n times and you never need to detect the end. The time is O(m × n), and the seen grid costs O(m × n) extra memory.

Algorithm

Start at row 0, column 0, direction index d = 0, with dr = [0, 1, 0, -1], dc = [1, 0, -1, 0] and an all false seen grid.
Repeat m × n times: append the current value and mark its cell as seen.
If the next cell is outside the matrix or seen, turn with d = (d+1) % 4.
Move one step in direction d.

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

Describe the current ring with rows top to bottom and columns left to right. Each side of a lap starts one cell past the end of the side before it, so every corner is read once. Then move all four bounds inward.

A ring one row or one column thick breaks the lap. In the second example the last ring is the row 9, -4: the top row reads both values, and walking the bottom row back would add 9 again. In the third example, walking back up the single column would reread 1. So walk the bottom row and the left column only when top < bottom and left < right.

Every value is read once, so the time is O(m × n), and the extra 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.

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

Skipping the top < bottom and left < right check. The second example then ends 9, -4, 9 and the third reads 4, 1, 7, 1.
Running every side from its own first cell to its own last cell. Each corner is then read twice.
Looping while top < bottom. In a 3 × 3 matrix the center value is never read.
Using matrix.length for both bounds. It passes every square input and fails on a 3 × 4 one.
In R, 3:2 gives 3, 2 instead of an empty range; guard it or use seq_len. In Lua and R, indexes start at 1.

Frequently asked questions3

What is the time and space complexity of Spiral Matrix?

The time is O(m × n), since each value is read once and the answer holds every value. Peeling layers with four bounds uses O(1) extra memory. The turn-when-blocked walk needs an O(m × n) grid of seen cells.

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

Start each side one cell after the previous side ended, so each corner belongs to one side. In a layer one row or one column thick, skip the bottom row and the left column.

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

Use the same four bounds and sides, but write instead of read. Store a counter that starts at 1 into each cell as you pass, adding one each time. For an n × n matrix the counter ends at n².

def spiralOrder(matrix):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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