Spiral Matrix

The problem

matrix is a table of integers, given as a list of rows that all have the same length. Return its values as one list in clockwise spiral order: start at the top left cell and go right along the top row, down the right column, left along the bottom row and up the left column. Then go round the cells not yet taken in the same way, again and again, until every value has been taken exactly once. The table need not be square. It may also have no rows, or rows with nothing in them: then return an empty list.

What to write

function solve(matrix: number[][]): number[]

Input
matrix = [[1,2,3],[4,5,6],[7,8,9]]

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

Input
matrix = [[1,2,3],[4,5,6]]

Output
[1,2,3,6,5,4]

Constraints

Rectangular integer matrix up to 50 × 50; empty matrices allowed.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The matrix has at most 50 rows and 50 columns, so at most 2,500 cells, and every cell has to be read once anyway. Speed is not the problem. The care goes into the turns, and into the odd shapes the tests include: a single row, a single column, and a matrix with no cells at all.

2. Hint 2: Ask a smaller question

   Trace the spiral with your finger on a grid of 4 rows and 5 columns. Stop after one full trip around the outside, when you are next to the cell where you started. What shape do the cells you have not touched make?

3. Hint 3: Name the pattern

   After every trip around, the unread cells form a smaller rectangle. So four numbers describe what is left: its top row, bottom row, left column and right column. You need no copy of the matrix and no record of the cells you have read. Visiting every cell in a planned order, steered by a few position numbers, is matrix traversal. Read the lesson on matrix traversal.

4. Hint 4: State the invariant

   The unread cells are always exactly the rectangle from the top edge to the bottom edge and from the left edge to the right edge. Each time you finish reading one side of it, move that edge one step inward. When the top edge passes the bottom edge, or the left passes the right, nothing is unread.

5. Hint 5: Sketch the pseudocode

   top = left = 0, bottom = last row, right = last column (-1 if none). While top <= bottom and left <= right, read four sides, moving each edge inward once its side is read: row top rightward; column right downward; if top <= bottom, row bottom leftward; if left <= right, column left upward. Return the values read.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Traverse the top edge, right edge, bottom edge, and left edge. Shrink each boundary after traversal and check that another edge still exists.

The slow way

Walk the path one cell at a time. Keep a direction and a second grid of marks, one mark per cell read, and turn right whenever the next cell is off the matrix or already marked. It gives the right answer, but it needs a whole extra grid, and it has to test for a turn before every single step.

The insight

After one trip around the outside, the cells still unread form a smaller rectangle. So you never have to mark cells: four numbers, the first and last unread row and the first and last unread column, say exactly what is left. Each side you read moves one of those four numbers inward.

Step by step

1. Start an empty answer and mark the four edges of the unread part. Nothing is read yet, so counting from 0 the edges are row 0, the last row, column 0 and the last column. A matrix with no rows has no first row to measure: its right edge becomes -1.
2. Go round while the unread part still has a row and a column. Once the top edge is past the bottom edge, or the left edge past the right, no cell lies between them. That is also why a matrix with no cells returns an empty list at once.
3. Read the top row from left to right, then move the top edge down. The loop test promises that this row exists and has cells between the left and right edges. Moving the edge at once takes the whole row, corner cells included, out of the unread part.
4. Read the right column downward, then move the right edge inward. The top edge has already moved, so the column starts one row lower and the top right corner is not read twice. If no row is left, there is nothing to read here.
5. If a row is left, read the bottom row leftward and move its edge up. Reading the top row may have used up the last row. Without this check, a single row would be read again, backwards, except for its last cell.
6. If a column is left, read the left column upward and move its edge in. Reading the right column may have used up the last column. Without this check, a single column of three or more rows would have its middle cells read again on the way up.
7. Return the values in the order they were read. Every cell was read exactly once, in spiral order, so the list is the answer. For a matrix with no cells the list is still empty.

The same numbered steps are the comments in each solution.

function solve(matrix) {
  // 1. Start an empty answer and mark the four edges of the unread part
  const out = [];
  let top = 0,
    bottom = matrix.length - 1,
    left = 0,
    right = (matrix[0]?.length || 0) - 1;
  // 2. Go round while the unread part still has a row and a column
  while (top <= bottom && left <= right) {
    // 3. Read the top row from left to right, then move the top edge down
    for (let c = left; c <= right; c++) out.push(matrix[top][c]);
    top++;
    // 4. Read the right column downward, then move the right edge inward
    for (let r = top; r <= bottom; r++) out.push(matrix[r][right]);
    right--;
    // 5. If a row is left, read the bottom row leftward and move its edge up
    if (top <= bottom) {
      for (let c = right; c >= left; c--) out.push(matrix[bottom][c]);
      bottom--;
    }
    // 6. If a column is left, read the left column upward and move its edge in
    if (left <= right) {
      for (let r = bottom; r >= top; r--) out.push(matrix[r][left]);
      left++;
    }
  }
  // 7. Return the values in the order they were read
  return out;
}

function solve(matrix: number[][]): number[] {
  // 1. Start an empty answer and mark the four edges of the unread part
  const out = [];
  let top = 0,
    bottom = matrix.length - 1,
    left = 0,
    right = (matrix[0]?.length || 0) - 1;
  // 2. Go round while the unread part still has a row and a column
  while (top <= bottom && left <= right) {
    // 3. Read the top row from left to right, then move the top edge down
    for (let c = left; c <= right; c++) out.push(matrix[top][c]);
    top++;
    // 4. Read the right column downward, then move the right edge inward
    for (let r = top; r <= bottom; r++) out.push(matrix[r][right]);
    right--;
    // 5. If a row is left, read the bottom row leftward and move its edge up
    if (top <= bottom) {
      for (let c = right; c >= left; c--) out.push(matrix[bottom][c]);
      bottom--;
    }
    // 6. If a column is left, read the left column upward and move its edge in
    if (left <= right) {
      for (let r = bottom; r >= top; r--) out.push(matrix[r][left]);
      left++;
    }
  }
  // 7. Return the values in the order they were read
  return out;
}

def solve(matrix):
    # 1. Start an empty answer and mark the four edges of the unread part
    out = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, (len(matrix[0]) if matrix else 0) - 1
    # 2. Go round while the unread part still has a row and a column
    while top <= bottom and left <= right:
        # 3. Read the top row from left to right, then move the top edge down
        for c in range(left, right + 1):
            out.append(matrix[top][c])
        top += 1
        # 4. Read the right column downward, then move the right edge inward
        for r in range(top, bottom + 1):
            out.append(matrix[r][right])
        right -= 1
        # 5. If a row is left, read the bottom row leftward and move its edge up
        if top <= bottom:
            for c in range(right, left - 1, -1):
                out.append(matrix[bottom][c])
            bottom -= 1
        # 6. If a column is left, read the left column upward and move its edge in
        if left <= right:
            for r in range(bottom, top - 1, -1):
                out.append(matrix[r][left])
            left += 1
    # 7. Return the values in the order they were read
    return out

Example 1, traced

Input
matrix = [[1,2,3],[4,5,6],[7,8,9]]

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

Why it works

The unread cells are always exactly the rectangle between the four edges. Reading a side takes every cell of that side, and moving its edge inward removes exactly those cells from the rectangle. So no cell is read twice and none is skipped. The two checks stop a trip when the rectangle runs out halfway through, as it does for a single row or column.

Time and space

Time O(rows × columns), extra space O(rows × columns) output. Every cell is read once and added to the answer once, so the time is O(rows × columns). The answer, which is the output, holds one value per cell: that is the O(rows × columns) space. Besides the answer, only the four edges are stored.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Check that a row is left before reading the bottom row. Without the check, the single row [[1, 2, 3]] gives 1, 2, 3, 2, 1: all but its last cell is read again, backwards, as its own bottom row.
• Check that a column is left before reading the left column. Without the check, the single column [[1], [2], [3]] gives 1, 2, 3, 2.
• Do not measure the first row before you know that there is one. A matrix with no rows has no first row, and asking for its length stops the program with an error.

Pattern

Matrix traversal. Builds on Valid Palindrome and Rotate Image.

Keep going