Making a large island

Hard

Label the islands, then test each zero

Problem

In a binary grid you may flip one 0 to 1. Return the largest island size possible.

In simple words

Label each island with its size, then for every 0 sum the distinct islands it would bridge, plus one.

The idea

First label every island with an id and record its size. Then for each 0, sum the sizes of the distinct island ids around it plus one — using a set of ids so an island touched twice is not counted twice.

The trick

Deduplicate neighbouring island ids before summing.
Handle the all-ones grid, where no flip is possible.
Two passes, O(rows × cols).

←→stepspaceplay

1/10

Optimal

timeO(α(n))spaceO(n)

Almost constant per op.

1function find(x) {2  while (p[x] !== x) { p[x] = p[p[x]]; x = p[x]; }3  return x;4}5function union(a, b) {6  a = find(a); b = find(b);7  if (a === b) return false;8  if (rank[a] < rank[b]) [a, b] = [b, a];9  p[b] = a; if (rank[a] === rank[b]) rank[a]++;10  return true;11}

Input

nodes: 5, 0 edges

Memory

groups: —

Output

groups: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: grid = [[1,0],[0,1]]
Output:: 3
Explanation:: Flipping one 0 joins two islands → size 3.

Example 2

Input:: grid = [[1,1],[1,0]]
Output:: 4
Explanation:: One flip makes the whole grid land → 4.

Example 3

Input:: grid = [[1,1],[1,1]]
Output:: 4
Explanation:: Already all land → 4.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.