Breadth-First Search (BFS)

Intuition

Imagine pouring water onto one square of a tiled floor with some tiles blocked. The water spreads to all four neighboring tiles at once, then to their neighbors, and so on, flowing around obstacles. The moment the water touches the exit, the number of spreading rounds is the length of the shortest route. Grid BFS simulates that flood.

You never build an adjacency list. A cell (r, c) implicitly has up to four neighbors, (r-1, c), (r+1, c), (r, c-1) and (r, c+1), and you generate them with a small direction array. Walls and out-of-bounds coordinates are simply skipped. Everything else from Graph BFS carries over unchanged: a FIFO queue, mark on enqueue, distance equals the BFS round.

How it works step by step

1. Define dirs = {{-1,0},{1,0},{0,-1},{0,1}} for up, down, left and right.
2. Create a dist grid filled with -1. Set the start cell to 0 and push it onto the queue. For multi-source BFS, push every source cell with distance 0 before the loop starts.
3. Pop a cell. If it is the target, stop: its distance is the answer.
4. For each direction compute (nr, nc). Skip it if it is outside the grid, a wall, or already has a distance.
5. Otherwise set dist[nr][nc] = dist[r][c] + 1, store parent[nr][nc] = (r, c), and push it.
6. If the queue empties without reaching the target, it is unreachable; return -1.
7. To recover the route, start at the target and follow parent links back to the start, then reverse the list.

Dry run on a 3x3 maze

Grid rows are S . #, . # ., . . E, where # is a wall, S is (0,0) and E is (2,2). Directions are tried in the order up, down, left, right.

Following parents from E gives (2,2) ← (2,1) ← (2,0) ← (1,0) ← (0,0). Reversed, that is the 4-move path. Cell (1,2) is open but was never reached because the exit was found first, which shows how BFS stops as early as the answer allows.

Code

import java.util.*;

public class GridBFS {
    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // grid[r][c] == '#' is a wall. Returns the shortest path as a list of {r, c}, or empty.
    public static List<int[]> shortestPath(char[][] grid, int[] start, int[] end) {
        int rows = grid.length, cols = grid[0].length;
        int[][] parent = new int[rows * cols][];      // parent cell for each cell id
        boolean[][] seen = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(start);
        seen[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            if (cur[0] == end[0] && cur[1] == end[1]) {
                LinkedList<int[]> path = new LinkedList<>();
                for (int[] p = cur; p != null; p = parent[p[0] * cols + p[1]]) path.addFirst(p);
                return path;
            }
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                if (grid[nr][nc] == '#' || seen[nr][nc]) continue;
                seen[nr][nc] = true;
                parent[nr * cols + nc] = cur;
                queue.offer(new int[]{nr, nc});
            }
        }
        return Collections.emptyList();
    }
}

from collections import deque

DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))


def oranges_rotting(grid):
    """Multi-source BFS: every rotten orange starts in the queue at minute 0."""
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):          # one BFS level = one minute
            r, c = queue.popleft()
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2         # mark on enqueue
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1


print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))  # 4
print(oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))  # -1

The Java version is the single-source maze with path reconstruction; the Python version shows the multi-source pattern. Seeding the queue with all sources at once is equivalent to adding a virtual super-source connected to each of them, so every cell ends up with its distance to the nearest source.

Time and space complexity

Edge cases

• Start or end is a wall: return -1 immediately instead of running the search.
• Start equals end: distance 0, path of length one.
• No fresh oranges at all: the answer is 0 minutes, not -1; the while queue and fresh guard handles it.
• Fresh orange with no rotten neighbor anywhere: BFS finishes with fresh > 0, so return -1.
• 1 x N or N x 1 grids: the bounds checks matter; do not assume the grid is square.
• Diagonal moves allowed: problems like #1091 use 8 directions; extend the direction array instead of rewriting the loop.

Common mistakes

• Running a separate BFS from each source in a multi-source problem. That is O(k x R x C) and times out; seed one queue with all of them.
• Counting minutes with an extra increment after the last level, producing an answer one too large. Only count a level if it actually rotted something, or guard the loop as above.
• Marking cells on dequeue, which lets the same cell enter the queue from two neighbors in the same round.
• Storing parent pointers but forgetting to reverse the reconstructed path.
• Mutating the input grid when the caller still needs it; copy it or use a separate visited array.

Variations and when to use it

Use grid BFS for any minimum-steps question where each move costs one: escaping a maze, distance to the nearest gate, spreading fire or infection, knight moves on a chessboard. When the state includes more than position, such as how many walls you may still break or which keys you hold, the node becomes (r, c, extra) and the visited array gains a dimension, but the algorithm is unchanged. When moves have different costs, switch to Dijkstra's algorithm, and when you have a good distance estimate to the target, A* search expands far fewer cells.

Related LeetCode problems

• #994 Rotting Oranges — multi-source BFS where each level is one minute.
• #1926 Nearest Exit from Entrance in Maze — single-source BFS that stops at the first border cell other than the entrance.
• #1091 Shortest Path in Binary Matrix — the same BFS with 8 directions.
• #542 01 Matrix — seed every 0 cell and BFS outward to get each cell's distance to the nearest 0.
• #1162 As Far from Land as Possible — multi-source BFS from all land cells; the last level reached is the answer.
• #934 Shortest Bridge — mark one island, then BFS from all of its cells until the other island is hit.
• #1293 Shortest Path in a Grid with Obstacles Elimination — BFS over (row, col, eliminations left) states.

FAQ