Making A Large Island
Hard · Matrix · Array · Depth-First Search · Breadth-First Search · Union Find · Matrix
Problem
You are given an n x n grid of 1s (land) and 0s (water). An island is a group of land cells connected through shared sides (not corners).
You may turn at most one water cell into land. Return the size of the largest island the grid can have after that change. Changing nothing is allowed, which matters when there is no water to turn.
Examples
Input: grid = [[1,0],[0,1]] Output: 3
Turning either water cell joins the two single cells through it: 1 + 1 + 1 = 3.
Input: grid = [[1,1,0],[0,0,0],[0,1,1]] Output: 5
Turning the center cell touches the top pair through (0,1) and the bottom pair through (2,1): 2 + 2 + 1 = 5.
Input: grid = [[1,1],[1,1]] Output: 4
Nothing can be changed, so the whole grid is the island: 4.
Constraints
- n == len(grid) == len(grid[i])
- 1 <= n <= 500
- grid[i][j] is 0 or 1
Approaches
- Baseline: flip each water cell and remeasure — time O(n⁴), space O(n²)
Follow-up
If cells could be flipped one after another while the size is asked after each flip, relabeling each time would be too slow. A union-find over land cells merges islands as cells turn to land, keeping sizes at the roots, so each flip costs nearly O(1).
Related problems
Start free on Cariara · Coding problems · System design studio
