The O(n) Club: Shortest Bridge — When DFS and BFS Join Forces (and Regret It Immediately)

The O(n) Club: Shortest Bridge — When DFS and BFS Join Forces (and Regret It Immediately)

⚡ TL;DR

Connect two islands in a binary grid by flipping the fewest possible water cells. Mark one island with DFS, then let BFS storm the boundaries to build the shortest bridge. Pro tip: brute force makes your CPU cry.

// Brute force, aka "please no one ever do this"
for every water cell:
    flip it and check if the islands connect
// Time complexity: O(N^4). Interviewer: "...next!"

🧠 How Devs Usually Mess This Up

Some folks treat BFS and DFS like magic spells: cast one, cross fingers, hope for the best. But if you don’t start BFS from every edge of your first island, you’ll get bridges looping in circles—or worse, infinite loops if you forget to mark visited cells. And if you only use DFS, good luck getting shortest distances—DFS is the master of getting lost in mazes. Using only one approach here is like making a sandwich without bread—you’ll end up with a sticky mess and nowhere to put the cheese.

🔍 What’s Actually Going On

Picture your grid as a bunch of binary Lego floating in a bathtub. You’ve got two islands (clusters of 1s) and a bunch of water (0s) in-between. Your job: build the world’s shortest bridge by flipping as few zeros to ones as possible. Step 1 is finding one island and marking it as “mine” (think DFS with claim-staking), then queuing up all its land edges. Step 2, launch a BFS outwards from those edges: each layer is a new row of bridge. As soon as you touch the second island with your expanding ‘bridge’, you shout “land ho!” and return the number of flips it took.

🛠️ PseudoCode

• Find a land cell:
  • Wander until you hit a 1. That’s your VIP island entry point.

  // Find one island
  for each cell in grid:
      if grid[i][j] == 1:
          start DFS from (i, j)
          break;

• DFS Marking:
  • Recursively label all connected 1s as visited (or, if you’re spicy, change to 2). Add every marked cell to a queue for later BFS shenanigans.

  // Mark first island via DFS
  dfs(i,j):
      if out of bounds or not 1 or already visited: return
      mark visited (or grid[i][j]=2)
      add (i,j) to queue
      repeat for four directions

• BFS Bridge Building:
  • From your queue of island edge cells, expand outward level by level. Each BFS level = one extra water cell flipped. The second you reach a 1 that’s not on your island, you’re done.

  // Build bridge with BFS
  while queue not empty:
      for each cell in current BFS layer:
          for dir in {up, down, left, right}:
              if it's water and not visited:
                  mark visited
                  add to queue
              if it's 1 and not marked by DFS:
                  return current bridge length

💻 The Code

class Solution {
    private static final int[][] DIRS = {{0,1},{1,0},{0,-1},{-1,0}};
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Queue<int> queue = new LinkedList<>();
        boolean found = false;
        for (int i = 0; i < n && !found; i++) {
            for (int j = 0; j < n && !found; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, visited, queue, i, j);
                    found = true;
                }
            }
        }
        int bridgeLen = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                int[] curr = queue.poll();
                for (int[] d : DIRS) {
                    int ni = curr[0] + d[0], nj = curr[1] + d[1];
                    if (ni < 0 || nj < 0 || ni >= n || nj >= n || visited[ni][nj]) continue;
                    if (grid[ni][nj] == 1) return bridgeLen;
                    visited[ni][nj] = true;
                    queue.offer(new int[]{ni, nj});
                }
            }
            bridgeLen++;
        }
        return -1; // If your islands somehow floated away
    }
    private void dfs(int[][] grid, boolean[][] visited, Queue<int> queue, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || visited[i][j] || grid[i][j] != 1) return;
        visited[i][j] = true;
        queue.offer(new int[]{i, j});
        for (int[] d : DIRS) {
            dfs(grid, visited, queue, i + d[0], j + d[1]);
        }
    }
}</int></int>

⚠️ Pitfalls, Traps & Runtime Smacks

• Boundary bloopers: Forgetting to start BFS from every single island edge cell means your bridge could be comically long or just…never show up.
• Visited confusion: Mark every cell you touch; otherwise, you’ll cycle between water and land like a stuck submarine.
• Input shenanigans: This only works if there are exactly two islands. Grid with three? Chaos. One? Sadness.
• Performance: DFS and BFS both visit O(N^2) cells, which is about as good as it gets when you’re island-hopping.

🧠 Interviewer Brain-Tattoo

DFS discovers your turf; BFS gets you across. Want the shortest bridge? Don’t let DFS drive — hand BFS the keys, and hope nobody asks about vacation days.