DSA problem
Making A Large Island
You are given an n x n binary matrix grid. You are allowed to change AT MOST one 0 to 1. Return the size of the largest island in grid after applying this operation. An island is a 4-directionally connected group of 1s.
The naive idea is to try every 0 cell, flip it, and compute the largest island via a fresh DFS. With up to n^2 zero cells and an O(n^2) DFS each, this is O(n^4) — far too slow for n up to 500.
The optimal solution observes that flipping a single 0 can only merge UP TO FOUR distinct adjacent islands. So we precompute the size of every existing island once. We DFS each island and color all its cells with a unique island ID (starting at 2 to avoid conflict with 0 and 1), and record size[id]. Then we scan every 0 cell, collect the SET of unique island IDs among its four orthogonal neighbors, and the candidate answer for that flip is 1 + sum(size[id] for id in unique_neighbor_ids). The maximum over all 0 cells is the answer.
We must also consider the case where the grid is already all 1s (no 0 to flip); the answer is then just the size of the single existing island. Total time is O(n^2): one DFS pass to label all islands plus O(1) work per 0 cell. Space is O(n^2) for the recursion stack and the size map.
Examples
grid = [[1,0],[0,1]]3grid = [[1,1],[1,0]]4grid = [[1,1],[1,1]]4Constraints
- n == grid.length
- n == grid[i].length
- 1 <= n <= 500
- grid[i][j] is either 0 or 1.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.