Spiral Matrix

Medium Problem 31 of 151 Java and Python

Problem

Given an m × n matrix, return all of its elements in spiral order: along the top row left to right, down the right column, along the bottom row right to left, up the left column, and so on inwards.

Example 1

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

Example 2

Input: matrix = [[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]

Constraints

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

Explanation

Keep four boundaries: top, bottom, left, right. Walk the top edge and move top down, the right edge and move right in, and so on.

After the first two edges, check that rows and columns remain; otherwise a single middle row or column gets read twice.

Approach 1 · Better

Simulate with direction changes

Time O(m · n)
Space O(m · n) for `visited`

Walk the grid like a robot: keep a direction, mark visited cells, and turn right whenever the next cell is outside or already visited.

Use directions right, down, left, up and a visited grid.
For each of the m · n steps, record the cell, mark it, and turn if the next cell is blocked.

Java

import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        boolean[][] visited = new boolean[m][n];
        List<Integer> result = new ArrayList<>();
        int r = 0;
        int c = 0;
        int d = 0;
        for (int step = 0; step < m * n; step++) {
            result.add(matrix[r][c]);
            visited[r][c] = true;
            int nr = r + dirs[d][0];
            int nc = c + dirs[d][1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || visited[nr][nc]) {
                d = (d + 1) % 4;
                nr = r + dirs[d][0];
                nc = c + dirs[d][1];
            }
            r = nr;
            c = nc;
        }
        return result;
    }
}

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        visited = [[False] * n for _ in range(m)]
        result = []
        r = c = d = 0
        for _ in range(m * n):
            result.append(matrix[r][c])
            visited[r][c] = True
            nr, nc = r + dirs[d][0], c + dirs[d][1]
            if not (0 <= nr < m and 0 <= nc < n) or visited[nr][nc]:
                d = (d + 1) % 4
                nr, nc = r + dirs[d][0], c + dirs[d][1]
            r, c = nr, nc
        return result

Approach 2 · Optimal

Shrinking boundaries

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

Read one edge at a time and move that boundary inwards. No visited grid is needed.

Set top = 0, bottom = m - 1, left = 0, right = n - 1.
Read the top row (left → right), then top++. Read the right column (top → bottom), then right--.
If top <= bottom, read the bottom row (right → left), then bottom--.
If left <= right, read the left column (bottom → top), then left++. Repeat while top <= bottom and left <= right.

Java

import java.util.*;

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

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        result = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1
        while top <= bottom and left <= right:
            for c in range(left, right + 1):
                result.append(matrix[top][c])
            top += 1
            for r in range(top, bottom + 1):
                result.append(matrix[r][right])
            right -= 1
            if top <= bottom:
                for c in range(right, left - 1, -1):
                    result.append(matrix[bottom][c])
                bottom -= 1
            if left <= right:
                for r in range(bottom, top - 1, -1):
                    result.append(matrix[r][left])
                left += 1
        return result

Complexity compared

Approach	Time	Space
Better Simulate with direction changes	O(m · n)	O(m · n) for `visited`
Optimal Shrinking boundaries	O(m · n)	O(1) besides the output

Key takeaways

Test a single row, a single column and a non-square matrix: they catch the missing boundary checks.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem