Spiral Matrix
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return all elements of a matrix in spiral order (clockwise from the top-left).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which four boundaries do you track?
- Hint 2After going along the top row, which boundary moves?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Walking round a park along its fence, then stepping one path inside and walking the next ring, and so on until you reach the middle. You keep four notes: the top row, bottom row, left column and right column you may still use. After walking along a side, that side is done and its wall moves inward.
- The obvious way
Mark visited cells and turn when blocked: also O(cells), with extra memory.
- The key insight
Keep top, bottom, left, right. While top <= bottom and left <= right: walk the top row left to right then top + 1; the right column top to bottom then right - 1; if rows remain walk the bottom row right to left then bottom - 1; if columns remain walk the left column bottom to top then left + 1.
- The algorithm
- Set the four boundaries.
- Walk the top row, then move top down.
- Walk the right column, then move right in.
- Walk the bottom row and left column if still inside; repeat.
Watch it run
Examplematrix = [[1,2,3],[4,5,6],[7,8,9]]
Top row left to right: 1, 2, 3.
1, 2, 3
Where people slip
- The two if checks stop the walk from repeating a row or column when only one is left.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def spiral_order(matrix):
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
for column in range(left, right + 1): # along the top fence
result.append(matrix[top][column])
top += 1
for row in range(top, bottom + 1): # down the right fence
result.append(matrix[row][right])
right -= 1
if top <= bottom:
for column in range(right, left - 1, -1): # back along the bottom fence
result.append(matrix[bottom][column])
bottom -= 1
if left <= right:
for row in range(bottom, top - 1, -1): # up the left fence
result.append(matrix[row][left])
left += 1
return resultNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.