LeetCode 827 Making A Large Island - Logic

$1.$ Build: Loop through the grid.

If a cell is $1$, unite it with its $1$ neighbors. Use DSU with Size Tracking.

$2.$ Search: Now loop through every $0$ cell.

$3.$ Test: Imagine turning this $0$ into a $1$. It would connect its $4$ neighbors.

$4.$ Sum: Look up the Leader of each neighbor. Sum the sizes of these unique leaders + $1$ (for the new cell).

$5.$ The answer is the maximum sum you find.

Note: Be careful not to double-count if Up and Down already belong to the same island!