Abstract / Summary

Given a grid with two islands, find the minimum number of water cells to change to connect them.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 59% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the “shortest bridge” problem on a square binary matrix. It first isolates one of the two islands, marks its cells, extracts the water cells that border the island (the beach), and then performs a breadth-first expansion from the beach until it reaches the second island. The number of expansion layers corresponds to the minimum number of water cells that must be flipped to connect the islands.

Finding and Marking the First Island

The algorithm begins by scanning the grid row-wise to locate any land cell (1). As soon as a land cell is found, the nested loops break, leaving the coordinates stored in seedx and seedy. This early exit prevents unnecessary traversal of the remainder of the grid.

seedx, seedy = None, None
for y in range(n):
    if seedx != None:
        break
    for x in range(n):
        if grid[y][x] == 1:
            seedx = x
            seedy = y
            break

A flood-fill using a set-based frontier (todo) expands from the seed cell. Each visited land cell is added to the set two and re-marked in the grid with the value 2. The use of a set for the frontier eliminates duplicate coordinates and provides O(1) membership checks, which speeds up the expansion compared with a list-based queue.

two  = set()
todo = set([ ( seedx, seedy ) ])
while todo:
    next = set()
    for x, y in todo:
        if grid[y][x] == 0:
            continue
        if (x, y) in two:
            continue;
        two.add((x, y))
        grid[y][x] = 2
        if x > 0:
            next.add((x - 1, y))
        if x < n - 1:
            next.add((x + 1, y))
        if y > 0:
            next.add((x, y - 1))
        if y < n - 1:
            next.add((x, y + 1))
    todo = next

Reducing to the Beach

After the first island is fully marked, the code iterates over its cells to collect all adjacent water cells. These water cells constitute the “beach” - the starting frontier for the bridge-building phase. By focusing only on water cells that directly touch the island, the algorithm avoids expanding from interior water that could never be part of the shortest bridge.

beach = set()
for x, y in two:
    if x > 0     and grid[y][x - 1] == 0:
        beach.add(( x - 1, y ))
    if x < n - 1 and grid[y][x + 1] == 0:
        beach.add(( x + 1, y ))
    if y > 0     and grid[y - 1][x] == 0:
        beach.add(( x, y - 1 ))
    if y < n - 1 and grid[y + 1][x] == 0:
        beach.add(( x, y + 1 ))

Expanding the Bridge

The bridge construction proceeds as a level-order BFS from the beach set. Each iteration represents one step (or layer) of water cells that would be flipped. The variable steps counts how many layers have been processed. When a cell belonging to the second island (grid[y][x] == 1) is encountered, the current step count is returned as the answer.

steps = 0
todo = beach
while todo:
    next = set()
    for x, y in todo:
        if grid[y][x] == 1: # reached other island
            return steps
        if grid[y][x] != 0:
            continue
        grid[y][x] == 3 # build bridge
        if x > 0:
            next.add((x - 1, y))
        if x < n - 1:
            next.add((x + 1, y))
        if y > 0:
            next.add((x, y - 1))
        if y < n - 1:
            next.add((x, y + 1))
    todo   = next
    steps += 1

Edge Cases Handled

The code gracefully handles islands that touch the grid border because all neighbor checks are guarded by bounds (x > 0, x < n - 1, y > 0, y < n - 1). When the first island occupies a corner, the beach extraction still correctly identifies the only adjacent water cells.

If the two islands are already adjacent (i.e., a water cell is not required), the beach set will contain cells that are directly next to the second island. The first expansion step will encounter a 1 and return 0, indicating that no bridge cells need to be added.

When the grid contains only one island (an invalid input for the problem), the flood-fill will mark all land cells, the beach will consist of all surrounding water, and the expansion will never encounter a second island. In such a scenario the loop would eventually exhaust all water cells, but the problem guarantees two islands, so the code’s early return on reaching a 1 is sufficient for the intended inputs.

The algorithm also tolerates grids where the islands are separated by a single narrow water corridor. The BFS expands uniformly from all beach cells, ensuring that the shortest possible crossing is found regardless of the corridor’s orientation.

Performance Optimizations

The use of set objects for both the island frontier (todo) and the beach frontier eliminates duplicate entries automatically, reducing the number of redundant neighbor checks.

Marking visited land cells directly in the input grid (grid[y][x] = 2) avoids the need for an auxiliary visited matrix, saving memory and improving cache locality.

The early termination after locating the first land cell prevents a full scan of the grid when the seed is found early, which is common in random inputs.

During the bridge expansion, the algorithm skips any cell that is not water (grid[y][x] != 0). This prevents unnecessary processing of already marked island cells or previously expanded bridge cells.

By separating the beach extraction from the main BFS, the algorithm reduces the initial frontier size, focusing the expansion on the most promising cells and thereby decreasing the number of BFS layers required to reach the second island.

Imagine a big square map filled with blue water and two islands made of sand. The computer wants to build a bridge to connect the two islands by traveling across the water.

First, the computer searches the map to find where the sand is. When it finds a piece of sand, it walks around to find all the neighboring sand pieces to map out the whole first island. It marks these sand pieces with a special tag so it knows which island it has already found.

Next, the computer looks around the edges of that first island where the sand touches the water. These spots are like a beach. The computer decides to start building the bridge from these beach spots.

Finally, the computer starts counting steps. It moves out from the beach into the water, one step at a time, moving in all directions like a ripple in a pond. It keeps moving further and further into the water until it finally steps onto the sand of the second island. The number of steps it took to get there tells the computer how long the bridge needs to be to connect the two islands together.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++			Java
	leetcode.ca	C++	Python		Java		Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality