DiffPush Tier Graphs · MST Problems O(n^2 α(n^2)) · O(n^2)
A port authority may reclaim exactly one water cell into usable dock. Planners want the resulting largest connected dock region: measure every existing region, then test each candidate water cell — reclaiming it merges every distinct region touching its four sides, plus the cell itself. If the harbour is already seamless, the answer is simply its full size.
Input: An n x n binary matrix grid where 1 is dock and 0 is water.
Output: Return the size of the largest island after converting at most one 0 to 1.
1 <= n <= 500grid[i][j] is 0 or 1Input: {"grid":[[1,0],[0,1]]}
Output: 3
Reclaiming either water cell bridges the two 1-regions into a size-3 harbour.
Input: {"grid":[[1,1],[1,1]]}
Output: 4
No water exists to reclaim — the whole grid is already one island.