Making A Large Island
Find the largest island you can make by turning at most one 0 into a 1, by labeling islands with ids and sizes and then scoring each water cell from its neighbors.
Problem Understanding
Making A Large Island: in an n × n binary grid you may change at most one 0 to 1. Return the size of the largest island (4-directionally connected 1s) afterwards.
Examples: [[1,0],[0,1]] → 3; [[1,1],[1,0]] → 4; [[1,1],[1,1]] → 4.
The Intuition: Precompute Islands, Then Each Flip Is a Sum
Flipping a 0 joins every island that touches it. So:
- Label every island with a DFS, as in Number of Islands, but also record each island's size under its id.
- Score each 0: 1 for the flipped cell plus the sizes of the distinct neighboring islands.
- Take the best, or the largest existing island if there is nothing to flip.
Merging groups and counting their size is also what union-find does in Number of Operations to Make Network Connected.
Interactive Walkthrough
LAND SHOWS ITS ISLAND ID · · = WATER · + = THE FLIP BEING TRIED
LABEL THE ISLANDS
islands
0
this flip
:
best
:
Pass 1: give every island an id (2, 3, …) and record its size
Next
Island 2 starts at (0, 0): DFS marks its 3 cells with 2
grid
Land cells show their island id and color; water is a dot. On each try the flipped cell is marked + and the islands it joins are emphasized. The default grid shows one flip touching the same island twice.
Dry Run Table
Input: [[1,1,0,0],[1,0,1,1],[0,0,1,0]]. Island 2 = {(0,0),(0,1),(1,0)}, size 3; island 3 = {(1,2),(1,3),(2,2)}, size 3.
| Flip | Neighbor islands | Score |
|---|---|---|
| (0,2) | 3, 2 | 1 + 3 + 3 = 7 |
| (0,3) | 3 | 4 |
| (1,1) | 2 (twice), 3 | 1 + 3 + 3 = 7 |
| (2,0) | 2 | 4 |
| (2,1) | 3 | 4 |
| (2,3) | 3 | 4 |
Answer: 7.
The Solution Template
Label with DFS, then score each water cell. The grid is modified in place to store island ids.
Making A Large Island Code
1var largestIsland = function(grid) {2 const n = grid.length, m = grid[0].length;3 const sizes = new Map();4 const fill = (r, c, island) => {5 if (r < 0 || c < 0 || r >= n || c >= m || grid[r][c] !== 1) return 0;6 grid[r][c] = island;7 return 1 + fill(r + 1, c, island) + fill(r - 1, c, island) + fill(r, c + 1, island) + fill(r, c - 1, island);8 };9 let island = 2, best = 0;10 for (let r = 0; r < n; r++)11 for (let c = 0; c < m; c++)12 if (grid[r][c] === 1) {13 const size = fill(r, c, island);14 sizes.set(island++, size);15 best = Math.max(best, size);16 }17 for (let r = 0; r < n; r++)18 for (let c = 0; c < m; c++)19 if (grid[r][c] === 0) {20 const seen = new Set();21 for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]])22 if (nr >= 0 && nc >= 0 && nr < n && nc < m && grid[nr][nc] > 1) seen.add(grid[nr][nc]);23 let total = 1;24 for (const k of seen) total += sizes.get(k);25 best = Math.max(best, total);26 }27 return best;28};
Edge Cases & Common Mistakes
- No zeros: answer is n²; initialize best with the largest island.
- All zeros: answer is 1.
- Double counting: use a set of neighbor ids.
- Deep recursion: a 500 × 500 snake-shaped island can overflow the call stack; use an explicit stack in production.
- Using 1 as an id: clashes with unvisited land; start ids at 2.
Summary
Label each island with an id and size via DFS, then for each 0 add 1 to the sizes of its distinct neighboring islands; return the maximum (or the largest island if there is no 0). O(R·C) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet