cf.completefrontend
ARRAYS & HASHING · FOUNDATION

Matrix traversal

Visit the cells of a grid in a planned order, such as row by row, column by column, along diagonals, or in a spiral.

Time O(rows * cols)Space O(1) besides the output10 practice problemsStep-through picture

The idea

A matrix (or grid) is an array of rows, and each row is an array of cells. The cell in row r and column c is grid[r][c]. Rows count down from 0 at the top, and columns count across from 0 at the left.

Many grid problems are about visiting cells in a particular order: row by row to read it, column by column to flip it (transpose), along diagonals, or in a spiral from the outside in. The skill is keeping the row and column indexes straight and never stepping outside the grid.

The code here reads a grid in spiral order. It keeps four walls, top, bottom, left, and right, walks along each wall in turn, and moves that wall inward after it's done.

An everyday example

Mowing a lawn from the edge inward

You mow a rectangular lawn by going around its edge: along the top, down the right side, back along the bottom, and up the left side. Then the uncut part is a smaller rectangle, so you go around its edge, and so on until nothing is left. Each lap, the edge you've just mowed is no longer part of the lawn you have to think about.

How the example maps to the code
In the exampleIn the code
The edges of the uncut lawntop, bottom, left, right
Mowing along the top edgefor (let c = left; c <= right; c++) on row top
That edge is done, so the lawn gets shortertop++
Nothing left to mowtop > bottom or left > right

From the slow way to matrix traversal

  1. One obvious way to read a grid in a spiral is to simulate a walker. It moves in one direction and turns right when the next cell is outside the grid or already visited. That works, but it needs a visited grid as big as the input and careful turning logic.
  2. Look at the cells not yet read. After reading the whole top row, they form a smaller rectangle. After reading its right column, a smaller one still. The unread part is always a rectangle, so four numbers describe it: top, bottom, left, and right.
  3. So instead of tracking every cell, walk along one side of the rectangle and then move that side's wall inward by one. Top row, then right column, then bottom row backwards, then left column upwards: each pass shrinks the rectangle.
  4. When only a single row or column is left, the bottom-row and left-column passes would read cells a second time, so each gets a check first. Repeat until the walls cross: that loop is spiral matrix traversal.

How it works

  1. Set the walls: top = 0, bottom = last row, left = 0, right = last column.
  2. Read the top row from left to right, then move top down by one.
  3. Read the right column from top to bottom, then move right left by one.
  4. If rows are left (top <= bottom), read the bottom row from right back to left, then move bottom up.
  5. If columns are left (left <= right), read the left column from bottom up to top, then move left right.
  6. Repeat while top <= bottom and left <= right.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function spiralOrder(grid) {
  2. const result = [];
  3. let top = 0;
  4. let bottom = grid.length - 1;
  5. let left = 0;
  6. let right = grid[0].length - 1;
  7. while (top <= bottom && left <= right) {
  8. for (let c = left; c <= right; c++) result.push(grid[top][c]);
  9. top++;
  10. for (let r = top; r <= bottom; r++) result.push(grid[r][right]);
  11. right--;
  12. if (top <= bottom) {
  13. for (let c = right; c >= left; c--) result.push(grid[bottom][c]);
  14. bottom--;
  15. }
  16. if (left <= right) {
  17. for (let r = bottom; r >= top; r--) result.push(grid[r][left]);
  18. left++;
  19. }
  20. }
  21. return result;
  22. }

How fast it is

TimeO(rows * cols)
Extra memoryO(1) besides the output

Each cell is read exactly once. Only the four walls and loop counters are stored.

  • Best caseO(rows × cols)

    Even a 1 × 1 grid reads its one cell. The output holds every cell, so no input can skip any.

  • Average caseO(rows × cols)

    Each cell is read once, plus a few wall checks per lap.

  • Worst caseO(rows × cols)

    A square grid needs the most laps, about half its side, but the total reads are still one per cell.

Common mistakes

  • Swapping row and column: grid[c][r] instead of grid[r][c]. Name the loop variables r and c to keep them straight.
  • Leaving out the top <= bottom and left <= right checks inside the loop, which reads a single leftover row or column twice.
  • Assuming the grid is square. Use grid.length for rows and grid[0].length for columns.
  • Reading a neighbor before checking it's inside the grid. grid[-1][c] throws an error.

When to use it

Look for these clues in a problem:

  • The input is a 2D array: a board, an image, a spreadsheet, a seat map.
  • The problem describes a reading order: spiral, diagonal, zigzag, layer by layer.
  • You need to rotate, flip, or transpose a grid.
  • Each cell's answer depends on its neighbors (up, down, left, right).

Check yourself

Answer each one in your head first, then open it.

In the trace's second lap, why does the bottom-row pass read nothing even though top <= bottom?

right has dropped to 0 while left is 1, so the loop from right down to left has no steps.

What would [[3, 8, 1]] return without the top <= bottom check?

[3, 8, 1, 8, 3]. The bottom-row pass would read row 0 again, backwards, from right = 1 down to left = 0.

How many laps does the while loop make for a 4 × 3 grid?

Two. The first reads the outer ring of 10 cells, and the second reads the last 2.

Why is the extra space O(1)?

The unread part is always a rectangle, so four numbers describe it. No per-cell visited flags are needed.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 10 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule: at the top of each lap, the unread cells are exactly rows top to bottom in columns left to right, and result holds every other cell in spiral order. At the start the walls are the grid's edges and result is empty, so it holds.

Each pass reads one edge of that rectangle and then moves the matching wall, so the cells it read are now outside the walls. The right-column pass starts at the new top, so the top-right corner isn't read twice. The checks before the bottom-row and left-column passes stop a lone row or column from being read again in the other direction.

Every lap moves top down by one, so the loop can't run forever. When the walls cross, the rectangle is empty, which by the rule means result holds every cell exactly once, in the right order.

Going deeper

4 more ideas

Why the walls never let a cell be read twice

After a side is read, its wall moves inward, so the cells on that side are outside the walls from then on. The checks before the bottom row and left column matter when only one row or one column is left: without them, the code would read that row forwards and then backwards again.

Other common orders

Transposing swaps rows and columns: result[c][r] = grid[r][c]. Rotating 90 degrees clockwise puts grid[r][c] at result[c][n - 1 - r]; in place, that's a transpose followed by reversing each row. Cells on the same diagonal share r - c, and cells on the same anti-diagonal share r + c.

Neighbors and edges

To visit a cell's four neighbors, loop over a list of moves like [[-1, 0], [1, 0], [0, -1], [0, 1]] and skip any neighbor where nr < 0, nr >= rows, nc < 0, or nc >= cols. Reading grid[-1] gives undefined, and reading undefined[c] throws, so check the bounds first.

Cost

Every traversal here visits each cell a constant number of times: O(rows * cols) time. The spiral uses only the four walls besides the output, so O(1) extra space.

Work it by hand

Every step in a table, with why

Read a grid with 4 rows and 3 columns in spiral order. The second lap shows why the inner checks matter.

grid = [[7, 1, 8], [2, 9, 4], [6, 3, 5], [0, 4, 2]]

StepSideReadstopbottomleftrightWhy
1Top row7, 1, 81302Read row 0 from left to right, then move top down to 1.
2Right column4, 5, 21301Read column 2 from the new top to bottom, then move right in to 1.
3Bottom row4, 01201top <= bottom, so read row 3 backwards from right to left, then move bottom up to 2.
4Left column6, 21211left <= right, so read column 0 upwards from bottom to top, then move left to 1. The first lap is done.
5Top row92211The rectangle left is rows 1 to 2 of column 1. Read 9 and move top to 2.
6Right column32210Read 3 from row 2 of column 1. right drops to 0, below left.
7Bottom rownothing2110top <= bottom (2 <= 2) is true, but the loop from right = 0 down to left = 1 is empty, so nothing is read. bottom moves to 1.
8Left columnskipped2110left <= right is 1 <= 0, false, so the pass is skipped. Now top > bottom, and the while loop ends.

The result is [7, 1, 8, 4, 5, 2, 4, 0, 6, 2, 9, 3]: all 12 cells, each read once, in 2 laps.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Matrix traversalO(rows × cols)O(1)A plain spiral or layer order with the least memory, using four walls.
Walker with a visited gridO(rows × cols)O(rows × cols)The path has extra rules, like blocked cells, that four walls can't describe.
Read the top row, rotate the rest, repeatO(n^3)O(n²)Very short code for tiny grids. Rebuilding the rest after every row costs about n³ steps for an n × n grid.

Extra memory: O(1) besides the output: four walls and a loop counter. The walker approach needs an extra O(rows × cols) grid of visited flags.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Matrix traversal and the other approaches, on a scale where each line up is 10 times more steps.
  • Matrix traversal, Walker with a visited grid O(rows × cols)
  • Read the top row, rotate the rest, repeat O(n^3)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Matrix traversal1001 million1 trillion
Walker with a visited grid1001 million1 trillion
Read the top row, rotate the rest, repeat1,0001 billionmore than a quadrillion

Inputs that need care

5 tricky inputs
One row: grid = [[3, 8, 1]]
The top pass reads all three, top passes bottom, the right-column loop is empty, and both checks keep the other passes from reading anything again. Result: [3, 8, 1].
One column: grid = [[3], [8], [1]]
The top pass reads 3, the right pass reads 8, 1, and right drops below left. The bottom loop is empty and the left pass is skipped. Result: [3, 8, 1].
An empty grid: grid = []
grid[0].length throws, because grid[0] is undefined. Return [] first when grid.length is 0.
Rows with no cells: grid = [[]]
right starts at -1, so left <= right is false at once and the result is [].
Rows of different lengths
The walls assume every row has grid[0].length cells. Shorter rows give undefined in the result, so check the shape first.

Variations and follow-ups

Twists interviewers add

Fill a grid in spiral order

Use the same four walls, but write 1, 2, 3, ... into the cells instead of reading them. This builds an n × n spiral of numbers.

Rotate a square layer by layer

To rotate a square grid 90 degrees in place, handle one ring at a time, from the outside in. For each position on the ring, move four cells around in one cycle: top to right, right to bottom, bottom to left, left to top.

A walker with direction lists

Keep dr = [0, 1, 0, -1] and dc = [1, 0, -1, 0] with a direction index, and turn when the next cell is outside or visited. It needs the visited grid, but it also handles walks with obstacles or snake-like paths.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "spiral order", "clockwise", "layer by layer", or "rotate the image".
  • Explain the walls before coding: "the unread cells always form a rectangle, so I keep its four edges and move one inward after each side".
  • Test by hand: one row, one column, and a grid that isn't square. All three hit the inner checks.
  • A common follow-up is "rotate the matrix 90 degrees in place". Answer: transpose it and reverse each row, or rotate four cells at a time ring by ring.

Where frontend code uses it

The same idea in real UI code
  • Canvas pixel data from getImageData is a flat array where pixel (x, y) starts at index (y * width + x) * 4, so image filters are matrix traversals.
  • Spreadsheet and data-grid components move the active cell with arrow keys, checking the grid's edges.
  • Rotating or flipping an image or a game board by 90 degrees in a browser editor.
  • Calendar month views lay out days in a grid of weeks and weekdays, read row by row.

Related algorithms