Shortest Bridge

Medium Graphs Multi source BFS Original on LeetCode

Shortest Bridge is a medium graphs problem solved with the multi source bfs pattern. The best approach, optimal (flood fill + multi-source bfs), runs in O(n²) time and O(n²) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (closest pair of cells) up.

Problem

You are given an n x n binary grid where 1 is land and 0 is water. Land cells that share an edge (up, down, left, right) belong to the same island, and the grid contains exactly two islands.

You may turn water cells into land. Return the smallest number of water cells you must flip so that the two islands become one connected island.

Examples

Example 1

Input
grid = [[1, 0, 0], [0, 0, 0], [0, 0, 1]]
Output
3
Why
The two single-cell islands are at the corners. Flipping three water cells, for example (0, 1), (0, 2) and (1, 2), connects them; two flips are not enough.

Example 2

Input
grid = [[1, 1, 0, 0], [1, 0, 0, 0], [0, 0, 1, 1], [0, 0, 1, 0]]
Output
2
Why
Flipping (1, 1) and (1, 2) links (0, 1) of the top-left island to (2, 2) of the other one. No single water cell touches both islands.

Example 3

Input
grid = [[0, 1], [1, 0]]
Output
1
Why
The two cells only touch diagonally, which does not count. Flipping either water cell joins them.

Constraints

  • n == grid.length == grid[i].length
  • 2 <= n <= 100
  • grid[i][j] is 0 or 1.
  • There are exactly two islands (4-directionally connected groups of 1s).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (closest pair of cells)O(n⁴)O(n²)
Optimal (flood fill + multi-source BFS)O(n²)O(n²)

1Brute force (closest pair of cells)

TimeO(n⁴)Each island can have about n² / 2 cells, so the pair loop is quadratic in the number of cells.
SpaceO(n²)The two cell lists and the flood-fill stack.

Label the two islands with a flood fill. The bridge needed between a cell a of the first island and a cell b of the second is |ra - rb| + |ca - cb| - 1 water cells; for the closest pair, every cell on a monotone path between them is water (otherwise there would be a closer pair). So the answer is the minimum of that value over all pairs.

  1. Flood fill from the first land cell found; collect island A. Collect every other land cell as island B.
  2. For every a in A and b in B, answer = min(answer, |ra - rb| + |ca - cb| - 1).
class Solution {
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        boolean[][] inA = new boolean[n][n];
        List<int[]> a = new ArrayList<>(), b = new ArrayList<>();
        outer:
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    fill(grid, r, c, inA, a);
                    break outer;
                }
            }
        }
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                if (grid[r][c] == 1 && !inA[r][c]) b.add(new int[] { r, c });
        int best = Integer.MAX_VALUE;
        for (int[] p : a)
            for (int[] q : b)
                best = Math.min(best, Math.abs(p[0] - q[0]) + Math.abs(p[1] - q[1]) - 1);
        return best;
    }

    private void fill(int[][] grid, int sr, int sc, boolean[][] inA, List<int[]> cells) {
        int n = grid.length;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        Deque<int[]> stack = new ArrayDeque<>();
        inA[sr][sc] = true;
        stack.push(new int[] { sr, sc });
        while (!stack.isEmpty()) {
            int[] cur = stack.pop();
            cells.add(cur);
            for (int[] d : dirs) {
                int r = cur[0] + d[0], c = cur[1] + d[1];
                if (r >= 0 && r < n && c >= 0 && c < n && grid[r][c] == 1 && !inA[r][c]) {
                    inA[r][c] = true;
                    stack.push(new int[] { r, c });
                }
            }
        }
    }
}

2Optimal (flood fill + multi-source BFS)

TimeO(n²)Every cell is visited at most once by the flood fill and once by the BFS.
SpaceO(n²)The visited grid and the queue.

Flood fill the first island and mark its cells as visited; put all of them in a BFS queue at distance 0. Expand the BFS one layer at a time through water. The first time a layer steps onto an unvisited land cell, that cell belongs to the second island, and the current layer number is the number of water cells flipped.

  1. Find any land cell; flood fill its island, marking cells visited and adding them to the queue.
  2. steps = 0. While the queue is not empty: process the whole current layer.
  3. For each neighbour in bounds and not visited: if it is land, return steps; otherwise mark it and enqueue it.
  4. After the layer, steps++.
class Solution {
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        boolean[][] seen = new boolean[n][n];
        Deque<int[]> queue = new ArrayDeque<>();
        Deque<int[]> stack = new ArrayDeque<>();
        outer:
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    seen[r][c] = true;
                    stack.push(new int[] { r, c });
                    break outer;
                }
            }
        }
        while (!stack.isEmpty()) {
            int[] cur = stack.pop();
            queue.add(cur);
            for (int[] d : dirs) {
                int r = cur[0] + d[0], c = cur[1] + d[1];
                if (r >= 0 && r < n && c >= 0 && c < n && grid[r][c] == 1 && !seen[r][c]) {
                    seen[r][c] = true;
                    stack.push(new int[] { r, c });
                }
            }
        }
        int steps = 0;
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; size--) {
                int[] cur = queue.poll();
                for (int[] d : dirs) {
                    int r = cur[0] + d[0], c = cur[1] + d[1];
                    if (r < 0 || r >= n || c < 0 || c >= n || seen[r][c]) continue;
                    if (grid[r][c] == 1) return steps;
                    seen[r][c] = true;
                    queue.add(new int[] { r, c });
                }
            }
            steps++;
        }
        return -1;
    }
}

Edge cases to test

  • Islands that touch only diagonally (still need one flip)
  • Islands on opposite corners of the grid
  • One island wrapping around the other, so the shortest bridge is not along a straight row or column
  • Large islands: the cost of checking every pair of land cells grows quickly

Hints

Hint 1

First tell the two islands apart: flood fill from any land cell to collect the whole first island.

Hint 2

The answer is the shortest distance, through water, from the first island to the second. Which traversal finds shortest distances on a grid?

Hint 3

Start a BFS from every cell of the first island at once (distance 0) and expand layer by layer until you step onto a cell of the second island.

FAQ

What is the best time complexity for Shortest Bridge?

Optimal (flood fill + multi-source BFS) runs in O(n²) time and O(n²) extra space. Every cell is visited at most once by the flood fill and once by the BFS.

Which pattern does Shortest Bridge use?

It is a graphs problem that uses the multi source bfs pattern. Other problems with the same pattern: Rotting Oranges, 01 Matrix, Pacific Atlantic Water Flow.

Is there a brute force solution for Shortest Bridge?

Yes. Brute force (closest pair of cells) takes O(n⁴) time and O(n²) space. Label the two islands with a flood fill.

Which edge cases should I test for Shortest Bridge?

Islands that touch only diagonally (still need one flip); Islands on opposite corners of the grid; One island wrapping around the other, so the shortest bridge is not along a straight row or column; Large islands: the cost of checking every pair of land cells grows quickly.