Grid & Matrix Traversal

Many interview problems use a 2D grid or matrix. The grid can be viewed as a graph: each cell is a node, and edges connect adjacent cells (e.g. up/down/left/right). Traversal then reduces to BFS or DFS on this implicit graph. This article covers how to set up grid traversal, when to use BFS vs DFS, and how to solve common grid problems.

Grid as a Graph

  • Nodes: Cells (r, c) with 0 ≤ r < m and 0 ≤ c < n.
  • Edges: Typically 4-directional (up, down, left, right) or 8-directional (add diagonals).
  • Weights: In “plain” grid problems, each step has the same cost (unweighted), so BFS gives shortest path in number of steps.

You do not build an explicit adjacency list. Instead, for each cell (r, c) you generate neighbors on the fly by adding direction offsets and checking bounds (and any blocked cells).

Direction Vectors

4-directional (most common):

Java
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right

8-directional (including diagonals):

Java
int[][] dirs = {
    {-1,-1}, {-1,0}, {-1,1},
    { 0,-1},         { 0,1},
    { 1,-1}, { 1,0}, { 1,1}
};

For each current cell (r, c):

Java
for (int[] d : dirs) {
    int nr = r + d[0], nc = c + d[1];
    if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] != OBSTACLE) {
        // (nr, nc) is a valid neighbor
    }
}

Always check bounds and visited (and optionally obstacles) before enqueueing or recursing.

BFS on a Grid (Shortest Path)

Use BFS when you need the shortest number of steps from a start cell to a target (or to all cells) in an unweighted grid.

Template:

Java
int shortestPath(int[][] grid, int sr, int sc, int tr, int tc) {
    int m = grid.length, n = grid[0].length;
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    boolean[][] visited = new boolean[m][n];
    Queue<int[]> q = new ArrayDeque<>(); // [r, c, dist]

    visited[sr][sc] = true;
    q.offer(new int[]{sr, sc, 0});

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1], d = cur[2];
        if (r == tr && c == tc) return d;

        for (int[] dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] != 1) {
                visited[nr][nc] = true;
                q.offer(new int[]{nr, nc, d + 1});
            }
        }
    }
    return -1; // unreachable
}

Important: mark visited when you enqueue, not when you poll, so the same cell is not enqueued multiple times.

DFS on a Grid (Connectivity, Count Regions)

Use DFS when you need to explore all cells in a connected region (e.g. count islands, flood fill) or enumerate paths. DFS does not give shortest path; it just visits every reachable cell.

Template:

Java
void dfs(int[][] grid, int r, int c, boolean[][] visited) {
    int m = grid.length, n = grid[0].length;
    if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) return;

    visited[r][c] = true;
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    for (int[] d : dirs) {
        dfs(grid, r + d[0], c + d[1], visited);
    }
}

For “count islands”, you iterate over all cells; when you find an unvisited land cell, run DFS from it and increment a counter. Each DFS call marks one connected component.

Number of Islands

Given a 2D grid of '1' (land) and '0' (water), count the number of islands (connected land cells in 4 directions).

  • Idea: Scan every cell. When you see a '1' not yet visited, start a DFS (or BFS) from that cell to mark the whole island, then increment the count.
  • Visited: Use a separate visited[][] or mutate the grid in place (e.g. set grid[r][c] = '0' after visiting) to avoid revisiting.
Java
public int numIslands(char[][] grid) {
    int m = grid.length, n = grid[0].length;
    int count = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '1') {
                dfsMark(grid, r, c, m, n);
                count++;
            }
        }
    }
    return count;
}

void dfsMark(char[][] grid, int r, int c, int m, int n) {
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] != '1') return;
    grid[r][c] = '0';
    dfsMark(grid, r - 1, c, m, n);
    dfsMark(grid, r + 1, c, m, n);
    dfsMark(grid, r, c - 1, m, n);
    dfsMark(grid, r, c + 1, m, n);
}

Same idea works with BFS; you only care about marking the component, not path length.

Shortest Path in Binary Matrix

Given an n×n binary matrix, find the shortest path from (0,0) to (n-1, n-1) (only through 0 cells). Return the number of steps, or -1 if no path.

  • Idea: Plain BFS from (0,0). Neighbors are 4-adjacent cells with value 0. First time you reach (n-1, n-1) is the shortest step count.
  • Edge case: If start or end is 1, return -1.
Java
public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;

    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}, {-1,-1},{-1,1},{1,-1},{1,1}};
    boolean[][] visited = new boolean[n][n];
    Queue<int[]> q = new ArrayDeque<>();
    visited[0][0] = true;
    q.offer(new int[]{0, 0, 1});

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1], len = cur[2];
        if (r == n - 1 && c == n - 1) return len;

        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] == 0) {
                visited[nr][nc] = true;
                q.offer(new int[]{nr, nc, len + 1});
            }
        }
    }
    return -1;
}

Here we used 8 directions; the problem often allows diagonal moves. If only 4 directions are allowed, use the 4-direction dirs array.

Multi-Source BFS (Walls and Gates / Rotten Oranges)

When multiple cells are “sources” (e.g. all gates, or all rotten oranges), run one BFS by initializing the queue with all source cells at distance 0. The BFS expands in layers; each cell gets the distance to its nearest source.

Example: Walls and Gates — fill each empty room with the distance to the nearest gate. Gates and walls are given.

  • Initialize queue with all gate coordinates (r, c) and distance 0.
  • BFS: for each neighbor that is an empty room, set rooms[nr][nc] = d + 1 and enqueue (nr, nc, d+1).
  • No need for a separate visited if you only enqueue empty rooms and overwrite their value (they go from INF to a distance and are never enqueued again).
Java
public void wallsAndGates(int[][] rooms) {
    int m = rooms.length, n = rooms[0].length;
    Queue<int[]> q = new ArrayDeque<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (rooms[r][c] == 0) q.offer(new int[]{r, c, 0});
        }
    }
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};

    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1], d = cur[2];
        for (int[] dir : dirs) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && rooms[nr][nc] == Integer.MAX_VALUE) {
                rooms[nr][nc] = d + 1;
                q.offer(new int[]{nr, nc, d + 1});
            }
        }
    }
}

Flood Fill

Given a start cell and a new color, replace the connected component of the start cell’s color with the new color.

  • Idea: DFS or BFS from the start cell, only stepping to cells with the same color as the start. Replace color when visiting (or when enqueueing). If the new color equals the old color, no work (or avoid infinite recursion by checking and returning early).
Java
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    int old = image[sr][sc];
    if (old == color) return image;
    int m = image.length, n = image[0].length;
    dfsFill(image, sr, sc, m, n, old, color);
    return image;
}

void dfsFill(int[][] image, int r, int c, int m, int n, int old, int color) {
    if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != old) return;
    image[r][c] = color;
    dfsFill(image, r - 1, c, m, n, old, color);
    dfsFill(image, r + 1, c, m, n, old, color);
    dfsFill(image, r, c - 1, m, n, old, color);
    dfsFill(image, r, c + 1, m, n, old, color);
}

When to Use BFS vs DFS on Grids

GoalUse
Shortest number of steps (unweighted)BFS
Count connected components (islands, regions)DFS or BFS
Flood fill / mark one componentDFS or BFS
Multi-source shortest distancesMulti-source BFS

Implementation Tips

  • Row/column order: Be consistent. Usually grid[r][c] with r = row, c = column; (0,0) top-left.
  • Visited: Mark as soon as you enqueue (BFS) or enter (DFS) to avoid duplicate work.
  • Bounds: Centralize in a helper inBounds(r, c) or inline r >= 0 && r < m && c >= 0 && c < n.
  • Obstacles: Include in the neighbor condition (e.g. grid[nr][nc] != 1 for blocked).

Summary

  • Treat the grid as an implicit graph; generate neighbors with direction arrays and bounds checks.
  • BFS → shortest step count; DFS → explore or count components.
  • Multi-source BFS: initialize the queue with all sources at distance 0.
  • Classic problems: Number of Islands (DFS/BFS), Shortest Path in Binary Matrix (BFS), Flood Fill (DFS/BFS), Walls and Gates (multi-source BFS).

Once you are comfortable with 4-direction BFS/DFS and multi-source BFS, grid traversal problems follow the same patterns with small variations.