Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 934. Shortest Bridge

Given an n×n binary grid containing exactly two 4-connected islands, return the minimum number of 0→1 flips needed to connect them. The core challenge is finding the shortest bridge between island boundaries (commonly solved by marking one island and doing a multi-source BFS outward across water until the other island is reached).

Asked at:

DESCRIPTION

Input:

grid = [[0,1],[1,0]]

Output:

Explanation: We have island 1 at positions (0,1) and (1,0). They are diagonal neighbors. We can flip either (0,0) or (1,1) to connect them, requiring 1 flip.

Constraints:

n == grid.length == grid[i].length
2 <= n <= 100
grid[i][j] is either 0 or 1
There are exactly two 4-connected islands in the grid

Understanding the Problem

Let's understand what we're being asked to do. We have an n×n binary grid (containing only 0s and 1s) with exactly two separate islands. An island is a group of 1s connected horizontally or vertically (4-connected).

For example, given:

[[0,1,0],
 [0,0,0],
 [0,0,1]]

We have island 1 at position (0,1) and island 2 at position (2,2). They are separated by water (0s).

Our goal: Find the minimum number of 0→1 flips needed to connect these two islands. In the example above, we could flip (1,1) and (1,2) to create a bridge, requiring 2 flips.

Important constraints: The grid contains exactly two 4-connected islands (no more, no less). We need to find the shortest bridge between them.

Edge cases to consider: What if the islands are already adjacent (answer would be 0)? What if the grid is very large? What's the most efficient way to measure distance between island boundaries?

Brute Force Approach

The brute force approach would be to identify all cells belonging to each island using DFS/BFS, then check every pair of cells (one from island 1, one from island 2) and calculate their Manhattan distance. The minimum distance minus 1 would be the answer (since adjacent cells have distance 1 but need 0 flips). This requires iterating through all possible pairs of cells from the two islands.

Visualization

def shortest_bridge(grid):
    """
    Brute force: Find all cells of both islands using DFS,
    then check every pair of cells (one from each island)
    to find minimum Manhattan distance.
    """
    n = len(grid)
    
    # Find all cells belonging to island 1
    island1 = []
    # Find all cells belonging to island 2
    island2 = []
    
    visited = [[False] * n for _ in range(n)]
    
    def dfs(r, c, island):
        """DFS to collect all cells of an island"""
        if r < 0 or r >= n or c < 0 or c >= n:
            return
        if visited[r][c] or grid[r][c] == 0:
            return
        
        visited[r][c] = True
        island.append((r, c))
        
        # Explore all 4 directions
        dfs(r + 1, c, island)
        dfs(r - 1, c, island)
        dfs(r, c + 1, island)
        dfs(r, c - 1, island)
    
    # Find first island
    found_first = False
    for i in range(n):
        if found_first:
            break
        for j in range(n):
            if grid[i][j] == 1:
                dfs(i, j, island1)
                found_first = True
                break
    
    # Find second island
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1 and not visited[i][j]:
                dfs(i, j, island2)
    
    # Brute force: check every pair of cells
    min_distance = float('inf')
    
    for r1, c1 in island1:
        for r2, c2 in island2:
            # Manhattan distance between two cells
            distance = abs(r1 - r2) + abs(c1 - c2)
            min_distance = min(min_distance, distance)
    
    # Subtract 1 because adjacent cells have distance 1 but need 0 flips
    return min_distance - 1

Start: Find shortest bridge between two islands

0 / 16

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n⁴) We need O(n²) to identify islands, then potentially O(n²) cells in each island, leading to O(n²) × O(n²) = O(n⁴) pairwise distance calculations

Space Complexity: O(n²) We need O(n²) space to store which cells belong to each island, plus recursion stack for DFS

Building Intuition

The key insight is that we need to find the shortest path from any cell of island 1 to any cell of island 2. This is not about connecting specific points - it's about connecting the boundaries of two regions.

Think of it as: "What's the minimum distance between the two island perimeters?" We need to expand outward from one island until we touch the other.

If we tried checking every pair of cells (one from each island), we'd have O(n⁴) comparisons for an n×n grid. That's extremely inefficient!

Instead, by treating all cells of one island as simultaneous starting points and expanding outward level-by-level, we naturally find the shortest bridge. The first time we reach the other island tells us the minimum distance.

Imagine you're standing on island 1 and you have unlimited paint. You paint all cells of island 1 first. Then, in round 1, you paint all water cells adjacent to island 1. In round 2, you paint all water cells adjacent to those. You keep expanding outward in waves.

The moment your paint touches island 2, you know the number of rounds equals the minimum bridge length. This wave-like expansion is exactly what breadth-first search does - it explores all cells at distance d before exploring cells at distance d+1.

Common Mistakes

Trying to find specific 'closest points' on each island instead of treating entire island boundaries as starting points - this misses the multi-source BFS insight

Using Manhattan distance between island cells without accounting for obstacles - this doesn't work because we can only flip water cells, not go through existing land

Forgetting to mark the initial island cells as visited before starting BFS - this can cause infinite loops or incorrect distance calculations

Counting the number of cells in the path instead of the number of flips - remember that adjacent cells (distance 1) require 0 flips, so answer is distance minus 1 when islands are already adjacent

Not handling the edge case where islands are already adjacent (answer should be 0) - the BFS should immediately detect this in the first expansion

Optimal Solution

The optimal approach uses a two-phase BFS strategy. First, use DFS or BFS to mark all cells of one island (say, island 1) and add them all to a queue as starting points. Then, perform multi-source BFS from all cells of island 1 simultaneously, expanding outward across water cells level by level. Track the number of levels (distance) as we expand. The moment we reach any cell of island 2, the current level count is our answer - this represents the minimum number of 0→1 flips needed to bridge the islands.

Visualization

from collections import deque
def shortest_bridge(grid):
    """
    Find the shortest bridge between two islands in a binary grid.
    Uses DFS to mark first island, then multi-source BFS to find shortest path to second island.
    """
    n = len(grid)
    
    # Find first island cell
    def find_first_island():
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    return (i, j)
        return None
    
    # DFS to mark all cells of first island and add to queue
    def dfs(i, j, queue):
        if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != 1:
            return
        grid[i][j] = 2  # Mark as visited (first island)
        queue.append((i, j))
        dfs(i + 1, j, queue)
        dfs(i - 1, j, queue)
        dfs(i, j + 1, queue)
        dfs(i, j - 1, queue)
    
    # Initialize queue with all cells of first island
    queue = deque()
    start_i, start_j = find_first_island()
    dfs(start_i, start_j, queue)
    
    # Multi-source BFS from first island
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    distance = 0
    
    while queue:
        size = len(queue)
        for _ in range(size):
            i, j = queue.popleft()
            
            for di, dj in directions:
                ni, nj = i + di, j + dj
                
                if ni < 0 or ni >= n or nj < 0 or nj >= n or grid[ni][nj] == 2:
                    continue
                
                # Found second island
                if grid[ni][nj] == 1:
                    return distance
                
                # Water cell - mark as visited and add to queue
                grid[ni][nj] = 2
                queue.append((ni, nj))
        
        distance += 1
    
    return -1

Start: Find shortest bridge between two islands

0 / 71

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) We visit each cell at most twice: once during island identification and once during BFS expansion. Since there are n² cells, this gives us O(n²) time complexity

Space Complexity: O(n²) We need O(n²) space for the queue (in worst case, all cells could be in the queue) and O(n²) for tracking visited cells

What We've Learned

Two-phase BFS strategy: When finding shortest paths between two unknown regions, use DFS/BFS to mark one region first, then multi-source BFS from that region's boundary - this transforms an ambiguous two-target problem into a clear single-target search with known starting points.
Multi-source BFS for boundary expansion: Instead of starting BFS from a single point, initialize the queue with all boundary cells of the first island - this simultaneously expands in all directions and naturally finds the shortest path to any point on the second island, avoiding the need to try every possible starting point.
Island marking with DFS: Use DFS to flood-fill the first island you encounter (changing 1s to 2s or adding to a set) - this prevents revisiting the same island during BFS and clearly distinguishes between the two islands, making the bridge-building phase unambiguous.
Distance tracking without visited array: In BFS for shortest path, track distance as a level counter (incrementing after processing each queue level) rather than storing distance in each cell - this saves space and the queue naturally prevents revisiting cells when you mark them as visited upon addition, not upon removal.
Early termination on first contact: The BFS can return immediately upon reaching any cell of the second island (a cell with value 1) - because BFS explores layer by layer, the first contact is guaranteed to be the shortest bridge, eliminating the need to explore all possibilities.
Grid boundary problems pattern: This island-bridging technique applies to any problem requiring minimum connections between separated regions in a grid - think of it for problems involving connecting components, expanding territories, or finding shortest paths between multiple sources and targets in 2D spaces.

Test Your Understanding

Why is matrix the right data structure for this problem?

matrix provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early August, 2025

Microsoft

Senior

Late January, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 934. Shortest Bridge

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact