Spiral traversal on a Matrix

The problem, simply

You get a grid of numbers with m rows and n columns. In code this is a matrix, int[][].

Read every number exactly once in spiral order. Start at the top left corner. Go right along the top row, down the right side, left along the bottom row, and up the left side. Then do the same thing one ring further in, until nothing is left. Give back the numbers in the order you read them.

A story to remember it

Picture it

Examples

Way 1: the simple way

Pretend you are a robot that walks forward and turns right when it bumps into something. Keep a second grid of check marks, so you know which cells you already visited.

1. Start at row 0, column 0, facing right.
2. Write down the number and put a check mark on the cell.
3. Look at the next cell straight ahead. If it is off the grid or already checked, turn right (right, then down, then left, then up, then right again).
4. Step forward. Repeat until you have written m * n numbers.

import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0 || matrix[0].length == 0) return result;

        int m = matrix.length, n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];   // the check marks

        int[] dr = {0, 1, 0, -1};   // right, down, left, up
        int[] dc = {1, 0, -1, 0};
        int row = 0, col = 0, dir = 0;

        for (int i = 0; i < m * n; i++) {
            result.add(matrix[row][col]);
            visited[row][col] = true;

            int nr = row + dr[dir], nc = col + dc[dir];
            boolean blocked = nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc];
            if (blocked) {                 // bumped into a wall or a checked cell
                dir = (dir + 1) % 4;       // turn right
                nr = row + dr[dir];
                nc = col + dc[dir];
            }
            row = nr;
            col = nc;
        }
        return result;
    }
}

How long it takes: every cell is read once, O(m*n). Extra room: the grid of check marks is as big as the input, O(m*n).

Way 2: the clever way

Throw away the check marks. Use four fences instead: top, bottom, left and right. Everything between the fences is still unread.

1. Walk the top row from left to right. Then move the top fence down by one.
2. Walk the right column from top to bottom. Then move the right fence left by one.
3. If top <= bottom, a bottom row still exists. Walk it from right to left, then move the bottom fence up.
4. If left <= right, a left column still exists. Walk it from bottom to top, then move the left fence right.
5. Repeat while top <= bottom and left <= right.

The two if checks in steps 3 and 4 matter. After step 1 and step 2 the fences may already have crossed, and without the checks you would read a row or column a second time.

import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0 || matrix[0].length == 0) return result;

        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            for (int c = left; c <= right; c++) result.add(matrix[top][c]);      // top row, going right
            top++;

            for (int r = top; r <= bottom; r++) result.add(matrix[r][right]);    // right column, going down
            right--;

            if (top <= bottom) {                                                  // a bottom row is still there
                for (int c = right; c >= left; c--) result.add(matrix[bottom][c]);
                bottom--;
            }

            if (left <= right) {                                                  // a left column is still there
                for (int r = bottom; r >= top; r--) result.add(matrix[r][left]);
                left++;
            }
        }
        return result;
    }
}

How long it takes: still every cell once, O(m*n). Extra room: four whole numbers for the fences, O(1), not counting the answer list we must return anyway.

Watch out for

• An empty matrix, or [[]]. Check matrix.length == 0 || matrix[0].length == 0 first.
• Mixing up rows and columns. matrix[r][c] is row first, then column.
• Moving a fence before the walk that needs it. Walk the side, then move that one fence.
• In Way 1, checking only the edge of the grid and forgetting the checked cells. The robot would walk off its own path.

What interviewers ask next

• Fill an n by n grid with 1, 2, 3 and so on in spiral order (Spiral Matrix II). Use the same four fences, but write a counter into the cells instead of reading them.
• Counter clockwise spiral. Walk down the left column first, then the bottom row, then up the right column, then the top row.
• Find the kth number of the spiral without walking it all. Each full ring has 2 * (rows + cols) - 4 cells, so skip whole rings until k lands inside one, then walk only that ring. That is O(min(m, n)) time.
• Start from a given cell and spiral outward (Spiral Matrix III). Walk 1 step right, 1 down, 2 left, 2 up, 3 right, and so on, and keep only the cells that land inside the grid.
• Can you do it with recursion? Yes. Read the outer ring, then call yourself on the inner grid. It is the same work with an extra call stack of O(min(m, n)) depth.

Remember this

Grown-up words: the grid is a matrix, the robot with check marks is direction simulation with a visited array, the fences are boundary pointers, and each lap of the lawn is a layer or ring of the matrix.