hardGraphsPure DSA~45 min
Largest Cluster After Flipping One Cell
A grid marks active (1) and idle (0) cells; orthogonally connected active cells form a cluster. You may flip at most one idle cell to active. Find the size of the largest cluster you can form.
Problem
Given an n x n binary grid, you may change at most one 0 to 1. Return the size of the largest island (4-directionally connected group of 1s) achievable. If the grid is already all 1s, return n*n.
Input
An n x n binary matrix grid.
Output
The maximum island size after at most one flip.
Constraints
- 1 ≤ n ≤ 500
- grid[i][j] ∈ {0,1}
Examples
Example 1
Input
[[1,0],[0,1]]
Output
3
Flipping either 0 connects two size-1 islands into size 3.
Example 2
Input
[[1,1],[1,0]]
Output
4
Flipping the single 0 merges into one island of size 4.