Shortest Bridge
Medium · Graphs · Explanation and code example
Disjoint Set Union + Breadth First Search
How it works
A Disjoint Set Union (DSU) data structure can identify connected components. By scanning the grid and unioning adjacent land cells, we naturally group cells into their respective islands.
Once we know which cells belong to the first island (tracked during the initial union phase), we start BFS from the boundary cells of that island. As we expand, we union newly visited cells with the first island. When a union operation connects to a cell that was already land (value 1) but in a different component, we have found the bridge.
Steps
- Initialize a
DSUwithn * n + 1elements. - Scan the grid, unioning adjacent land cells. Track the first island's root.
- Identify boundary cells of the first island (cells adjacent to water) and add them to the
BFSqueue. - Perform
BFS, expanding outward level by level:- For each cell, check all four neighbors.
- If a neighbor is land and unioning returns
true(different component), return the current distance. - If a neighbor is water, mark it as land, union with current cell, and add to queue.
- Increment distance after each level.
- Return the distance when the islands are connected.
Complexity
- Time complexity:
O(n ^ 2) - Space complexity:
O(n ^ 2)
Things to watch for
Not Marking Cells Before Adding to Queue
A common mistake is marking cells as visited only when dequeuing rather than when enqueuing. This causes the same cell to be added to the queue multiple times from different neighbors, leading to incorrect distance calculations and potential TLE. Always mark a cell as visited immediately when adding it to the BFS queue.
Confusing Island Detection with Bridge Finding
The DFS phase identifies all cells of the first island, while the BFS phase finds the shortest path to the second island. Mixing up these phases or using incorrect termination conditions (e.g., stopping DFS when finding any land cell) will produce wrong results. The BFS should return immediately upon reaching any cell with value 1 that was not part of the first island.
Incorrect Handling of the Return Value
When BFS reaches a cell of the second island, the current distance or steps counter represents the number of water cells flipped, which is the bridge length. Some implementations incorrectly return distance + 1 or forget that the starting cells of BFS (the first island's boundary) should not count toward the bridge length. The bridge length is the number of 0s between the islands, not including the island cells themselves.
Python code example
from collections import deque
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [1] * n
def find(self, node):
cur = node
while cur != self.parent[cur]:
self.parent[cur] = self.parent[self.parent[cur]]
cur = self.parent[cur]
return cur
def union(self, u, v):
pu, pv = self.find(u), self.find(v)
if pu == pv:
return False
if self.rank[pv] > self.rank[pu]:
pu, pv = pv, pu
self.parent[pv] = pu
self.rank[pu] += self.rank[pv]
return True
class Solution:
def shortestBridge(self, grid: list[list[int]]) -> int:
n, direct = len(grid), [(0, 1), (0, -1), (1, 0), (-1, 0)]
dsu = DSU(n * n + 1)
def idx(r, c):
return r * n + c + 1
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
first_island = dsu.find(idx(r, c))
if c + 1 < n and grid[r][c + 1] == 1:
dsu.union(idx(r, c), idx(r, c + 1))
if r + 1 < n and grid[r + 1][c] == 1:
dsu.union(idx(r, c), idx(r + 1, c))
q = deque()
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
if dsu.find(idx(r, c)) != first_island:
continue
for dx, dy in direct:
nr, nc = r + dx, c + dy
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
q.append((r,c))
break
res = 0
while q:
for _ in range(len(q)):
r, c = q.popleft()
for dx, dy in direct:
nr, nc = r + dx, c + dy
if 0 <= nr < n and 0 <= nc < n:
if grid[nr][nc] == 1 and dsu.union(idx(r, c), idx(nr, nc)):
return res
if grid[nr][nc] == 0:
grid[nr][nc] = 1
dsu.union(idx(r, c), idx(nr, nc))
q.append((nr, nc))
res += 1
C++ code example
class DSU {
public:
vector<int> parent, rank;
DSU(int n) : parent(n), rank(n, 1) {
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int node) {
if (parent[node] != node)
parent[node] = find(parent[node]);
return parent[node];
}
bool unionSet(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (rank[pv] > rank[pu]) swap(pu, pv);
parent[pv] = pu;
rank[pu] += rank[pv];
return true;
}
};
class Solution {
public:
int shortestBridge(vector<vector<int>>& grid) {
int N = grid.size();
vector<vector<int>> direct = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
DSU dsu(N * N + 1);
queue<pair<int, int>> q;
auto idx = [&](int r, int c) {
return r * N + c + 1;
};
int firstIsland = -1;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (grid[r][c] == 1) {
firstIsland = dsu.find(idx(r, c));
if (c + 1 < N && grid[r][c + 1] == 1)
dsu.unionSet(idx(r, c), idx(r, c + 1));
if (r + 1 < N && grid[r + 1][c] == 1)
dsu.unionSet(idx(r, c), idx(r + 1, c));
}
}
}
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (grid[r][c] == 1 && dsu.find(idx(r, c)) == firstIsland) {
for (auto& d : direct) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nc >= 0 && nr < N && nc < N && grid[nr][nc] == 0) {
q.push({r, c});
break;
}
}
}
}
}
int res = 0;
while (!q.empty()) {
for (int i = q.size(); i > 0; i--) {
auto [r, c] = q.front();q.pop();
for (auto& d : direct) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nc >= 0 && nr < N && nc < N) {
if (grid[nr][nc] == 1 && dsu.unionSet(idx(r, c), idx(nr, nc)))
return res;
if (grid[nr][nc] == 0) {
grid[nr][nc] = 1;
dsu.unionSet(idx(r, c), idx(nr, nc));
q.push({nr, nc});
}
}
}
}
res++;
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.