Spiral traversal of a matrix

Medium

Problem

Return all elements of an R × C matrix in spiral order: along the top row left to right, down the right column, back along the bottom row, up the left column, then repeat inward.

Example 1

Input:  [[1,2,3], [4,5,6], [7,8,9]]
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Also asked as: Spiral traversal on a Matrix

Test cases

Case 1

Input:    [[1,2,3],[4,5,6],[7,8,9]]
Expected: [1,2,3,6,9,8,7,4,5]

Case 2

Input:    [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Expected: [1,2,3,4,8,12,11,10,9,5,6,7]

Case 3

Input:    [[1],[2],[3]]
Expected: [1,2,3]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Shrinking boundaries

Time O(R·C)Space O(1) extra

Keep top/bottom/left/right walls; walk right, down, left, up, moving the wall in after each pass.

function spiralOrder(m) {
const res = [];
let top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;
while (top <= bottom && left <= right) {
for (let c = left; c <= right; c++) res.push(m[top][c]);
top++;
for (let r = top; r <= bottom; r++) res.push(m[r][right]);
right--;
if (top <= bottom) { for (let c = right; c >= left; c--) res.push(m[bottom][c]); bottom--; }
if (left <= right) { for (let r = bottom; r >= top; r--) res.push(m[r][left]); left++; }
}
return res;
}