Spiral Matrix

NeetCode: Spiral Matrix · LeetCode: 54. Spiral Matrix · Difficulty: Medium

Given an m x n matrix (int[][]), return all its elements in spiral order: across the top row, down the right column, back along the bottom row, up the left column, then repeat on the inner layer.

Example

Text

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

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

Brute force: walk and turn at obstacles

Simulate a pointer that starts top-left facing right and keep a visited grid. Step forward; if the next cell is out of bounds or already visited, turn clockwise first. Stop after m * n cells. The visited grid is as large as the input. LeetCode's Java signature returns a List<Integer>, and ArrayList prints as [1, 2, 3].

Java

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

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int total = rows * cols;
        boolean[][] visited = new boolean[rows][cols];
        List<Integer> out = new ArrayList<>(total);
        // right, down, left, up
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int r = 0, c = 0, d = 0;
        for (int i = 0; i < total; i++) {
            visited[r][c] = true;
            out.add(matrix[r][c]);
            int nr = r + dirs[d][0];
            int 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 out;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.spiralOrder(new int[][] {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
        System.out.println(s.spiralOrder(new int[][] {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}));
        System.out.println(s.spiralOrder(new int[][] {{1, 2, 3}}));
    }
}

Output

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

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

Optimal: shrink four boundaries

Instead of tracking visited cells, track the rows and columns that remain: top..bottom and left..right (half-open). Peel one layer at a time: take the top row and move top down, take the right column and move right left, then, only if rows remain, take the bottom row backwards, and only if columns remain, take the left column upwards. The two if checks stop a single remaining row or column from being read twice. With half-open ranges, right - 1 and bottom - 1 are only read on non-empty ranges, so the indices stay inside the matrix.

Java

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

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int top = 0, bottom = rows, left = 0, right = cols;
        List<Integer> out = new ArrayList<>(rows * cols);
        while (top < bottom && left < right) {
            for (int c = left; c < right; c++) {
                out.add(matrix[top][c]);
            }
            top++;
            for (int r = top; r < bottom; r++) {
                out.add(matrix[r][right - 1]);
            }
            right--;
            if (top < bottom) {
                for (int c = right - 1; c >= left; c--) {
                    out.add(matrix[bottom - 1][c]);
                }
                bottom--;
            }
            if (left < right) {
                for (int r = bottom - 1; r >= top; r--) {
                    out.add(matrix[r][left]);
                }
                left++;
            }
        }
        return out;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.spiralOrder(new int[][] {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
        System.out.println(s.spiralOrder(new int[][] {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}));
        System.out.println(s.spiralOrder(new int[][] {{1, 2, 3}}));
    }
}

Output

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

Time: O(m · n), every cell is output once. Space: O(1) besides the output.