Blind 75 · Math & Geometry

Spiral Matrix

Medium

Problem

Given an m x n matrix, return all its values in clockwise spiral order: across the top row, down the right edge, back across the bottom, up the left edge, then inward and around again until every value is visited once.

Examples

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]

Example 3:
Input: matrix = [[7]]
Output: [7]

Example 4:
Input: matrix = [[1],[2],[3]]
Output: [1,2,3]

Constraints

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

Prerequisites

Index arithmetic on a grid, and the discipline of writing the coordinate rule down before coding it.

How to think about it

1. Four Shrinking Boundaries Optimal

Intuition

Hold four edges — top, bottom, left, right — and consume one at a time, pulling the boundary in behind you. The two guards before the bottom and left passes are what stop a single remaining row or column being read twice: after the top row is consumed, top may have passed bottom, and the bottom pass would replay it. [[1],[2],[3]] is in the tests for exactly that.

Algorithm

1. Walk the top row left to right; drop the top boundary.
2. Walk the right column downward; drop the right boundary.
3. If rows remain, walk the bottom row right to left; raise the bottom.
4. If columns remain, walk the left column upward; raise the left.
5. Repeat while the boundaries have not crossed.

Time & Space

Time O(m x n). Space O(1) beyond the output.