Making A Large Island

1. Define the problem

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1. Return the size of the largest island in grid after applying this operation. An island is a group of 1s connected 4-directionally. Union every pair of adjacent land cells to size up each island. Then for every 0 cell, sum the distinct island sizes touching it, plus one for the flipped cell itself.

Constraints

n == grid.length == grid_i.length
1 ≤ n ≤ 500
grid_i[j] is 0 or 1

Example

Inputgrid = [[1,0],[0,1]]

Output3

Explanation Flipping either 0 connects both single-cell islands into one island of size 3.

2. Know the words first

In plain terms

4-directionally connected: Two cells touch only if one sits directly above, below, left, or right of the other — not diagonally.

3. Visualize the solution

Union land cells, then test every water cell as a flip

(0,0)root (0,0)

(0,1)water

(1,0)water

(1,1)root (1,1)

Statusunion

(0,0) and (1,1) are both land but not adjacent — no union happens between them.

What happens in this step

id(0,0) = 0, id(0,1) = 1, id(1,0) = 2, id(1,1) = 3
parent = [0, 1, 2, 3]   size = [1, 1, 1, 1]

Scanning top-to-bottom, left-to-right: (0,0) has no land neighbor above or to its left, so no union call happens for it. (1,1) checks its up neighbor (0,1) — water — and its left neighbor (1,0) — also water — so it stays its own island too. (0,0) and (1,1) never touch, so parent and size never change: two separate size-1 islands.

Step 1 of 3

Steps to visualize

Give every land cell its own group and union it with every adjacent land cell, tracking group size.
If there is no water at all, the whole grid is one island — return n * n.
Otherwise, for every water cell, look at its up to four land neighbors.
Sum the sizes of the distinct islands touching that water cell, plus one for the cell itself.
The largest such sum across every water cell is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Union land cells, then test every water cell as a flip

(0,0)root (0,0)

(0,1)water

(1,0)water

(1,1)root (1,1)

Statusunion

(0,0) and (1,1) are both land but not adjacent — no union happens between them.

What happens in this step

id(0,0) = 0, id(0,1) = 1, id(1,0) = 2, id(1,1) = 3
parent = [0, 1, 2, 3]   size = [1, 1, 1, 1]

Scanning top-to-bottom, left-to-right: (0,0) has no land neighbor above or to its left, so no union call happens for it. (1,1) checks its up neighbor (0,1) — water — and its left neighbor (1,0) — also water — so it stays its own island too. (0,0) and (1,1) never touch, so parent and size never change: two separate size-1 islands.

Step 1 of 3

5. Solution

Solution

solution.tsTypeScript

function largestIsland(grid) {
  const n = grid.length;
  const parent = Array.from({ length: n * n }, (_, i) => i);
  const size = new Array(n * n).fill(1);

  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) return;

    if (size[rootA] < size[rootB]) {
      parent[rootA] = rootB;
      size[rootB] += size[rootA];
    } else {
      parent[rootB] = rootA;
      size[rootA] += size[rootB];
    }
  }

  const id = (r, c) => r * n + c;

  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] !== 1) continue;
      if (r > 0 && grid[r - 1][c] === 1) union(id(r, c), id(r - 1, c));
      if (c > 0 && grid[r][c - 1] === 1) union(id(r, c), id(r, c - 1));
    }
  }

  let best = 0;
  let hasWater = false;

  for (let r = 0; r < n; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === 1) {
        best = Math.max(best, size[find(id(r, c))]);
        continue;
      }

      hasWater = true;
      const seenRoots = new Set();
      let total = 1;

      const neighbors = [
        [r - 1, c],
        [r + 1, c],
        [r, c - 1],
        [r, c + 1],
      ];

      for (const [nr, nc] of neighbors) {
        if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
        if (grid[nr][nc] !== 1) continue;

        const root = find(id(nr, nc));
        if (seenRoots.has(root)) continue;
        seenRoots.add(root);
        total += size[root];
      }

      best = Math.max(best, total);
    }
  }

  return hasWater ? best : n * n;
}

Time: O(n^2 · α(n^2))
Space: O(n^2)

6. Test cases

Test cases

Input	Expected	Covers
`grid = [[1,0],[0,1]]`	`3`	example from the docstring
`grid = [[1,1],[1,0]]`	`4`	flipping the one water cell connects to an already-connected group of three
`grid = [[1,1],[1,1]]`	`4`	no water at all, so the whole grid is already one island
`grid = [[0,0],[0,0]]`	`1`	no land at all, flipping any single cell makes an island of size 1
`grid = [[1]]`	`1`	smallest valid grid, a single land cell with no water to flip
`grid = [[0]]`	`1`	smallest valid grid, a single water cell with no land neighbors

Making A Large Island