Coding Interview PatternsMaking a Large Island
HardUnion Find
Making a Large Island
Explanation & Solution
Description
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s to create an island of size 3.
Constraints
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j]is either0or1
Approach
Union Find pattern
1. Build Islands with Union Find
- Iterate through every cell that is
1 - Union it with adjacent
1cells in all 4 directions - Track component
size— when unioning, add the smaller component's size to the larger
2. Find Baseline Largest Island
- Check the size of every component to find the current largest island
- This handles the case where the grid is all
1s (no0to flip)
3. Try Flipping Each 0
- For each
0cell, check its 4 neighbors - Collect the distinct island roots of neighboring
1cells using a Set - Sum up: 1 (the flipped cell) + sizes of all distinct neighboring islands
- Track the maximum across all
0cells
4. Return the Best
- The answer is the maximum of the baseline (no flip needed) and all flip options
Key Insight
- Union Find identifies all islands and their sizes in one pass
- For each
0cell, using a Set of roots prevents double-counting when two neighbors belong to the same island
Time
O(n²)two passes over the gridSpace
O(n²) for Union Find arraysVisualization
Input:
DFS Traversal2×2 grid
output—
Press play to start dfs traversal
CurrentQueuedVisitedSource
16 steps