Matrix and 2D Array Traversal Patterns: 8 Essential Techniques for Grid Problems

Row-major, column-major, snake, diagonal, spiral, and graph-based BFS/DFS are the eight fundamental matrix and 2D array traversal patterns used to solve grid-based LeetCode problems.

A 2-dimensional array, or matrix, is the foundational data structure behind most LeetCode grid problems. Mastering matrix and 2D array traversal patterns is essential for efficiently visiting, reading, and updating cells in specific orders. This guide analyzes concrete implementations found in the azl397985856/leetcode repository to provide runnable code examples and authoritative file references.

Linear Scans: Row-Major and Column-Major Traversal

The most basic matrix and 2D array traversal patterns involve systematic linear scans. These are the default approaches when you need to inspect every element exactly once.

Row-Major (Left-to-Right, Top-to-Bottom)

Row-major traversal processes elements horizontally across each row before moving to the next. This pattern appears in problems/73.set-matrix-zeroes.md, where the algorithm first scans the entire matrix to identify which rows and columns must be zeroed.

def row_major(matrix):
    rows, cols = len(matrix), len(matrix[0])
    for i in range(rows):
        for j in range(cols):
            # process matrix[i][j]

            print(matrix[i][j], end=' ')
    print()

Column-Major (Top-to-Bottom, Left-to-Right)

Column-major traversal inverts the loop order, processing vertically down each column before advancing right. This pattern is essential in problems/85.maximal-rectangle.md, which uses column-wise scanning to build histograms for dynamic programming.

Directional Variations: Snake and Diagonal Patterns

When problems require specific visit orders that deviate from straight lines, directional variations of matrix and 2D array traversal patterns become necessary.

Snake (Zig-Zag) Traversal

The snake pattern alternates direction on each row—left-to-right on even indices, right-to-left on odd indices. This creates a "Z" shaped path useful for board games and specific image scanning algorithms. The logic can be adapted from daily/answers/54.spiral-matrix.js.

function snakeTraverse(mat) {
  const m = mat.length, n = mat[0].length;
  const res = [];
  for (let i = 0; i < m; i++) {
    if (i % 2 === 0) {                 // left → right
      for (let j = 0; j < n; j++) res.push(mat[i][j]);
    } else {                            // right → left
      for (let j = n - 1; j >= 0; j--) res.push(mat[i][j]);
    }
  }
  return res;
}

Diagonal and Anti-Diagonal Traversal

Diagonal traversal respects the invariant i + j = constant, producing a top-left to bottom-right wave. This is crucial for "Diagonal Traverse" problems and matrix-based DP on diagonals. The thinkings/graph.en.md file discusses diagonal symmetry in adjacency matrices.

def diagonal_traverse(mat):
    m, n = len(mat), len(mat[0])
    out = []
    for d in range(m + n - 1):
        # elements with i + j == d

        i_start = max(0, d - n + 1)
        i_end   = min(m - 1, d)
        for i in range(i_start, i_end + 1):
            j = d - i
            out.append(mat[i][j])
    return out

Anti-diagonal traversal starts from the top-right and moves toward the bottom-left, used in problems/Longest-Matrix-Path-Length.md for specific path-length calculations.

Layer-Based Traversal: Spiral Order

The spiral pattern processes the matrix from the outside in, shrinking boundaries after completing each perimeter. This is the core solution for "Spiral Matrix" and rotation problems. The implementation in daily/answers/54.spiral-matrix.js uses four boundary pointers.

function spiralOrder(matrix) {
  const res = [];
  if (!matrix.length) return res;
  let top = 0, bottom = matrix.length - 1;
  let left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    // left → right
    for (let c = left; c <= right; c++) res.push(matrix[top][c]);
    top++;

    // top → bottom
    for (let r = top; r <= bottom; r++) res.push(matrix[r][right]);
    right--;

    if (top <= bottom) {
      // right → left
      for (let c = right; c >= left; c--) res.push(matrix[bottom][c]);
      bottom--;
    }
    if (left <= right) {
      // bottom → top
      for (let r = bottom; r >= top; r--) res.push(matrix[r][left]);
      left++;
    }
  }
  return res;
}

Graph-Based Traversal: BFS and DFS on Grids

Viewing the matrix as an implicit graph—where each cell is a node and edges connect to adjacent cells—enables classic graph algorithms. The thinkings/graph.en.md file explicitly treats matrices as adjacency matrices, while thinkings/binary-tree-traversal.en.md provides the theoretical DFS/BFS foundations applicable to 2-D grids.

Breadth-First Search (BFS)

BFS is optimal for shortest-path problems on unweighted grids, such as flood-fill or multi-source distance calculations.

from collections import deque

def bfs_grid(mat, start):
    m, n = len(mat), len(mat[0])
    q = deque([start])
    visited = [[False] * n for _ in range(m)]
    visited[start[0]][start[1]] = True
    dirs = [(1,0), (-1,0), (0,1), (0,-1)]

    while q:
        r, c = q.popleft()
        # process mat[r][c]

        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                visited[nr][nc] = True
                q.append((nr, nc))

Depth-First Search (DFS)

DFS excels at connected component analysis, such as counting islands or exploring all paths in backtracking puzzles. The recursive neighbor exploration mirrors the DFS concepts detailed in thinkings/binary-tree-traversal.en.md.

Advanced: Morris-Style O(1) Space Traversal

For memory-constrained environments, Morris-style traversal uses the matrix itself to store temporary pointers, achieving O(1) auxiliary space. While not directly implemented in the repository, the concept is analogous to the Morris traversal discussed in thinkings/binary-tree-traversal.md, adapted for 2-D structures.

Summary

• Row-major and column-major scans provide the foundation for simple aggregation and dynamic programming over lines.
• Snake and diagonal patterns alternate directions to satisfy specific ordering constraints like zig-zag or wave traversal.
• Spiral traversal uses shrinking boundaries to process matrices from the outside in, essential for rotation and perimeter problems.
• BFS and DFS treat the grid as a graph, enabling shortest-path calculations and connected component analysis.
• Morris-style traversal offers O(1) space complexity for in-place matrix transformations in constrained environments.

Frequently Asked Questions

What is the most common matrix and 2D array traversal pattern for LeetCode problems?

Row-major traversal is the most frequently encountered pattern because it provides the simplest O(m·n) scan with minimal overhead. It serves as the default approach for counting, summing, and dynamic programming solutions, as demonstrated in problems/73.set-matrix-zeroes.md.

How do I choose between BFS and DFS for grid traversal problems?

Choose BFS when you need the shortest path on an unweighted grid or require level-order processing, such as in flood-fill or multi-source distance problems. Choose DFS when you need to explore all possible paths, count connected components like islands, or solve backtracking puzzles. The thinkings/graph.en.md file provides the theoretical foundation for both approaches on grids.

Can spiral matrix traversal be implemented with O(1) extra space?

Yes, spiral traversal can be implemented using O(1) auxiliary space by maintaining four boundary pointers (top, bottom, left, right) that shrink inward after processing each perimeter. This boundary-shrinking approach avoids creating a separate visited matrix, as shown in daily/answers/54.spiral-matrix.js.

Where can I find production-ready implementations of these patterns in the azl397985856/leetcode repository?

The repository contains concrete implementations across several files: daily/answers/54.spiral-matrix.js demonstrates spiral and snake logic; problems/73.set-matrix-zeroes.md shows row-major scanning; problems/85.maximal-rectangle.md uses column-major traversal; problems/Longest-Matrix-Path-Length.md implements anti-diagonal navigation; and thinkings/graph.en.md provides the graph-theoretical foundation for BFS and DFS on grids.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}