#934

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Shortest Bridge

Find the minimum flips to connect two separate islands in a binary matrix using Array and DFS techniques efficiently.

array depth first search breadth first search matrix

Problem Statement

You are given an n x n binary matrix where 1 represents land and 0 represents water. There are exactly two islands, each formed by 4-directionally connected 1's. Your task is to find the minimal number of 0's that must be flipped to 1's to connect the two islands, forming a single island.

Implement a solution that identifies one island, explores its boundaries, and efficiently bridges the gap to the second island using the minimal path. The matrix size is constrained, so the solution must carefully manage traversal and avoid revisiting cells while capturing the shortest connection.

Examples

Example 1

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

Output: 1

Example details omitted.

Example 2

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

Output: 2

Example details omitted.

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

Example details omitted.

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.

Solution Approach

Identify One Island via DFS

Traverse the grid to locate the first 1, then perform Depth-First Search to mark all connected land cells. Collect their coordinates for the BFS expansion phase. This ensures the starting island is fully mapped and prevents reprocessing in subsequent steps.

Expand Using BFS

Initialize a queue with all coordinates from the first island and perform Breadth-First Search into neighboring water cells. Increment a distance counter for each layer, stopping when the second island is reached. This guarantees the minimal number of flips to connect both islands.

Track Visited Cells and Distance

Maintain a visited matrix to avoid revisiting cells during BFS. Update distances only when expanding into new water cells. Proper bookkeeping ensures efficiency and avoids failure modes where BFS could circle back to the first island or miscount steps.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(n^2)

Time complexity is O(n^2) because DFS visits all cells of the first island and BFS potentially visits every cell in the grid. Space complexity is O(n^2) to store visited flags and the BFS queue for the island boundaries.

What Interviewers Usually Probe

Expect you to recognize the two-island pattern in the grid and articulate an efficient search strategy.
They may hint at using DFS first to mark the island before attempting BFS expansion.
They look for correct distance measurement while handling matrix boundaries and visited checks.

Common Pitfalls or Variants

Common pitfalls

Failing to mark visited cells can cause infinite loops or incorrect distance calculation.
Expanding BFS incorrectly may overshoot the shortest path or revisit the first island.
Not handling edge boundaries leads to index errors in matrix traversal.

Follow-up variants

Compute shortest bridge in non-square grids with different numbers of islands.
Return all possible shortest paths connecting two islands instead of just the count.
Find minimal bridge while allowing diagonal connections between islands.

FAQ

What is the main idea behind solving Shortest Bridge using DFS and BFS?

Use DFS to mark one island and BFS to expand outward, flipping the minimal number of 0's until the second island is reached.

Why is a visited matrix necessary for this problem?

It prevents revisiting cells during BFS, ensuring accurate distance counting and avoiding infinite loops.

Can this approach handle the largest allowed grid sizes?

Yes, the solution is O(n^2) time and space, which works efficiently for grids up to 100x100.

What are common mistakes when implementing Shortest Bridge?

Not marking visited cells, incorrect BFS expansion, and mishandling matrix edges are frequent errors.

Does the order of DFS and BFS affect correctness?

Yes, performing DFS first ensures one island is fully captured; BFS then finds the shortest bridge without missing cells.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

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

Continue Practicing

#959 regions cut by slashes #1020 number of enclaves #1034 coloring a border