AlgoMaster Logo

Making A Large Island

hardFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We have a grid of 0s and 1s, where groups of connected 1s form islands. We get one move: flip a single 0 to a 1. The question is what is the largest island we can create with that one flip.

Flipping a 0 can connect multiple separate islands at once. A 0 cell might have a different island on each of its four sides. Flipping that cell to 1 merges all four islands into one. So a flip does not always grow a single island by one cell. It can bridge several islands together.

This gives the central subproblem: for each 0 cell, we need the sizes of all distinct islands adjacent to it. Once we can answer that, the answer is 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 up to 250,000 cells. An O(n^4) brute force (a fresh DFS per zero cell) is around 62.5 billion operations, far too slow. The target is O(n^2) total.
  • At most one 0 can be changed → We might not change any cell at all. When the grid is all 1s, there is no 0 to flip, so the answer is the whole grid: n * n.

Approach 1: Brute Force

Intuition

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 to find the size of the island containing that cell, record the size, then set it back to 0.

This is easy to implement but does a lot of repeated work. Every flip re-explores islands that earlier flips already measured, and the size of an island does not change between flips.

Algorithm

  1. For each cell (i, j) in the grid where grid[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).
  2. Also track the maximum existing island size (in case there are no 0 cells).
  3. Return the maximum size found.

Example Walkthrough

1Initial grid: two isolated 1s at (0,0) and (1,1)
0
1
0
1
0
1
0
1
1/6

Code

The repeated DFS work is the bottleneck. Each island's size is fixed, so the next approach computes every island's size once up front and then looks up neighboring sizes in O(1) per 0 cell.

Approach 2: Island Labeling with DFS (Optimal)

Intuition

Split the problem into two phases. The first phase identifies every island and computes its size once. The second phase evaluates each 0 cell using those precomputed sizes.

Assign each island a unique ID starting from 2, since 0 and 1 are already used as grid values. During the DFS that explores an island, overwrite every cell in that island with the island's ID. Store the size of each island in a map: islandId -> size.

For each 0 cell, check its four neighbors. Collect the unique island IDs among those neighbors into a set, sum their sizes, and add 1 for the flipped cell. The set deduplicates: a single island can border the same 0 cell from two or more sides, and counting it once is required. The maximum sum across all 0 cells is the answer.

Algorithm

  1. Initialize islandId = 2 and a map islandSize to store each island's size.
  2. 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.
  3. Iterate over every cell in the grid again. For each 0 cell:
    • 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.
  4. Return the maximum. If no 0 cell was found, return n * n.

Example Walkthrough

1Phase 1: Start labeling. Scan for unvisited land cells.
0
1
0
scan
1
0
1
0
1
1/9

Code

The labeling approach rewrites the grid in place to store IDs. The next approach reaches the same O(n^2) result without mutating cell values, using a disjoint-set structure to group connected 1s.

Approach 3: Union-Find

Intuition

Connected components are what Union-Find is built for. Treat each cell as a node identified by i * n + j. Union every pair of horizontally or vertically adjacent 1-cells. After processing the whole grid, each island is one set, and the set's root carries the island's size.

For each 0 cell, find the roots of its neighboring 1-cells. Distinct roots correspond to distinct islands, so collecting roots into a set and summing their sizes (plus 1 for the flipped cell) gives the island that flipping this 0 would form. The maximum over all 0 cells is the answer.

This produces the same answer as island labeling. The difference is structural: labeling marks the grid with IDs during DFS, while Union-Find keeps component membership in parent and size arrays and leaves the grid unchanged.

Algorithm

  1. Build a DSU over n * n nodes, each starting as its own set with size 1.
  2. Scan the grid. For each 1 cell, union it with its right neighbor and its down neighbor if those are also 1. (Right and down alone cover every adjacency once.)
  3. For each 0 cell, collect the roots of its 4 neighbors that hold a 1. Sum the sizes of the distinct roots and add 1. Track the maximum.
  4. If there was no 0 cell, return n * n. Otherwise return the maximum found (which is at least 1, from flipping a 0 with no land neighbors).

Example Walkthrough

1Build DSU. Union adjacent 1s. (0,0)-(0,1) right, (0,0)-(1,0) down.
0
1
0
1
1
1
1
0
1/6

Code

Union-Find and island labeling both run in O(n^2) and use O(n^2) space. Labeling is shorter to write and avoids the DSU bookkeeping. Union-Find avoids mutating the input grid and generalizes cleanly when edges arrive incrementally rather than all at once. The brute force is useful only to confirm the answer on tiny grids while debugging.