Spiral Matrix
MediumThe problem
Read the numbers of matrix in a spiral: start at the top-left, go right along the top row, then down the right column, then left along the bottom row, then up, and keep spiralling inward. Return the numbers in the order you read them.
- Example 1Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
- Example 2Input: 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]
Right along the top, down the right side, left along the bottom, up the left side, then right along what remains of the middle row.
- 1 ≤ rows, columns ≤ 10
- -100 ≤ matrix[r][c] ≤ 100
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Walk the outer ring, then shrink the four boundaries.
The idea
Maintain top, bottom, left, right; walk right, down, left, up, tightening the boundary after each side and stopping when they cross.
Target: O(m·n) time
Go function shape
func spiralOrder(matrix [][]int) []intReference solution
Tested with go test. Try it yourself first, then compare.
// SpiralOrder: walk the outer ring, then shrink the four boundaries.
func SpiralOrder(m [][]int) []int {
if len(m) == 0 {
return nil
}
top, bottom, left, right := 0, len(m)-1, 0, len(m[0])-1
var out []int
for top <= bottom && left <= right {
for c := left; c <= right; c++ {
out = append(out, m[top][c])
}
top++
for r := top; r <= bottom; r++ {
out = append(out, m[r][right])
}
right--
if top <= bottom { // a single remaining row must not be walked twice
for c := right; c >= left; c-- {
out = append(out, m[bottom][c])
}
bottom--
}
if left <= right { // same for a single remaining column
for r := bottom; r >= top; r-- {
out = append(out, m[r][left])
}
left++
}
}
return out
}