Spiral Matrix

The problem

You are given a grid matrix with m rows and n columns (rows and columns in the code). Return all its values in spiral order: start at the top left, go right along the top row, down the right column, left along the bottom row, up the left column, and keep circling inward until every value is taken.

Example 1

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

Output: [7, 1, 4, 9, 6, 11, 10, 0, 5, 3, 8, 2]

The outer ring gives 7, 1, 4, 9, 6, 11, 10, 0, 5, 3. The inner part, 8 and 2, comes last.

	c0	c1	c2	c3
r0	7	1	4	9
r1	3	8	2	6
r2	5	0	10	11

spiral

71496111005382

Example 2

Input: matrix = [[4, 6], [8, 2]]

Output: [4, 6, 2, 8]

Right along the top, down, then left along the bottom.

Example 3

Input: matrix = [[5], [6], [7]]

Output: [5, 6, 7]

One column: the spiral just goes down.

Constraints

• 1 ≤ m, n ≤ 10
• −100 ≤ matrix[i][j] ≤ 100

Clarifying questions

Is the grid square?

Not always. m and n can differ, and a single row or column is allowed.

Which way does it turn?

Clockwise: right, down, left, up, and again.

May we change the grid?

Better not. Marking cells inside it would work, but it changes the caller's data.

What do we return?

A flat list of all m × n values.

Spot the pattern

This is a grid walk with a fixed route, so the work is pure bookkeeping. The route peels the grid like an onion: one ring, then the ring inside it. Four numbers, the walls top, bottom, left and right, describe what is left. Each side taken moves one wall in.

Solutions

Walk and turnO(m·n), O(m·n) spaceShrinking wallsO(m·n), O(1) space

Show all

This problem has two approaches. Both take each cell once, and the second drops the visited grid.

Walk and turn O(m·n), O(m·n) space

The idea

Walk the grid like a snake. Keep a direction: right, down, left or up. Take the current cell and mark it as seen. If the next cell ahead is off the grid or already seen, turn right. Repeat m × n times.

It is a direct copy of the route. The cost is a second grid of seen flags.

Walkthrough

	c0	c1	c2	c3
r0	7	1	4	9
r1	3	8	2	6
r2	5	0	10	11

result

empty

1. seen = [[False] * columns for _ in range(rows)]
2. i = j = direction = 0 # direction: right, down, left, up
3. for _ in range(rows * columns):
4. result.append(matrix[i][j]); seen[i][j] = True
5. next_row, next_column = i + row_step[direction], j + column_step[direction]
6. if off the grid or seen[next_row][next_column]:
7. direction = (direction + 1) % 4 # turn right
8. next_row, next_column = i + row_step[direction], j + column_step[direction]
9. i, j = next_row, next_column
10. return result

Walk like a snake: go right until the next cell is off the grid or already seen, then turn right. A seen grid remembers where we have been.

← BackStep →Play1 / 14

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Walk and turn: go straight until the next cell is off the grid or seen, then
    // turn right. Each cell once: O(m * n) time, and the seen grid is O(m * n) memory.
    public java.util.List<Integer> spiralOrder(int[][] matrix) {
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] seen = new boolean[rows][columns];
        // Right, down, left, up: turning right is the next index.
        int[] rowStep = { 0, 1, 0, -1 }, columnStep = { 1, 0, -1, 0 };
        int i = 0, j = 0, direction = 0;
        java.util.List<Integer> result = new java.util.ArrayList<>();
        for (int step = 0; step < rows * columns; step++) {
            result.add(matrix[i][j]);
            seen[i][j] = true;
            int nextRow = i + rowStep[direction], nextColumn = j + columnStep[direction];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns
                || seen[nextRow][nextColumn]) {
                direction = (direction + 1) % 4;
                nextRow = i + rowStep[direction];
                nextColumn = j + columnStep[direction];
            }
            i = nextRow;
            j = nextColumn;
        }
        return result;
    }
}

Big O

Time O(m·n)Space O(m·n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop takes one cell, checks the cell ahead and maybe turns. That is 1 step. There is one loop, and it runs once per cell.

   1. seen = [[False] * columns for _ in range(rows)]
   2. i = j = direction = 0 # direction: right, down, left, up
   3. for _ in range(rows * columns):
   4. result.append(matrix[i][j]); seen[i][j] = True
   5. next_row, next_column = i + row_step[direction], j + column_step[direction]
   6. if off the grid or seen[next_row][next_column]:
   7. direction = (direction + 1) % 4 # turn right
   8. next_row, next_column = i + row_step[direction], j + column_step[direction]
   9. i, j = next_row, next_column
   10. return result

2. 2 Count the runs on Example 1

   Example 1 is 3 × 4, so 12 cells. The loop takes one per run.

   12 runs.

   run	1	2	3	4	5	6	7	8	9	10	11	12
   takes	7	1	4	9	6	11	10	0	5	3	8	2

3. 3 Write the count for any n

   m × n runs

   Check it with Example 1: 3 × 4 = 12.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already m·n, which is also the size of the answer.

   So the time is O(m·n).

5. S Space: count the extra memory the same way

   The seen grid holds one flag per cell, so m × n flags. The space is O(m·n), not counting the output list.

   seen (m × n flags)ijdirection

Shrinking walls O(m·n), O(1) space

The idea

Keep four walls: top, bottom, left and right. Everything between them is not yet taken. Then go round:

1. Take the top row from left to right. Move top down.
2. Take the right column from top to bottom. Move right left.
3. If a row is still left, take the bottom row from right to left. Move bottom up.
4. If a column is still left, take the left column from bottom to top. Move left right.

Stop when the walls cross. The two if checks matter when only one row or one column is left: without them, the same cells would be taken twice.

The invariant: the cells between the walls are exactly the cells not yet taken.

Walkthrough

	c0	c1	c2	c3
r0	7	1	4	9
r1	3	8	2	6
r2	5	0	10	11

result

empty

1. top, bottom, left, right = 0, rows - 1, 0, columns - 1
2. while top <= bottom and left <= right:
3. for j in range(left, right + 1): result.append(matrix[top][j])
4. top += 1
5. for i in range(top, bottom + 1): result.append(matrix[i][right])
6. right -= 1
7. if top <= bottom:
8. for j in range(right, left - 1, -1): result.append(matrix[bottom][j])
9. bottom -= 1
10. if left <= right:
11. for i in range(bottom, top - 1, -1): result.append(matrix[i][left])
12. left += 1
13. return result

Four walls mark the part not yet taken: top, bottom, left and right. Take one side, then move that wall in by one.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Shrinking walls: take the top row, right column, bottom row and left column,
    // moving each wall in after. Each cell once: O(m * n) time, O(1) extra memory.
    public java.util.List<Integer> spiralOrder(int[][] matrix) {
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
        java.util.List<Integer> result = new java.util.ArrayList<>();
        // The cells between the walls are exactly the ones not taken yet.
        while (top <= bottom && left <= right) {
            for (int j = left; j <= right; j++) result.add(matrix[top][j]);
            top++;
            for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
            right--;
            // With one row left, the bottom row is the top row we just took.
            if (top <= bottom) {
                for (int j = right; j >= left; j--) result.add(matrix[bottom][j]);
                bottom--;
            }
            // With one column left, the left column is the right one we just took.
            if (left <= right) {
                for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
                left++;
            }
        }
        return result;
    }
}

Big O

Time O(m·n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The four inner loops each take one cell per run. That is 1 step. The while loop goes once per ring. The question is how many cells all the inner loops take together.

   1. top, bottom, left, right = 0, rows - 1, 0, columns - 1
   2. while top <= bottom and left <= right:
   3. for j in range(left, right + 1): result.append(matrix[top][j])
   4. top += 1
   5. for i in range(top, bottom + 1): result.append(matrix[i][right])
   6. right -= 1
   7. if top <= bottom:
   8. for j in range(right, left - 1, -1): result.append(matrix[bottom][j])
   9. bottom -= 1
   10. if left <= right:
   11. for i in range(bottom, top - 1, -1): result.append(matrix[i][left])
   12. left += 1
   13. return result

2. 2 Count the runs on Example 1

   Example 1 is 3 × 4. The sides take 4, 2, 3, 1 and then 2 cells.

   4 + 2 + 3 + 1 + 2 = 12 takes.

   side	top row 0	right column 3	bottom row 2	left column 0	top row 1
   cells	4	2	3	1	2

   total

   4 + 2 + 3 + 1 + 2 = 12

3. 3 Write the count for any n

   Every cell is taken exactly once, because each side moves its wall past the cells it took:

   m × n takes, plus a few wall moves per ring

   Check it with Example 1: 12 takes for 12 cells.

4. 4 Keep only the part that grows fastest

   Drop the wall moves. There are at most about min(m, n) / 2 rings, far fewer than m·n cells. What is left is m·n.

   So the time is O(m·n).

5. S Space: count the extra memory the same way

   The walls are four numbers, for any size of grid. The space is O(1), not counting the output list.

   topbottomleftright

Common mistake

Taking the last row or column twice

On a grid with one row left, step 1 takes it left to right. Without the top <= bottom check, step 3 takes the same row again, right to left. Check the walls before the bottom row and the left column.

Tested at the limits

2,000 random grids from 1 x 1 to 6 x 6, with single rows, single columns, tall grids and wide grids. Walk and turn and shrinking walls gave the same answer every time.

Largest inputs	Result
Every shape up to 10 x 10 (the most allowed), 100 grids in all. Both approaches.	The right order on every one.
A 10 x 10 grid. Shrinking walls.	Under 0.001 s, and about 0.001 MB of extra memory, almost all of it the answer of 100 numbers. The walls are four numbers.