Making A Large Island

Making A Large Island

What is this problem about?

In the Making A Large Island problem, you are given an n x n binary matrix containing 0s (water) and 1s (land). You are allowed to change at most one 0 to a 1. An island is a 4-directionally connected group of 1s. Your objective is to find the maximum possible size of an island you can create after performing this single operation.

Why is this asked in interviews?

This is a benchmark Hard-level Graph problem. Companies like Meta and Uber ask it to test your optimization skills with Depth-First Search (DFS) or Union-Find. A naive approach—flipping every single 0 to 1 one by one and running a full DFS each time—results in an unacceptable $O(N^4)$ time complexity. Interviewers want to see you precompute island sizes to achieve an $O(N^2)$ solution.

Algorithmic pattern used

This problem is best solved using a Two-Pass DFS or Union-Find pattern.

1. Pass 1: Iterate through the grid. Whenever you find a 1, run a DFS to calculate the total size of that island. Paint every cell in that island with a unique island_id (e.g., 2, 3, 4...). Store the mapping of island_id -> size in a Hash Map.
2. Pass 2: Iterate through the grid again, this time looking for 0s. For every 0, check its 4 neighbors. Collect the unique island_ids of those neighbors. The potential new island size if you flip this 0 is 1 (the flipped zero) + sum(sizes of adjacent unique islands). Track the global maximum.

Example explanation

Grid:

1 0
0 1

Pass 1:

• Top-left 1: DFS finds size 1. Paint it with ID 2. Map: {2: 1}.
• Bottom-right 1: DFS finds size 1. Paint it with ID 3. Map {2: 1, 3: 1}. Grid is now:

2 0
0 3

Pass 2:

• Top-right 0: Neighbors are ID 2 and ID 3. They are unique. Size = 1 + map[2] + map[3] = $1 + 1 + 1 = 3$.
• Bottom-left 0: Neighbors are ID 2 and ID 3. Size = 3. The maximum possible island size is 3.

Common mistakes candidates make

A very common mistake during the second pass is adding the size of the same island multiple times. If a 0 is touching the same massive island on its left and its top, you must only add the island's size once! Using a Hash Set to store the island_ids of the 4 neighbors before summing their sizes prevents this double-counting bug.

Interview preparation tip

For the Making A Large Island coding problem, always cleanly separate your graph coloring logic from your evaluation logic. Modifying the grid in-place to store the island_id (starting from 2, since 0 and 1 are taken) is a brilliant memory-saving trick that interviewers love. Be sure to handle the edge case where the grid is already entirely 1s!