Spiral Matrix
MediumMatrix
You get an m × n matrix. Return all of its values in spiral order: start at the top left and go clockwise, along the top row, down the right column, back along the bottom row, up the left column, then the same again one ring further in, until every value is read once.
Examples
Input: matrix = [[1, 2, 3], [8, 9, 4], [7, 6, 5]] Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
The numbers are laid out so the spiral reads them in order: the outer ring 1 to 8, then the 9 in the middle.
Input: matrix = [[3, 1], [4, 1], [5, 9]] Output: [3, 1, 1, 9, 5, 4]
Across the top (3, 1), down the right (1, 9), back along the bottom (5), up the left (4).
Constraints
1 ≤ m, n ≤ 10-100 ≤ matrix[i][j] ≤ 100
Stuck?
Hint 1
Keep four bounds: the top row, the bottom row, the left column and the right column still unread. Read one side, then move that bound inward.
Hint 2
After reading the top row and the right column, check that a row and a column are still left before reading the bottom row and the left column backwards. Without that check, a matrix with a single row or column left is read twice.
The idea
Read the matrix ring by ring, keeping four bounds around the part not read yet. Each side you read moves one bound inward, and the loop ends when the bounds cross. The care is all in the last ring, which can be a single row or a single column.
Time O(m · n)Extra space O(1) besides the answer
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 5
Four bounds frame the part not read yet: the top and bottom rows and the left and right columns, all inclusive.
function spiralOrder(matrix) { const out = []; let top = 0; let bottom = matrix.length - 1; let left = 0; let right = matrix[0].length - 1; while (top <= bottom && left <= right) { for (let c = left; c <= right; c++) out.push(matrix[top][c]); top++; for (let r = top; r <= bottom; r++) out.push(matrix[r][right]); right--; if (top <= bottom) { for (let c = right; c >= left; c--) out.push(matrix[bottom][c]); bottom--; } if (left <= right) { for (let r = bottom; r >= top; r--) out.push(matrix[r][left]); left++; } } return out;}The trap
This version reads all four sides on every turn of the loop without checking that a row and a column are still left. On a square matrix the rings close neatly and the output is right. But once the top row or the right column has used up the last row or column, the next sides read the same values again, backwards. A single row, a single column and many matrices that are not square come out with repeats.
function spiralOrder(matrix) { const out = []; let top = 0; let bottom = matrix.length - 1; let left = 0; let right = matrix[0].length - 1; while (top <= bottom && left <= right) { for (let c = left; c <= right; c++) out.push(matrix[top][c]); top++; for (let r = top; r <= bottom; r++) out.push(matrix[r][right]); right--; for (let c = right; c >= left; c--) out.push(matrix[bottom][c]); // no check that a row is left bottom--; for (let r = bottom; r >= top; r--) out.push(matrix[r][left]); left++; } return out;}