Shortest Bridge – A BFS Story (with a Twist)

Here's another one from the Google 30 Days challenge on LeetCode — 934. Shortest Bridge. The goal? Given a 2D binary grid where two islands (groups of 1s) are separated by water (0s), flip the fewest number of 0s to 1s to connect them.

Easy to describe. Sneaky to implement well.

---

🧭 My Approach

My solution follows a two-phase Breadth-First Search (BFS) strategy:

1. Find and mark one island: I start by scanning the grid until I find the first 1, then use BFS to mark all connected land cells as 2. I store their positions for later use.

2. Bridge-building BFS: For each cell in the marked island, I run a BFS looking for the second island. Each BFS stops as soon as it hits a cell with value 1.

The minimum distance across all these searches gives the shortest bridge.

---

🔍 Code Snippet

Here's the core logic simplified:

public int ShortestBridge(int[][] grid)
{
    // 1. Mark one island as '2' and gather its coordinates
    List<int> island = FindAndMarkIsland(grid);

    // 2. For each coordinate in the first island, run BFS to second island
    int minBridge = int.MaxValue;
    foreach (var key in island)
    {
        int row = key / 105;
        int col = key % 105;
        minBridge = Math.Min(minBridge, BFS(grid, row, col));
    }

    return minBridge;
}

Each coordinate is encoded as row * 105 + col to avoid storing Tuple<int,int>. A cheap optimization I like using when performance matters.

---

📊 Time & Space Complexity

Let’s break this down:

Step	Time Complexity	Space Complexity
Marking island	O(NM)	O(NM)
BFS per cell	O(K × NM)	O(NM) per BFS
Worst-case	O((NM)²)	O(NM)

Where N = #rows, M = #cols, and K = number of cells in island.

This approach works fine for constraints on LeetCode, but…

---

💡 Optimization Opportunity

Instead of running a BFS from every cell in the first island, we could run one multi-source BFS from all island cells at once. This way:

• You expand the BFS frontier in parallel from the entire island.

• As soon as you reach the second island, you stop.

✅ Time Complexity: O(NM)

✅ Space Complexity: O(NM)

This is optimal and avoids the quadratic worst-case cost of repeated BFS traversals.

---

✍️ Final Thoughts

Sometimes you go with the brute force first — and that’s okay. It gets you a working solution. But then, you dig deeper and realize there’s a smarter way. That’s part of the fun.

Want the full code? Check it out here → LeetCode 934

---

Cheers, ACC