Skip to main content

14. Spiral Matrix

mediumAsked at Autodesk

Return all elements of a matrix walked in spiral order.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n matrix, return all elements of the matrix in spiral order starting from the top-left, walking right, down, left, then up, peeling off layers until everything is visited.

Constraints

  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

Examples

Example 1

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

Example 2

Input
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]

Approaches

1. Direction array with visited grid

Maintain a visited matrix and rotate direction when about to leave bounds or hit a visited cell.

Time
O(mn)
Space
O(mn)
const dirs=[[0,1],[1,0],[0,-1],[-1,0]]; let d=0;
while (count<m*n) { /* step, mark visited, rotate on need */ }

Tradeoff:

2. Shrinking boundaries

Track top, bottom, left, right boundaries and peel each side, advancing the boundary after each pass. Constant extra space.

Time
O(mn)
Space
O(1) extra
function spiralOrder(m) {
  const out = [];
  let top = 0, bot = m.length - 1;
  let left = 0, right = m[0].length - 1;
  while (top <= bot && left <= right) {
    for (let j = left; j <= right; j++) out.push(m[top][j]); top++;
    for (let i = top; i <= bot; i++) out.push(m[i][right]); right--;
    if (top <= bot) { for (let j = right; j >= left; j--) out.push(m[bot][j]); bot--; }
    if (left <= right) { for (let i = bot; i >= top; i--) out.push(m[i][left]); left++; }
  }
  return out;
}

Tradeoff:

Autodesk-specific tips

Boundary-shrinking patterns line up with Autodesk's raster-tile traversal used inside their image-processing pipelines.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

More Autodesk coding interview questions

See all Autodesk problems →

Companies that also ask Spiral Matrix