# Shortest Bridge
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shortest-bridge)
Canonical: https://scaleengineer.com/dsa/problems/shortest-bridge
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [Flipkart](https://scaleengineer.com/companies/flipkart), [Coupang](https://scaleengineer.com/companies/coupang), [Snap](https://scaleengineer.com/companies/snap), [McKinsey](https://scaleengineer.com/companies/mckinsey)
---
## Problem
You are given an `n x n` binary matrix `grid` where `1` represents land and `0` represents water.

An **island** is a 4-directionally connected group of `1`'s not connected to any other `1`'s. There are **exactly two islands** in `grid`.

You may change `0`'s to `1`'s to connect the two islands to form **one island**.

Return _the smallest number of_ `0`_'s you must flip to connect the two islands_.

**Example 1:**

**Input:** grid = [[0,1],[1,0]]
**Output:** 1

**Example 2:**

**Input:** grid = [[0,1,0],[0,0,0],[0,0,1]]
**Output:** 2

**Example 3:**

**Input:** grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
**Output:** 1

**Constraints:**

* `n == grid.length == grid[i].length`
* `2 <= n <= 100`
* `grid[i][j]` is either `0` or `1`.
* There are exactly two islands in `grid`.

# Approaches
## Brute Force: Pairwise Distance Calculation
This approach first identifies all cells belonging to each of the two islands. Then, it calculates the Manhattan distance between every possible pair of cells, one from each island. The minimum of these distances minus one gives the shortest bridge length.
**Time:** O(N^4), where N is the side length of the grid. Finding the islands takes O(N^2). If the islands have sizes S1 and S2, the pairwise distance calculation takes O(S1 * S2). In the worst case, S1 and S2 can be on the order of O(N^2), leading to a total time complexity of O(N^4). · **Space:** O(N^2), where N is the side length of the grid. This space is used to store the coordinates of the islands and for the recursion stack of the DFS.
**Pros:** Conceptually simple and easy to understand.
**Cons:** Extremely inefficient with a time complexity of O(N^4), which will time out for the given constraints.; The Manhattan distance calculation is a naive heuristic that doesn't account for the actual path through water, though it works for this specific problem where the goal is just to find the minimum number of flips.
### Explanation
This method involves two main steps. First, we locate and separate the two islands. We can do this by iterating through the grid. When we encounter a '1', we perform a traversal like DFS to find all connected '1's, which form an island. We store the coordinates of this island's cells in a list. We repeat this process to find the second island and store its cells in another list.

Once we have the coordinates of all cells for both islands, we calculate the shortest distance. We iterate through every cell in the first island and every cell in the second island, calculating the Manhattan distance between each pair. The Manhattan distance between `(r1, c1)` and `(r2, c2)` is `|r1 - r2| + |c1 - c2|`. The number of 0's we need to flip is this distance minus one. We keep track of the minimum distance found across all pairs. This minimum value is our answer.

While straightforward, this approach is computationally expensive. The number of pairs can be very large if the islands are big, leading to a high time complexity.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        List<int[]> island1 = new ArrayList<>();
        List<int[]> island2 = new ArrayList<>();
        boolean[][] visited = new boolean[n][n];
        int islandCount = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    List<int[]> currentIsland = new ArrayList<>();
                    findIsland(i, j, n, grid, visited, currentIsland);
                    if (islandCount == 0) {
                        island1 = currentIsland;
                    } else {
                        island2 = currentIsland;
                    }
                    islandCount++;
                }
            }
        }

        int minDistance = Integer.MAX_VALUE;
        for (int[] cell1 : island1) {
            for (int[] cell2 : island2) {
                int dist = Math.abs(cell1[0] - cell2[0]) + Math.abs(cell1[1] - cell2[1]) - 1;
                minDistance = Math.min(minDistance, dist);
            }
        }
        return minDistance;
    }

    private void findIsland(int r, int c, int n, int[][] grid, boolean[][] visited, List<int[]> island) {
        if (r < 0 || r >= n || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {
            return;
        }
        visited[r][c] = true;
        island.add(new int[]{r, c});
        findIsland(r + 1, c, n, grid, visited, island);
        findIsland(r - 1, c, n, grid, visited, island);
        findIsland(r, c + 1, n, grid, visited, island);
        findIsland(r, c - 1, n, grid, visited, island);
    }
}
```
### Algorithm
- Create two lists, `island1` and `island2`, to store the coordinates of the cells for each island.
- Iterate through the `grid`. If a cell `(r, c)` contains a `1` and has not been visited:
    - Perform a Depth First Search (DFS) or Breadth First Search (BFS) starting from `(r, c)` to find all connected land cells.
    - Add all found cells to the appropriate island list (`island1` if it's the first one found, `island2` otherwise). Mark these cells as visited.
- Initialize `min_distance` to a very large value.
- Iterate through each cell `(r1, c1)` in `island1`.
- Inside this loop, iterate through each cell `(r2, c2)` in `island2`.
- Calculate the Manhattan distance: `dist = abs(r1 - r2) + abs(c1 - c2) - 1`.
- Update `min_distance = min(min_distance, dist)`.
- Return `min_distance`.

## Two-Phase Traversal: DFS + Multi-Source BFS
This is a highly efficient approach that solves the problem in two main phases. First, it uses a graph traversal algorithm like DFS or BFS to find one of the islands and mark its cells. Second, it performs a multi-source BFS starting simultaneously from all the cells of the found island to find the shortest path to the second island.
**Time:** O(N^2), where N is the side length of the grid. The first phase (DFS) visits each cell at most once. The second phase (multi-source BFS) also visits each cell at most once. Therefore, the total time complexity is linear in the number of cells in the grid. · **Space:** O(N^2), where N is the side length of the grid. The space is dominated by the queue used for the BFS, which in the worst case can store all the cells of the grid.
**Pros:** Optimal time complexity, making it very efficient for the given constraints.; Guarantees finding the shortest path because BFS explores level by level.
**Cons:** Slightly more complex to implement than the brute-force approach due to the two-phase nature.; Modifies the input grid, which might not be desirable in some contexts (though a copy can be made or a separate `visited` array can be used to avoid this).
### Explanation
This optimal approach breaks the problem into two parts: finding an island and then finding the shortest path from it to the other island.

**Phase 1: Island Identification (using DFS)**
First, we traverse the grid to find any land cell (`1`). Once we find one, we start a Depth-First Search (DFS) from that cell to identify all the cells belonging to the first island. During this DFS, we perform two key actions:
1.  We change the value of each cell of this island from `1` to `2`. This helps us distinguish it from the second island and also marks it as visited for the next phase.
2.  We add the coordinates of each of these cells to a queue. This queue will serve as the starting set of nodes for our multi-source BFS.

**Phase 2: Shortest Path Search (using Multi-Source BFS)**
With the queue populated with all the cells of the first island, we begin a Breadth-First Search. BFS is ideal here because it explores the grid layer by layer, guaranteeing that we find the shortest path in terms of "steps" (which, in our case, are the water cells we flip).
We maintain a `distance` variable, initialized to 0. The BFS proceeds in levels. In each level, we dequeue all the cells that were added in the previous level and explore their neighbors.
- If a neighbor is a water cell (`0`), we mark it as visited (by changing it to `2`) and add it to the queue for the next level.
- If a neighbor is a land cell of the second island (`1`), we have found the shortest connection. The current `distance` is the number of water cells we had to traverse (and flip) to get here. We can immediately return this `distance`.
After exploring all cells at a level, we increment the `distance` and proceed to the next level.

This combination of DFS and multi-source BFS is efficient because each cell in the grid is processed a constant number of times.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        Queue<int[]> queue = new LinkedList<>();
        boolean found = false;

        // 1. DFS to find the first island and add its cells to the queue
        for (int i = 0; i < n; i++) {
            if (found) break;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, n, queue);
                    found = true;
                    break;
                }
            }
        }

        // 2. BFS to find the shortest path to the second island
        int distance = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] cell = queue.poll();
                int r = cell[0];
                int c = cell[1];

                for (int[] dir : dirs) {
                    int nr = r + dir[0];
                    int nc = c + dir[1];

                    if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                        if (grid[nr][nc] == 1) {
                            // Found the second island
                            return distance;
                        }
                        if (grid[nr][nc] == 0) {
                            // Mark as visited and add to queue
                            grid[nr][nc] = 2;
                            queue.offer(new int[]{nr, nc});
                        }
                    }
                }
            }
            distance++;
        }

        return -1; // Should not be reached given the problem constraints
    }

    private void dfs(int[][] grid, int r, int c, int n, Queue<int[]> queue) {
        if (r < 0 || r >= n || c < 0 || c >= n || grid[r][c] != 1) {
            return;
        }
        // Mark as visited (part of the first island)
        grid[r][c] = 2;
        queue.offer(new int[]{r, c});

        dfs(grid, r + 1, c, n, queue);
        dfs(grid, r - 1, c, n, queue);
        dfs(grid, r, c + 1, n, queue);
        dfs(grid, r, c - 1, n, queue);
    }
}
```
### Algorithm
- **Phase 1: Find and Mark the First Island**
    - Iterate through the `grid` to find the first land cell (`1`).
    - Once a land cell is found, start a DFS (or BFS) from this cell.
    - During the DFS:
        - Change the value of the visited island cells from `1` to `2` to mark them.
        - Add the coordinates of each cell of this island to a queue.
    - Stop the initial grid scan once the first island is fully processed.
- **Phase 2: Multi-Source BFS for Shortest Bridge**
    - Initialize a `distance` counter to `0`.
    - While the queue is not empty, perform a level-by-level BFS:
        - Get the number of nodes at the current level (`level_size`).
        - Loop `level_size` times to process all nodes at this level.
        - Dequeue a cell `(r, c)`.
        - Explore its 4-directional neighbors `(nr, nc)`.
        - For each valid neighbor:
            - If `grid[nr][nc]` is `1`, the second island is reached. Return the current `distance`.
            - If `grid[nr][nc]` is `0`, mark it as visited (e.g., set `grid[nr][nc] = 2`) and enqueue it.
        - After processing all nodes at the current level, increment `distance`.

# Solutions
### Java

```java
class Solution {
private
  int[] dirs = {-1, 0, 1, 0, -1};
private
  Deque<int[]> q = new ArrayDeque<>();
private
  int[][] grid;
private
  int n;
public
  int shortestBridge(int[][] grid) {
    this.grid = grid;
    n = grid.length;
    for (int i = 0, x = 1; i < n && x == 1; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          dfs(i, j);
          x = 0;
          break;
        }
      }
    }
    int ans = 0;
    while (true) {
      for (int i = q.size(); i > 0; --i) {
        var p = q.pollFirst();
        for (int k = 0; k < 4; ++k) {
          int x = p[0] + dirs[k], y = p[1] + dirs[k + 1];
          if (x >= 0 && x < n && y >= 0 && y < n) {
            if (grid[x][y] == 1) {
              return ans;
            }
            if (grid[x][y] == 0) {
              grid[x][y] = 2;
              q.offer(new int[]{x, y});
            }
          }
        }
      }
      ++ans;
    }
  }
private
  void dfs(int i, int j) {
    grid[i][j] = 2;
    q.offer(new int[]{i, j});
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
        dfs(x, y);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  const static inline vector<int> dirs = {-1, 0, 1, 0, -1};
  int shortestBridge(vector<vector<int>> &grid) {
    int n = grid.size();
    queue<pair<int, int>> q;
    function<void(int, int)> dfs = [&](int i, int j) {
      grid[i][j] = 2;
      q.emplace(i, j);
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < n && y >= 0 && y < n && grid[x][y] == 1) {
          dfs(x, y);
        }
      }
    };
    for (int i = 0, x = 1; i < n && x; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j]) {
          dfs(i, j);
          x = 0;
          break;
        }
      }
    }
    int ans = 0;
    while (1) {
      for (int h = q.size(); h; --h) {
        auto [i, j] = q.front();
        q.pop();
        for (int k = 0; k < 4; ++k) {
          int x = i + dirs[k], y = j + dirs[k + 1];
          if (x >= 0 && x < n && y >= 0 && y < n) {
            if (grid[x][y] == 1)
              return ans;
            if (grid[x][y] == 0) {
              grid[x][y] = 2;
              q.emplace(x, y);
            }
          }
        }
      }
      ++ans;
    }
  }
};

```

### Python

```python
class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int: def dfs(i, j): q . append((i, j)) grid[i][j] = 2 for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < n and 0 <= y < n and grid[x][y] == 1: dfs(x, y) n = len(grid) dirs = (- 1, 0, 1, 0, - 1) q = deque() i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j]) dfs(i, j) ans = 0 while 1: for _ in range(len(q)): i, j = q . popleft() for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < n and 0 <= y < n: if grid[x][y] == 1: return ans if grid[x][y] == 0: grid[x][y] = 2 q . append((x, y)) ans += 1

```