Coding

Spiral Matrix Traversal

Asked at

Apple

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Represent the unvisited rectangle with four boundaries.
02Consume one side at a time in clockwise order.
03Shrink a side immediately after consuming it.
04Check whether the rectangle remains nonempty before reverse sides.

Reference answer

The cleanest spiral traversal is boundary based. The current unvisited region is the rectangle [top..bottom] x [left..right]. Emit its top edge left to right, then its right edge top to bottom. Shrink both boundaries. If rows remain, emit the bottom edge right to left; if columns remain, emit the left edge bottom to top. Continue until the rectangle is empty. This representation makes the correctness argument simple: after each side is emitted, that side cannot contain an unvisited cell, so moving its boundary excludes exactly visited cells. Do not use a visited matrix unless the traversal can change direction around obstacles; for a plain rectangle it is unnecessary space. The algorithm is O(mn) time because every element is output once and O(1) auxiliary space excluding output. Test 1x1, 1xn, nx1, and rectangular input.

Then expect these follow-ups

When is a visited matrix necessary?
Tests: generalization
What is the boundary invariant?
Tests: correctness

Hiring now

Get the Apple interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question