Problem Description

You have an n x n binary matrix called grid where:

• 1 represents land
• 0 represents water

An island is defined as a group of 1s that are connected horizontally or vertically (4-directionally connected). These 1s are not connected to any other group of 1s outside the island.

The grid contains exactly two islands.

Your task is to connect these two islands into one single island by changing some 0s (water) to 1s (land). You want to find the minimum number of 0s that need to be changed to 1s to create a bridge between the two islands.

For example, if you have two islands separated by water, you need to find the shortest path of water cells between them and convert those water cells to land to connect the islands.

The function should return the smallest number of 0s you must flip to connect the two islands.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a 2D grid where cells can be connected to adjacent cells (4-directionally). This forms an implicit graph where each cell is a node and edges exist between adjacent cells.

Is it a tree?

• No: The grid structure is not a tree. We have islands (connected components) and we need to find connections between them. The grid can have cycles and multiple disconnected components.

Is the problem related to directed acyclic graphs?

• No: The grid represents an undirected graph where connections between adjacent cells are bidirectional.

Is the problem related to shortest paths?

• Yes: We need to find the minimum number of water cells (0s) to flip to connect two islands, which is essentially finding the shortest path between the two islands.

Is the graph weighted?

• No: Each step from one water cell to another has the same cost (flipping one 0 to 1), making this an unweighted shortest path problem.

BFS

• Following the "no" branch from weighted graphs leads us to BFS for unweighted shortest path problems.

However, the solution also uses DFS initially to:

1. Find and mark the first island (changing all its 1s to 2s)
2. Collect all cells of the first island as starting points for the BFS

Conclusion: The flowchart suggests using BFS for finding the shortest path between two islands. The actual solution combines DFS (to identify and mark one island) followed by BFS (to find the minimum distance to the second island). This hybrid approach efficiently solves the shortest bridge problem.

Intuition

To connect two islands with the minimum number of flips, we need to find the shortest distance between them. Think of this problem like building the shortest bridge between two pieces of land separated by water.

The key insight is that we can treat this as a multi-source BFS problem. Here's the thought process:

1. First, we need to distinguish the two islands. If we start BFS from random cells, we won't know which island they belong to. So we use DFS to find one complete island first and mark all its cells differently (say, change all 1s to 2s). This way, we know exactly where one island is.

2. Why start from the entire island edge? Instead of picking a single cell from the first island and finding the shortest path to the second island, we can be smarter. We treat all cells of the first island as starting points simultaneously. This is like expanding outward from the entire perimeter of the first island at once.

3. The expansion process: We perform a level-by-level BFS expansion from all cells of the first island. Each level represents one additional water cell we need to flip. We expand outward like ripples in water:

   • Level 0: All cells of the first island
   • Level 1: All water cells adjacent to the first island
   • Level 2: Water cells one step further out
   • And so on...

4. When do we stop? The moment our expansion reaches any cell of the second island (a cell with value 1), we've found the shortest bridge. The number of levels we've expanded equals the minimum number of water cells we need to flip.

This approach is optimal because BFS guarantees we find the shortest path in an unweighted graph, and by starting from all cells of one island simultaneously, we ensure we find the absolute minimum distance between any two points on different islands.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation uses a combination of DFS and multi-source BFS to solve the problem efficiently:

Step 1: Find and Mark the First Island

i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j])
dfs(i, j)

• We iterate through the grid to find the first cell with value 1
• Once found, we call DFS from that cell to explore the entire first island

Step 2: DFS to Mark and Collect Island Cells

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)

• The DFS function marks each visited cell of the first island as 2 (to distinguish it from the second island)
• It adds each cell to a queue q which will serve as the starting points for BFS
• Uses pairwise(dirs) where dirs = (-1, 0, 1, 0, -1) to generate the 4 directions: up, right, down, left

Step 3: Multi-source BFS to Find Shortest Bridge

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

The BFS expansion works level by level:

• ans tracks the current distance (number of water cells to flip)
• For each level, we process all cells currently in the queue
• For each cell, we check its 4 neighbors:
  • If we find a cell with value 1 (the second island), we immediately return ans as the minimum distance
  • If we find a cell with value 0 (water), we mark it as 2 (visited) and add it to the queue for the next level
  • Cells already marked as 2 are skipped to avoid revisiting
• After processing each level, we increment ans to represent moving one step further from the first island

Key Data Structures:

• deque: Used as a queue for BFS to efficiently add/remove elements from both ends
• grid: Modified in-place to mark visited cells, avoiding the need for a separate visited set

Time Complexity: O(n²) where n is the grid dimension, as we potentially visit every cell once Space Complexity: O(n²) for the queue in the worst case where one island occupies most of the grid

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 4×4 grid with two islands:

Initial Grid:
1 1 0 0
1 0 0 0  
0 0 0 1
0 0 1 1

Step 1: Find and Mark the First Island using DFS

Starting from position (0,0), we use DFS to explore and mark the entire first island:

• Visit (0,0): mark as 2, add to queue
• Visit (0,1): mark as 2, add to queue
• Visit (1,0): mark as 2, add to queue

After DFS:
2 2 0 0
2 0 0 0
0 0 0 1
0 0 1 1

Queue q = [(0,0), (0,1), (1,0)]

Step 2: Multi-source BFS Expansion

Now we perform BFS starting from all cells of the first island simultaneously.

Level 0 (ans = 0): Process the initial queue containing the first island's cells.

• From (0,0): Check neighbors → (0,1) is 2 (skip), (1,0) is 2 (skip)
• From (0,1): Check neighbors → (0,0) is 2 (skip), (0,2) is 0 (mark as 2, add to queue), (1,1) is 0 (mark as 2, add to queue)
• From (1,0): Check neighbors → (0,0) is 2 (skip), (1,1) already marked as 2 (skip), (2,0) is 0 (mark as 2, add to queue)

After Level 0:
2 2 2 0
2 2 0 0
2 0 0 1
0 0 1 1

New queue = [(0,2), (1,1), (2,0)]
ans = 1 (increment for next level)

Level 1 (ans = 1): Process water cells adjacent to the first island.

• From (0,2): Check neighbors → (0,1) is 2 (skip), (0,3) is 0 (mark as 2, add to queue), (1,2) is 0 (mark as 2, add to queue)
• From (1,1): Check neighbors → all are 2 or already processed
• From (2,0): Check neighbors → (1,0) is 2 (skip), (2,1) is 0 (mark as 2, add to queue), (3,0) is 0 (mark as 2, add to queue)

After Level 1:
2 2 2 2
2 2 2 0
2 2 0 1
2 0 1 1

New queue = [(0,3), (1,2), (2,1), (3,0)]
ans = 2 (increment for next level)

Level 2 (ans = 2): Continue expansion.

• From (0,3): Check neighbors → (1,3) is 0 (mark as 2, add to queue)
• From (1,2): Check neighbors → (1,3) already marked, (2,2) is 0 (mark as 2, add to queue)
• From (2,1): Check neighbors → (2,2) already marked, (3,1) is 0 (mark as 2, add to queue)
• From (3,0): Check neighbors → (3,1) already marked

After Level 2:
2 2 2 2
2 2 2 2
2 2 2 1
2 2 1 1

New queue = [(1,3), (2,2), (3,1)]
ans = 3 (increment for next level)

Level 3 (ans = 3):

• From (1,3): Check neighbors → all are 2
• From (2,2): Check neighbors → (2,3) is 1 (second island found!)

Return ans = 3

The algorithm found that we need to flip 3 water cells to connect the two islands. The shortest bridge would be through cells (1,1) → (1,2) → (2,2), converting these 3 water cells to land to connect the islands.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm consists of two main phases:

1. DFS phase: Finding and marking the first island

   • The DFS traverses all cells of the first island exactly once
   • In the worst case, the island could contain all n² cells
   • Time: O(n²)

2. BFS phase: Expanding from the first island to find the second island

   • The BFS explores cells level by level from the first island
   • Each cell in the grid is visited at most once during BFS
   • In the worst case, we might need to explore nearly all n² cells before reaching the second island
   • Time: O(n²)

Overall time complexity: O(n²) + O(n²) = O(n²)

Space Complexity: O(n²)

The space usage comes from:

1. Recursion stack for DFS:

   • In the worst case, if the island forms a long path, the recursion depth could be O(n²)

2. BFS queue:

   • In the worst case, the queue could contain all cells of the first island
   • Maximum queue size: O(n²)

3. Grid modification:

   • The algorithm modifies the input grid in-place, so no additional grid space is needed
   • However, if we consider the input space, it's O(n²)

Overall space complexity: O(n²) (dominated by either the recursion stack or the BFS queue)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect BFS Level Processing

A critical pitfall is not properly processing BFS levels, which leads to incorrect distance calculation. Many implementations mistakenly increment the distance counter inside the neighbor-checking loop rather than after processing all nodes at the current level.

Incorrect approach:

while queue:
    row, col = queue.popleft()
    for dx, dy in directions:
        # Check neighbors...
        if grid[next_row][next_col] == 1:
            return distance
        distance += 1  # WRONG: Increments for each cell, not each level

Correct approach:

while queue:
    # Process entire level before incrementing distance
    for _ in range(len(queue)):
        row, col = queue.popleft()
        for dx, dy in directions:
            # Check neighbors...
            if grid[next_row][next_col] == 1:
                return distance
    distance += 1  # Increment after processing all cells at current distance

2. Not Marking Water Cells Before Adding to Queue

Failing to mark water cells as visited (value 2) immediately when adding them to the queue can cause duplicate processing and incorrect results.

Incorrect approach:

if grid[next_row][next_col] == 0:
    queue.append((next_row, next_col))
    # Forgot to mark as visited!

Correct approach:

if grid[next_row][next_col] == 0:
    grid[next_row][next_col] = 2  # Mark immediately
    queue.append((next_row, next_col))

3. Using the Same Marker Value as Original Island

Using value 1 to mark visited cells would make it impossible to distinguish between the first island (already explored) and the second island (target).

Incorrect approach:

grid[row][col] = 1  # Can't distinguish from second island

Correct approach:

grid[row][col] = 2  # Use different value to mark first island and visited water

4. Starting BFS from a Single Cell Instead of All Island Cells

Starting BFS from only one cell of the first island rather than all boundary cells simultaneously would give incorrect distances.

Incorrect approach:

# Only add starting cell to queue
queue.append((start_row, start_col))
# Then start BFS...

Correct approach:

def dfs(row, col):
    queue.append((row, col))  # Add ALL island cells to queue
    grid[row][col] = 2
    # Continue DFS to add all cells...

5. Off-by-One Error in Distance Counting

The distance should represent the number of water cells to flip. A common mistake is returning distance + 1 or starting with distance = 1.

Solution verification:

• When we find the second island, we've expanded distance times from the first island
• The current distance value represents exactly how many water cells we crossed
• No adjustment needed when returning the answer