Skip to main content
Talentd

Shortest Bridge - Solution & Explanation

MediumArrayDepth-First SearchBreadth-First SearchMatrix14 min readAsked at: Amazon, Microsoft, Goldman Sachs +13
Practice this problem

Problem Statement

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.

 

Example 1:

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

Example 2:

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

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

 

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.

Approach Overview

Problem Overview: You are given an n x n binary grid with exactly two islands (groups of connected 1s). The task is to flip the minimum number of 0s to 1s so the two islands become connected. The answer is the length of the shortest bridge between them.

Approach 1: Brute Force Expansion from Every Island Cell (O(n^4) time, O(n^2) space)

First collect all cells belonging to the first island using a traversal such as depth-first search. For each of those cells, run a separate breadth-first search over the matrix to find the nearest cell of the second island. Each BFS explores outward layer by layer through water cells until land from the other island appears.

This works because BFS guarantees the shortest distance from a starting cell. However, running BFS independently from many cells causes repeated exploration of the same water regions. With up to O(n^2) starting points and each BFS costing O(n^2), the overall cost becomes O(n^4).

Approach 2: DFS to Mark First Island + Multi‑Source BFS (O(n^2) time, O(n^2) space)

This is the standard optimal solution. First scan the grid until you find the first 1. Run DFS to mark the entire island and push all its coordinates into a queue. Mark them as visited so they are not processed again.

Next perform a multi‑source BFS starting from every cell of the first island simultaneously. Each BFS layer represents flipping one additional ring of water cells. For every step, expand in four directions and convert reachable 0 cells to visited water. The moment a neighbor cell with value 1 from the second island is encountered, the current BFS level is the minimum number of flips required.

The key insight: instead of running BFS from each island cell separately, treat the entire first island as the starting frontier. This guarantees the shortest bridge while exploring each grid cell at most once. Time complexity becomes O(n^2) with O(n^2) space for the queue and visited tracking.

Recommended for interviews: Interviewers expect the DFS + multi‑source BFS approach. Detecting the first island with DFS shows comfort with grid traversal, and expanding with BFS demonstrates understanding of shortest path in an unweighted grid. Mentioning the brute force idea briefly helps show the reasoning path, but implementing the optimized BFS expansion is the real signal of problem‑solving skill.

Approach 1: Depth-First Search (DFS) and Breadth-First Search (BFS)

This approach involves two primary steps:
1. Use DFS to mark one of the islands completely.
2. Use BFS from the boundary of that marked island to find the shortest path to the other island.
The BFS will expand layer by layer, counting the zeros flipped until the boundary of the second island is reached.

This solution first uses DFS to mark all the cells of the first island. Each cell belonging to the island is added to a queue.
By using DFS for marking, we ensure all island cells are explored. Once marked, a BFS is used to expand outwards from all boundary points simultaneously, effectively finding the shortest path to the second island.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N^2), where N is the size of the grid, because each cell is processed at most twice (once in DFS and once in BFS).
Space Complexity: O(N^2), for the visited array and the queue holding grid indices.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth-First Search (DFS) and Breadth-First Search (BFS)

Time Complexity: O(N^2), where N is the size of the grid, because each cell is processed at most twice (once in DFS and once in BFS).
Space Complexity: O(N^2), for the visited array and the queue holding grid indices.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force BFS from Each Island CellO(n^4)O(n^2)Conceptual baseline to understand why repeated BFS searches are inefficient
DFS + Multi‑Source BFS (Optimal)O(n^2)O(n^2)Standard solution for grid shortest‑path problems where all edges have equal cost

Video Solution

Shortest Bridge - Leetcode 934 - Python • NeetCode • 49,153 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shortest Bridge easy or hard?
Shortest Bridge is classified as Medium difficulty on LeetCode. The challenge comes from combining two traversal strategies—DFS to identify an island and BFS to compute the shortest bridge distance across the grid.
Shortest Bridge Python/Java solution
In Python or Java, the typical implementation runs DFS to mark the first island and add its cells to a queue. Then BFS expands outward in four directions using a queue until the second island is reached. Both implementations run in O(n^2) time and use standard grid traversal patterns.
How to solve Shortest Bridge in O(n^2)?
Start by scanning the grid and run DFS from the first land cell to mark the entire island. Push all its coordinates into a queue. Then run a multi-source BFS that expands outward through water cells until a cell from the second island is reached. The BFS level at that moment equals the minimum flips required.
What is the best approach for Shortest Bridge?
The most efficient method uses Depth-First Search to locate and mark the first island, then runs a multi-source Breadth-First Search from all its cells simultaneously. BFS expands through water layer by layer until it reaches the second island. This guarantees the minimum number of flips with O(n^2) time and O(n^2) space complexity.
Is Shortest Bridge asked at Google/Amazon/Meta?
Shortest Bridge is a common medium-level grid traversal problem and variations appear in interviews at companies like Amazon, Google, and Meta. It tests understanding of DFS for island detection and BFS for shortest path in an unweighted grid.
What data structure is used in Shortest Bridge?
The solution primarily uses a queue for Breadth-First Search and recursion or a stack for Depth-First Search. The grid itself acts as the matrix structure, and a visited marker or in-place modification prevents revisiting cells.
What is the time complexity of Shortest Bridge?
The optimal DFS + BFS approach runs in O(n^2) time for an n x n grid. Each cell is visited at most once while marking the first island and during BFS expansion. Space complexity is also O(n^2) due to the queue and visited tracking.

Ready to solve this problem?

Practice Shortest Bridge with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Operations to Make X and Y Equal