Shortest Bridge - Practice Coding Problems

Shortest Bridge - 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.

Input & Output

Example 1 — Basic 3x3 Grid

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

› Output: 2

💡 Note: Island 1 is at (0,1), Island 2 is at (2,2). Shortest path: (0,1) → (1,1) → (1,2) → (2,2), requiring 2 flips at (1,1) and (1,2).

Example 2 — Adjacent Islands

$ 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

💡 Note: Large outer island surrounds inner island at (2,2). Only need to flip one adjacent cell like (1,2) or (2,1) to connect them.

Example 3 — Corner Islands

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

› Output: 4

💡 Note: Islands at opposite corners (0,0) and (2,2). Manhattan distance is |0-2| + |0-2| - 1 = 3, but need 4 flips for 4-directional path.

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

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Binary matrix with exactly two separate islands

Find Bridge

Calculate shortest path between island boundaries

Output Length

Return minimum number of 0s to flip

Key Takeaway

🎯 Key Insight: Use multi-source BFS from island boundary to find shortest water crossing

Asked in

a Amazon 15 G Google 12 f Facebook 8 M Microsoft 6

The key insight is to use multi-source BFS from the boundary of one island to find the shortest path to the other island. Best approach uses DFS + BFS: first mark one complete island, then BFS from its boundary. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ BFS - Multi-Source Shortest Path	O(n²)	O(n²)	Use DFS to find first island, then BFS from its boundary to find shortest path to second island
Brute Force - All Pairs Distance	O(n⁴)	O(n²)	Check distance between every cell of island 1 to every cell of island 2

BFS - Multi-Source Shortest Path — Algorithm Steps

Use DFS to find and mark first island completely
Add all boundary cells of first island to BFS queue
Perform BFS expanding outward layer by layer
Stop when we reach any cell of the second island
Return the number of steps taken

Visualization

Tap to expand

Step-by-Step Walkthrough

Mark Island

DFS marks first island with value 2

Find Boundary

Add boundary cells to BFS queue

BFS Expansion

Expand layer by layer until reaching second island

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n;

void dfs(int** grid, int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] != 1) {
        return;
    }
    grid[x][y] = 2;
    for (int i = 0; i < 4; i++) {
        dfs(grid, x + directions[i][0], y + directions[i][1]);
    }
}

int solution(int** grid, int grid_size) {
    n = grid_size;
    
    // Find and mark first island
    int found = 0;
    for (int i = 0; i < n && !found; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                dfs(grid, i, j);
                found = 1;
                break;
            }
        }
    }
    
    // Simple BFS implementation for demo
    int queue[10000][3];
    int front = 0, rear = 0;
    
    // Find boundary of first island
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) {
                for (int k = 0; k < 4; k++) {
                    int ni = i + directions[k][0], nj = j + directions[k][1];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] == 0) {
                        queue[rear][0] = i;
                        queue[rear][1] = j;
                        queue[rear][2] = 0;
                        rear++;
                        break;
                    }
                }
            }
        }
    }
    
    // BFS
    int visited[100][100] = {0};
    while (front < rear) {
        int x = queue[front][0], y = queue[front][1], dist = queue[front][2];
        front++;
        
        for (int k = 0; k < 4; k++) {
            int nx = x + directions[k][0], ny = y + directions[k][1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny]) {
                if (grid[nx][ny] == 1) {
                    return dist;
                }
                if (grid[nx][ny] == 0) {
                    visited[nx][ny] = 1;
                    queue[rear][0] = nx;
                    queue[rear][1] = ny;
                    queue[rear][2] = dist + 1;
                    rear++;
                }
            }
        }
    }
    
    return 0;
}

int main() {
    // Simplified input parsing for demo
    int** grid = (int**)malloc(10 * sizeof(int*));
    for (int i = 0; i < 10; i++) {
        grid[i] = (int*)malloc(10 * sizeof(int));
    }
    
    int result = solution(grid, 3);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

DFS visits each cell once O(n²), BFS visits each cell at most once O(n²)

⚠ Quadratic Growth

Space Complexity

O(n²)

BFS queue can contain up to O(n²) cells in worst case

⚠ Quadratic Space

89.0K Views

Medium Frequency

~25 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS - Multi-Source Shortest Path — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler