Shortest Bridge: DFS Plus BFS on a Grid

You are given an n x n binary matrix where 1 represents land and 0 represents water. There are exactly two islands in the grid. An island is a maximal group of 1s connected in the four cardinal directions (up, down, left, right). Return the smallest number of 0s you must flip to 1s to connect the two islands.

This is LeetCode 934: Shortest Bridge, and it is the problem that teaches you to combine DFS and BFS in a single algorithm. You use DFS to discover one island, then multi-source BFS to find the shortest path to the other. Two tools, one clean solution.

Why this problem matters

Most grid problems use either DFS or BFS. This one uses both, and each for a different purpose. DFS handles the "find and mark a connected component" part. BFS handles the "find the shortest distance" part. Once you see that split, the algorithm falls into place.

The underlying idea, multi-source BFS for shortest distance, appears in many other problems: Rotting Oranges, Walls and Gates, 01 Matrix. Shortest Bridge is a great place to learn it because the setup is concrete and the two phases are clearly separated.

The two-phase approach

The algorithm has two distinct phases:

Phase 1: Find one island with DFS. Scan the grid until you hit a 1. Run DFS from that cell to discover every cell in that island. Mark each cell as visited and add it to a BFS queue with distance 0.

Phase 2: Multi-source BFS to the other island. Process the queue. For each cell, check all four neighbors. If a neighbor is unvisited water, mark it visited and add it to the queue with distance + 1. If a neighbor is an unvisited 1 (the second island), return the current distance immediately.

The BFS guarantees that the first time you reach the second island, you have found the shortest path. That is the fundamental property of BFS on unweighted graphs: the first visit is always via the shortest path.

The solution

from collections import deque

def shortestBridge(grid):
    n = len(grid)
    visited = [[False] * n for _ in range(n)]
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    queue = deque()

    def dfs(r, c):
        visited[r][c] = True
        queue.append((r, c, 0))
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 1:
                dfs(nr, nc)

    found = False
    for i in range(n):
        if found:
            break
        for j in range(n):
            if grid[i][j] == 1:
                dfs(i, j)
                found = True
                break

    while queue:
        r, c, dist = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
                if grid[nr][nc] == 1:
                    return dist
                visited[nr][nc] = True
                queue.append((nr, nc, dist + 1))

    return -1

Let's walk through the key pieces.

The DFS function marks a cell as visited and adds it to the BFS queue with distance 0. Then it recurses into all valid, unvisited land neighbors. When DFS finishes, every cell in the first island is in the queue, all at distance 0. That is the "multi-source" setup.

The scanning loop finds the first 1 in the grid, calls DFS on it, then breaks. We only need to find one island. The other island will be discovered by BFS.

The BFS loop processes cells in order of increasing distance. For each cell, it checks all four neighbors. If a neighbor is unvisited and is land (value 1), that means we have reached the second island, and the current dist is the answer. If the neighbor is unvisited water, we mark it visited and enqueue it with dist + 1.

Visual walkthrough

Let's trace through the algorithm step by step on a 5x5 grid.

The DFS phase discovers island A (three cells in the top-left). All three go into the BFS queue at distance 0. Then BFS expands outward, one level at a time. At distance 3, the frontier touches a cell of island B. Answer: 3.

Complexity analysis

Time is O(n^2). The DFS visits every cell of the first island once. The BFS visits every cell in the grid at most once. Together, they touch at most n^2 cells.

Space is O(n^2) for the visited matrix and the BFS queue. In the worst case, the queue can hold all n^2 cells (if one island is a single cell in the corner and the other spans the opposite corner).

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

1. DFS flood fill for island marking

The same pattern from Number of Islands: scan until you find a 1, then DFS to mark every connected land cell. The only twist here is that instead of just marking cells, you also add them to a BFS queue for the next phase.

def dfs(r, c):
    visited[r][c] = True
    queue.append((r, c, 0))  # seed for BFS
    for dr, dc in directions:
        nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] == 1:
            dfs(nr, nc)

This is flood fill with a side effect. Every cell you visit gets added to the BFS queue. That dual-purpose DFS is the glue between the two phases.

2. Multi-source BFS for shortest distance

Instead of starting BFS from a single cell, you seed the queue with an entire set of cells, all at distance 0. Then BFS expands from all of them simultaneously, level by level. The first time you reach a target, the BFS level is the shortest distance from any source.

while queue:
    r, c, dist = queue.popleft()
    for dr, dc in directions:
        nr, nc = r + dr, c + dc
        if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc]:
            if grid[nr][nc] == 1:
                return dist
            visited[nr][nc] = True
            queue.append((nr, nc, dist + 1))

Multi-source BFS is the same as regular BFS. The only difference is the initialization: instead of one cell at distance 0, you start with many. The BFS logic does not change at all.

Edge cases

Before submitting, check these:

• Islands touching the grid border: the islands can be anywhere, including along edges and corners. The bounds check 0 <= nr < n and 0 <= nc < n handles this.
• Islands separated by one cell of water: the answer is 1. BFS returns at the first expansion level.
• Islands adjacent (distance 0): this cannot happen because the problem guarantees exactly two distinct islands, meaning they are not connected.
• Large grid with tiny islands: even if each island is a single cell in opposite corners of a 100x100 grid, the BFS will find the shortest path. It is still O(n^2).
• Recursion depth for DFS: if one island has many cells, recursive DFS can hit Python's stack limit. For safety, convert DFS to an iterative stack version. The algorithm is the same.

From understanding to recall

You now see how DFS and BFS split the work cleanly. DFS discovers the first island and seeds the BFS queue. BFS expands outward until it reaches the second island. The BFS level at first contact is the answer.

But can you reproduce the two-phase structure from scratch under pressure? The details that trip people up: remembering to add DFS cells to the BFS queue during the DFS, returning dist (not dist + 1) when you hit the second island, and the multi-source BFS initialization. These are recall challenges, not conceptual ones.

Spaced repetition closes that gap. You practice writing the DFS-to-BFS handoff and the multi-source BFS loop from memory at increasing intervals. After a few rounds, the two-phase pattern becomes automatic. You see a "connect two components" problem, and the DFS-plus-BFS skeleton flows out without hesitation.

Related posts

• Number of Islands - The foundational DFS flood fill pattern that Phase 1 of this problem builds on
• Pacific Atlantic Water Flow - Another two-pass grid problem using multi-source DFS from borders
• Making a Large Island - A harder island-connection problem that builds on the same DFS component-labeling technique

CodeBricks breaks Shortest Bridge into its DFS-flood-fill and multi-source-BFS building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid connectivity problem shows up in your interview, you do not think about it. You just write it.