Making A Large Island - Solution & Explanation

Problem Overview: You get an n x n binary grid where 1 represents land and 0 represents water. You may flip at most one 0 to 1. The task is to return the size of the largest island possible after the flip. An island is a group of 4-directionally connected land cells.

Approach 1: Brute Force Flip + DFS (O(n^4) time, O(n^2) space)

Iterate through every cell in the grid. Whenever you encounter a 0, temporarily flip it to 1 and run a full depth-first search to compute the size of the resulting island. Track the maximum size across all flips, then revert the cell back to 0. Each DFS may scan the entire grid (O(n^2)) and you potentially perform it for every cell (O(n^2)), resulting in O(n^4) time. This approach is straightforward but too slow for large grids.

Approach 2: DFS with Island Labeling (O(n^2) time, O(n^2) space)

The key insight is to pre-compute the size of every island so you never recompute it. Traverse the grid once and run DFS whenever you encounter an unvisited land cell. During the DFS, label the island with a unique id (for example 2, 3, 4...) and store its size in a hash map keyed by the island id. This step converts the grid into labeled components using DFS over the matrix.

Next, iterate over each 0 cell. Look at its four neighbors and collect the distinct island ids touching that cell. If you flip the cell to 1, the new island size becomes 1 + sum(sizes of unique neighboring islands). Use a set to avoid counting the same island twice. Track the maximum possible size while scanning all water cells. The grid traversal and labeling both take O(n^2), giving an optimal O(n^2) solution.

Approach 3: Union Find (Disjoint Set) (O(n^2) time, O(n^2) space)

You can also treat each land cell as a node in a disjoint-set structure and union adjacent land cells. The union operations build connected components representing islands. Each component stores its size. After building the structure, iterate through every 0 cell and inspect up to four neighboring components. Similar to the DFS labeling idea, combine the sizes of unique neighboring components plus one for the flipped cell. This approach relies on the Union Find data structure and performs nearly constant-time unions and finds with path compression.

Recommended for interviews: DFS with island labeling is the most common interview solution. It demonstrates strong grid traversal skills, component labeling, and efficient reuse of computed island sizes. Brute force shows basic reasoning but fails performance constraints. The labeled DFS approach reaches O(n^2) time and is easy to implement compared to Union Find while still demonstrating optimal thinking.