Making A Large Island
Last Updated: April 5, 2026
Understanding the Problem
We have a grid of 0s and 1s, where groups of connected 1s form islands. We get one free move: flip a single 0 to a 1. The question is, what is the largest island we can create with that one flip?
The tricky part is that flipping a 0 could potentially connect multiple separate islands. Imagine a 0 cell that has different islands to its north, south, east, and west. Flipping that cell to 1 would merge all four islands into one giant island. So we are not just growing one island by 1 cell. We are potentially bridging several islands together.
The key observation is this: for each 0 cell, we need to know the sizes of all distinct islands adjacent to it. If we can answer that question efficiently, we just pick the 0 cell that maximizes the sum of its neighboring island sizes plus 1 (for the flipped cell itself).
Key Constraints:
1 <= n <= 500→ The grid has at most 250,000 cells. An O(n^4) brute force (DFS per zero cell) would mean 62.5 billion operations, which is too slow. We need O(n^2) total.grid[i][j]is either0or1→ Simple binary grid, no special values to handle.- At most one
0can be changed → We might not need to change any (if the grid is all 1s).
Approach 1: Brute Force
Intuition
The most direct approach: try flipping every 0 cell, one at a time, and measure the resulting island. For each 0 cell, temporarily set it to 1, run a DFS/BFS to find the size of the island containing that cell, record the size, then set it back to 0.
This is simple to implement but does a lot of redundant work. Every time we flip a cell and run DFS, we are re-exploring islands we have already seen in previous iterations.
Algorithm
- For each cell
(i, j)in the grid wheregrid[i][j] == 0: - Set
grid[i][j] = 1. - Run DFS/BFS from
(i, j)to find the size of the connected island. - Update the maximum island size.
- Set
grid[i][j] = 0(restore). - Also track the maximum existing island size (in case there are no 0 cells).
- Return the maximum size found.
Example Walkthrough
Code
- Time Complexity: O(n^4). We iterate over all n^2 cells. For each 0 cell, we run a DFS that could visit up to n^2 cells, giving O(n^2) * O(n^2) = O(n^4).
- Space Complexity: O(n^2). The visited array for each DFS takes O(n^2) space, plus O(n^2) recursion stack depth in the worst case.
For every 0 cell, we re-explore islands we have already measured. The size of each island never changes, so we are recomputing the same sizes over and over. What if we computed each island's size just once and then looked up neighboring sizes in O(1)?
Approach 2: Island Labeling with DFS (Optimal)
Intuition
The key insight is to separate the problem into two phases. In the first phase, we identify every island and compute its size. In the second phase, we evaluate each 0 cell by looking at which islands surround it.
Assign each island a unique ID (starting from 2, since 0 and 1 are already used in the grid). During the DFS that explores an island, overwrite every cell in that island with the island's ID. Also store the size of each island in a map: islandId -> size.
Now, for each 0 cell, check its four neighbors. Collect the unique island IDs among those neighbors (using a set to avoid double-counting the same island that appears on multiple sides), sum up their sizes, and add 1 for the flipped cell. The maximum across all 0 cells is the answer.
Island sizes are fixed. Once we have labeled and measured every island, no future operation changes them. We are not actually flipping any 0 to 1. We are just asking: "If I flipped this 0, how big would the resulting island be?" And that question reduces to: "What is the total size of all distinct islands touching this cell, plus 1?"
The set-based deduplication is critical. A single island can wrap around a 0 cell and touch it from multiple directions. Without the set, we would double-count that island's size.
Algorithm
- Initialize
islandId = 2and a mapislandSizeto store each island's size. - Iterate over every cell in the grid. When you find a
1(unvisited land): - Run DFS from that cell, marking every cell in the island with
islandId. - Count the cells during DFS and store the count in
islandSize[islandId]. - Increment
islandId. - Iterate over every cell in the grid again. For each
0cell: - Check its 4 neighbors. Collect unique island IDs into a set.
- Sum the sizes of those islands (from the map) and add 1.
- Track the maximum.
- Return the maximum. If no 0 cell was found, return
n * n.
Example Walkthrough
Code
- Time Complexity: O(n^2). Phase 1 visits every cell exactly once during DFS labeling. Phase 2 iterates over every cell and checks at most 4 neighbors. Total: O(n^2).
- Space Complexity: O(n^2). The islandSize map stores at most O(n^2) entries. The DFS recursion stack can go up to O(n^2) in the worst case for a single snake-like island.