Abstract / Summary

You can change one 0 to 1 to create the largest possible island in a grid of 0s and 1s.

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 57% (700k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Matrix
• Union Find

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 problem of finding the largest possible island size after converting at most one water cell (value 0) into land (value 1). An island is defined as a group of orthogonally adjacent land cells. The algorithm proceeds in three conceptual phases: labeling existing islands with unique identifiers, handling special configurations where no or a single island exists, and evaluating each water cell as a potential bridge to merge neighboring islands.

Identifying Islands and Assigning IDs

The first phase scans the entire grid to replace each group of 1s with a distinct integer identifier starting from 2. This identifier doubles as a key in a dictionary that records the size of the corresponding island.

id      = 2
islands = {}
for y in range(height):
    for x in range(width):
        if grid[y][x] == 1:
            todo = [(x, y)]
            have = set()
            while todo:
                tx, ty = todo.pop()
                if (tx, ty) in have:
                    continue
                have.add((tx, ty))
                if tx > 0 and grid[ty][tx - 1] == 1:
                    todo.append((tx - 1, ty))
                if ty > 0 and grid[ty - 1][tx] == 1:
                    todo.append((tx, ty - 1))
                if tx < width - 1 and grid[ty][tx + 1] == 1:
                    todo.append((tx + 1, ty))
                if ty < height - 1 and grid[ty + 1][tx] == 1:
                    todo.append((tx, ty + 1))
            islands[id] = len(have)
            for hx, hy in have:
                grid[hy][hx] = id
            id += 1

The depth-first search uses an explicit stack (todo) and a set (have) to avoid revisiting cells. By overwriting the original grid with the island identifier, later phases can query the island belonging to any cell in constant time.

Handling Edge Cases

Two edge conditions are addressed before the main bridge evaluation loop.

1. Empty island set - when the grid contains only water, the algorithm returns 1 because flipping any cell creates a single-cell island.

if not islands:
    return 1

2. Single island scenario - when exactly one island exists, the code distinguishes between a completely filled grid and a grid with at least one water cell. If the grid is already full, the current island size is returned unchanged; otherwise, the size can be increased by one through a conversion.

if len(islands) == 1:
    covered  = sum(islands.values())
    complete = width * height
    if covered == complete:
        return complete
    else:
        return covered + 1

These branches guarantee correct results for degenerate inputs without entering the more expensive bridge-checking loop.

Evaluating Potential Bridges

The core of the algorithm iterates over every water cell, collects the identifiers of distinct neighboring islands, and computes the combined size that would result from turning the water cell into land.

result = 0
for y in range(height):
    for x in range(width):
        if grid[y][x] == 0:
            bridging = set()
            if x > 0:
                bridging.add(grid[y][x - 1])
            if y > 0:
                bridging.add(grid[y - 1][x])
            if x < width - 1:
                bridging.add(grid[y][x + 1])
            if y < height - 1:
                bridging.add(grid[y + 1][x])
            bridging.discard(0)
            total = 1
            for b in bridging:
                total += islands[b]
            result = max(result, total)
return result

Key aspects of this step include:

• The use of a set (bridging) to automatically eliminate duplicate identifiers, preventing an island from being counted multiple times when it touches the water cell on more than one side.
• The explicit removal of 0 from the set, which represents water and should not contribute to the size calculation.
• Adding 1 to the total to account for the newly converted cell itself.

The maximum across all water cells yields the answer.

Performance Optimizations

Several design choices contribute to efficient execution:

• In-place labeling - By overwriting the original grid with island identifiers, the algorithm avoids allocating a separate structure for cell-to-island mapping, reducing memory pressure and improving cache locality.
• Early exits for trivial cases - The checks for an empty island set and a single island allow the function to return immediately for inputs that would otherwise trigger the full double loop over the grid.
• Set-based duplicate elimination - Using a set to collect neighboring identifiers eliminates the need for explicit conditional checks for each direction, simplifying the code while still ensuring each island contributes its size only once.
• Iterative DFS with a stack - The depth-first search avoids recursion, preventing stack overflow on large grids and allowing the interpreter to manage the call stack more efficiently.
• Minimal neighbor checks - Each cell examines at most four neighbors, and the boundary conditions are handled with simple index comparisons, keeping the inner loop lightweight.

These choices together enable the solution to handle large grids within reasonable time and memory constraints while maintaining clear and maintainable code structure.

Imagine a giant map of the ocean made of square grid tiles. Some of these tiles are pieces of land, and some are water. When pieces of land are touching, they form a big island.

The first part of this code looks at the whole map to find these hidden islands. It goes square by square and, whenever it finds a piece of land that has not been labeled yet, it explores all the nearby land to see how big that island is. It marks all those connected squares with a special number so that it knows exactly which bits belong together. It even keeps a little notebook that remembers the number and the size of every island it finds.

After finishing the map and knowing the size of every island, the code looks for a way to make the biggest island possible. It looks for every spot that is currently water. It pretends to turn that one water square into land. When it does that, it checks if that square is touching any nearby islands. If it is, it adds the sizes of those neighboring islands onto the one square it just changed. It keeps track of the biggest total it can create by trying this at every single water spot on the map. It eventually figures out how to build the largest playground by connecting land in the best way possible.

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	Rust			Go	TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	JoshCrozier			JS
	lkwq007		Python
	ruoru					Rust
	Shamik07						Dart
	suxrobGM							C#
	trung-hn		Python
	varunu28				Java
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
JoshCrozier	JavaScript
lkwq007	Python
ruoru	Rust
Shamik07	Dart
suxrobGM	C#
trung-hn	Python
varunu28	Java
zfang399	C++

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