54. Spiral Matrix

How to solve Spiral Matrix (LeetCode 54): the approach in brief

The problem

Given an m x n matrix, return all elements of the matrix in spiral order.

Pattern

Spiral Matrix is a Array/Matrix Manipulation Patterns problem, in the Spiral Traversal subpattern. The pattern covers in-place operations, hashing, prefix sums, spiral traversal, and cyclic sort

Master spiral traversal pattern for 2D matrices. Learn to traverse matrices in spiral order for interview problems.

Approach outline

1. Well for some problems, the best way really is to come up with some algorithms for simulation. Basically, you need to simulate what the problem asks us to do.
2. We go boundary by boundary and move inwards. That is the essential operation. First row, last column, last row, first column, and then we move inwards by 1 and repeat. That's all. That is all the simulation that we need.
3. Think about when you want to switch the progress on one of the indexes. If you progress on i out of [i, j], you'll shift in the same column. Similarly, by changing values for j, you'd be shifting in the same row. Also, keep track of the end of a boundary so that you can move inwards and then keep repeating. It's always best to simulate edge cases like a single column or a single row to see if anything breaks or not.

Complexity

The reference solution runs in O(m * n) time and O(1) space.

Asked at

Spiral Matrix has been reported in interviews at Microsoft, Apple, Intuit, Facebook, Google, Amazon, ByteDance, Expedia.