Shortest Bridge

Shortest Bridge

What is this problem about?

The Shortest Bridge interview question gives you a binary matrix containing exactly two islands (connected groups of 1s). Find the minimum number of 0-cells that must be flipped to 1 to connect the two islands — in other words, find the shortest bridge between them. The answer is the minimum number of cells separating the two islands, which equals the BFS distance minus 1.

Why is this asked in interviews?

Apple, Uber, Microsoft, Meta, Amazon, Google, Bloomberg, and TikTok ask this problem because it combines DFS island discovery with multi-source BFS for minimum distance — two fundamental graph patterns chained together. It tests the ability to decompose a problem into sequential phases and apply different graph algorithms at each phase. The pattern models shortest-path problems in grid navigation, circuit board routing, and network topology.

Algorithmic pattern used

The pattern is DFS to mark one island + multi-source BFS to find the shortest path to the second island. Phase 1: find any '1' cell, then use DFS/BFS to discover and mark all cells of the first island, adding them to a queue. Phase 2: multi-source BFS from all cells of the first island simultaneously, expanding outward level by level. The first time you reach a '1' cell not belonging to the first island, the current BFS level (number of steps taken) is the answer.

Example explanation

Matrix:

0 1 0 0 0
0 1 0 0 0
0 0 0 1 1
0 0 0 1 0

Island 1: cells (0,1),(1,1). Island 2: cells (2,3),(2,4),(3,3).

BFS from island 1:

• Level 0: (0,1),(1,1).
• Level 1: neighbors: (0,0),(0,2),(1,0),(1,2),(2,1).
• Level 2: expand further...
• First island 2 cell reached at level 2: (2,3)? Path: (1,1)→(2,1)→(2,2)→(2,3) = 2 flips.

Common mistakes candidates make

• Not separating the two islands clearly before BFS — must mark which island is "source" to avoid treating its cells as targets.
• Using DFS for the second phase (distance search) instead of BFS — DFS doesn't guarantee shortest distance.
• Revisiting cells during BFS — mark cells as visited when added to the queue, not when processed.
• Starting BFS from only one cell of the first island instead of all cells (multi-source).

Interview preparation tip

For the Shortest Bridge coding problem, the DFS BFS matrix interview pattern in two phases is the approach. The key: multi-source BFS (starting from all cells of island 1 simultaneously) is crucial for finding the correct minimum. TikTok and Tesla interviewers test this exact two-phase structure. Practice the "DFS to mark, then BFS to measure" template — it applies to many grid problems where you identify a source region first, then find the shortest path to a target region.