Matrix traversal

Overview

A matrix (2D grid) is an array of rows, where grid[r][c] is row r, column c. Matrix problems test whether you can move around a grid safely: in 4 or 8 directions, in spiral or diagonal order, and without stepping outside the boundaries.

Most grid problems combine a small set of techniques: a directions array for neighbors, bounds checks, marking visited cells, and layer-by-layer processing for spirals and rotations. Grids are also implicit graphs, where each cell is a node connected to its neighbors.

When to use it

• Input is a 2D board, image, map, or game grid.
• The problem asks for spiral order, rotation, transpose, or diagonal traversal.
• You need to explore regions: islands, flood fill, shortest path in a maze.
• The matrix is sorted by rows and columns (staircase search).

Problem patterns it solves

Where it is used in real software

Key terms

Row-major order

Rows are stored one after another; iterating row by row is the cache-friendly order.

Directions array

[[1,0],[-1,0],[0,1],[0,-1]] lists row and column offsets for 4-directional neighbors.

Bounds check

0 <= r < rows and 0 <= c < cols before reading grid[r][c].

Visited marking

Change the cell value or keep a boolean grid so each cell is processed once.

Flattened index

Map (r, c) to id = r * cols + c, useful for Union Find or visited sets.

Spiral traversal with four boundaries

1. 1
   Set boundaries

   top = 0, bottom = rows - 1, left = 0, right = cols - 1.

2. 2
   Walk the top row left to right

   Visit grid[top][left..right], then top++.

3. 3
   Walk the right column top to bottom

   Visit grid[top..bottom][right], then right--.

4. 4
   Walk the bottom row right to left

   Only if top <= bottom. Visit grid[bottom][right..left], then bottom--.

5. 5
   Walk the left column bottom to top

   Only if left <= right. Visit grid[bottom..top][left], then left++. Repeat while top <= bottom and left <= right.

Spiral order of a 3 x 4 matrix

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

Result: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]. The two guard checks prevent revisiting the last row or column in non-square matrices.

Implementation

1const DIRS = [[1, 0], [-1, 0], [0, 1], [0, -1]];2 3// Visit valid 4-directional neighbors4function neighbors(grid, r, c) {5  const result = [];6  for (const [dr, dc] of DIRS) {7    const nr = r + dr, nc = c + dc;8    if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length) {9      result.push([nr, nc]);10    }11  }12  return result;13}14 15function spiralOrder(matrix) {16  const result = [];17  let top = 0, bottom = matrix.length - 1;18  let left = 0, right = matrix[0].length - 1;19 20  while (top <= bottom && left <= right) {21    for (let c = left; c <= right; c++) result.push(matrix[top][c]);22    top++;23    for (let r = top; r <= bottom; r++) result.push(matrix[r][right]);24    right--;25    if (top <= bottom) {26      for (let c = right; c >= left; c--) result.push(matrix[bottom][c]);27      bottom--;28    }29    if (left <= right) {30      for (let r = bottom; r >= top; r--) result.push(matrix[r][left]);31      left++;32    }33  }34  return result;35}36 37// Rotate 90 degrees clockwise in place: transpose, then reverse each row38function rotate(matrix) {39  const n = matrix.length;40  for (let r = 0; r < n; r++) {41    for (let c = r + 1; c < n; c++) {42      [matrix[r][c], matrix[c][r]] = [matrix[c][r], matrix[r][c]];43    }44  }45  for (const row of matrix) row.reverse();46}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Confusing rows and columns.

  Fix: Use grid[row][col] consistently; rows = grid.length, cols = grid[0].length.

• Spiral revisits the middle row or column.

  Fix: Check top <= bottom and left <= right before the third and fourth walks.

• Creating a 2D array with shared rows in JS.

  Fix: new Array(r).fill(new Array(c)) shares one row. Use Array.from({ length: r }, () => new Array(c).fill(0)).

• Checking bounds after reading the cell.

  Fix: Always check bounds first, then read.

Interview questions

Practice problems