54. Spiral Matrix
mediumAsked at Goldman SachsReturn all elements of a matrix in spiral order. Goldman Sachs uses Spiral Matrix to test boundary-tracking discipline — the candidate who articulates the four shrinking boundaries before coding is the one who survives the edge cases.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Goldman Sachs loops.
- Glassdoor (2026-Q1)— Goldman Sachs SWE candidate reports list Spiral Matrix as a 'matrix-traversal boundary-tracking' question.
- LeetCode Discuss (2025-12)— Spiral Matrix is in the top-20 of LeetCode's Goldman Sachs company tag.
Problem
Given an m x n matrix, return all elements of the matrix in spiral order.
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
Examples
Example 1
matrix = [[1,2,3],[4,5,6],[7,8,9]][1,2,3,6,9,8,7,4,5]Example 2
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]][1,2,3,4,8,12,11,10,9,5,6,7]Approaches
1. Four shrinking boundaries (optimal)
Maintain top, bottom, left, right boundaries. Traverse top row, right col, bottom row, left col; shrink each boundary after.
- Time
- O(m * n)
- Space
- O(1)
function spiralOrder(matrix) {
const result = [];
let top = 0, bottom = matrix.length - 1;
let left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (let j = left; j <= right; j++) result.push(matrix[top][j]);
top++;
for (let i = top; i <= bottom; i++) result.push(matrix[i][right]);
right--;
if (top <= bottom) {
for (let j = right; j >= left; j--) result.push(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (let i = bottom; i >= top; i--) result.push(matrix[i][left]);
left++;
}
}
return result;
}Tradeoff: Linear in matrix size, O(1) extra space beyond the output. The two if-guards after the third and fourth traversals are critical — for non-square matrices, one dimension exhausts before the other and you'd double-visit cells without them.
2. Direction-vector with visited marker
Walk with a (dr, dc) vector; rotate clockwise when you hit a boundary or visited cell.
- Time
- O(m * n)
- Space
- O(m * n)
function spiralOrderDir(matrix) {
const m = matrix.length, n = matrix[0].length;
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
const dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
let r = 0, c = 0, di = 0;
const result = [];
for (let i = 0; i < m * n; i++) {
result.push(matrix[r][c]);
seen[r][c] = true;
const nr = r + dr[di], nc = c + dc[di];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) {
di = (di + 1) % 4;
}
r += dr[di];
c += dc[di];
}
return result;
}Tradeoff: More general framework but uses O(m*n) extra space for the visited grid. Mention as the 'reusable template for any spiral-walk problem', but lead with the boundaries version since Goldman wants O(1) extra space.
Goldman Sachs-specific tips
Goldman Sachs interviewers want to see the four boundaries named explicitly BEFORE coding. The exact edge case they probe: rectangular matrices where m != n. Single-row [1,2,3] should not loop back; single-column [[1],[2],[3]] should not skip cells. The two if-checks after the third and fourth traversals are the rubric point — without them, an mxn matrix where m != n returns duplicate cells.
Common mistakes
- Forgetting the if (top <= bottom) and if (left <= right) guards for rectangular matrices.
- Indexing matrix[top][i] when you meant matrix[i][right] — confusing row/col with the loop variable.
- Hard-coding the assumption m == n, which silently breaks on non-square inputs.
Follow-up questions
An interviewer at Goldman Sachs may pivot to one of these next:
- Spiral Matrix II (LC #59) — fill an n x n matrix with 1..n*n in spiral order. (Same template, fill instead of read.)
- Spiral Matrix III (LC #885) — walk a spiral starting from an arbitrary cell, including out-of-grid positions.
- What if you needed to traverse counter-clockwise? (Reverse the order of the four edge-traversals.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why do we need the two extra if-guards?
Because for a rectangular matrix, one dimension exhausts before the other. After traversing the top row of a 1xN matrix, top exceeds bottom and the third traversal (right-to-left bottom row) would re-visit cells already added. The guards skip the redundant traversal.
Is the boundary version really O(1) space?
Excluding the output. The result array itself is O(m*n) which is unavoidable since we're returning every cell. The space for state variables (top, bottom, left, right) is O(1).
Free learning resources
Curated free links for this problem.