Spiral matrix traversal

Medium TimeO(n·m) SpaceO(1)

Reading a matrix in spiral order means walking its outer ring — left to right along the top, down the right side, right to left along the bottom, up the left side — then doing the same for the ring inside it, until nothing is left. Given matrix, return all of its values in that order as a single array. The matrix need not be square, and every value appears in the output exactly once, including a single leftover row or column at the centre.

Examples

Example 1

Input
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output
[1,2,3,6,9,8,7,4,5]
The outer ring 1, 2, 3, 6, 9, 8, 7, 4, and then the 5 alone at the centre.

Example 2

Input
matrix = [[1, 2], [3, 4], [5, 6]]
Output
[1,2,4,6,5,3]
Three rows by two columns: one ring uses up every cell, so there is no centre left.

The Code

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;
}
spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]);
Done
Step through spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) call by call

More like this

All matrices & grids examples (7) →