Spiral Matrix

Given an m × n matrix, return its elements in spiral order: along the top row, down the right column, back along the bottom row, up the left column, and then the same again one layer further in.

LeetCode: 54. Spiral Matrix

Example

Text

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Brute force: simulate the walk

Walk right, and turn clockwise whenever the next cell is outside the matrix or already visited. A visited grid remembers where we've been.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> spiralOrder(int[][] matrix) {
        int rows = matrix.length, cols = rows == 0 ? 0 : matrix[0].length;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // right, down, left, up
        boolean[][] visited = new boolean[rows][cols];
        List<Integer> result = new ArrayList<>(rows * cols);
        int r = 0, c = 0, d = 0;
        for (int step = 0; step < rows * cols; step++) {
            result.add(matrix[r][c]);
            visited[r][c] = true;
            int nr = r + dirs[d][0], nc = c + dirs[d][1];
            boolean blocked = nr < 0 || nc < 0 || nr >= rows || nc >= cols || visited[nr][nc];
            if (blocked) d = (d + 1) % 4;
            r += dirs[d][0];
            c += dirs[d][1];
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] m = new int[4][4];
        for (int r = 0; r < 4; r++) {
            for (int c = 0; c < 4; c++) m[r][c] = r * 4 + c + 1;
        }
        System.out.println(spiralOrder(m));
        System.out.println(spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}}));
    }
}

Output

[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
[1, 2, 3, 6, 5, 4]

Time: O(m·n). Space: O(m·n) for visited.

Optimal: shrink four boundaries

Keep the bounds of the unvisited rectangle: top, bottom, left, right (exclusive at the bottom and right). Read one side, then move that boundary inwards. The checks before the bottom row and left column stop a single remaining row or column from being read twice.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> spiralOrder(int[][] matrix) {
        int top = 0, bottom = matrix.length;
        int left = 0, right = matrix.length == 0 ? 0 : matrix[0].length;
        List<Integer> result = new ArrayList<>(bottom * right);
        while (top < bottom && left < right) {
            for (int j = left; j < right; j++) result.add(matrix[top][j]); // top row, left to right
            top++;
            for (int i = top; i < bottom; i++) result.add(matrix[i][right - 1]); // right column, downwards
            right--;
            if (top < bottom) {
                for (int j = right - 1; j >= left; j--) result.add(matrix[bottom - 1][j]); // bottom row, right to left
                bottom--;
            }
            if (left < right) {
                for (int i = bottom - 1; i >= top; i--) result.add(matrix[i][left]); // left column, upwards
                left++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] m = new int[4][4];
        for (int r = 0; r < 4; r++) {
            for (int c = 0; c < 4; c++) m[r][c] = r * 4 + c + 1;
        }
        System.out.println(spiralOrder(m));
        System.out.println(spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}}));
        System.out.println(spiralOrder(new int[][]{{1}, {2}, {3}}));
        System.out.println(spiralOrder(new int[0][0]));
    }
}

Output

[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
[1, 2, 3, 6, 5, 4]
[1, 2, 3]
[]

Time: O(m·n). Space: O(1) besides the output.

Edge cases

Single row or single column: the guarded steps prevent duplicates, as the 3 × 1 example shows.
Empty matrix: returns an empty List, as the last call shows.