Making a Large Island Using Disjoint Set Union (DSU)

Problem Statement❯

Given an n x n binary grid where each cell is either 0 or 1, your task is to determine the size of the largest island that can be formed by converting at most one 0 to 1.

An island is a group of 1s connected horizontally or vertically (not diagonally). You are allowed to change at most one 0 into 1. The goal is to identify the maximum size of a connected island that can be achieved with such a transformation.

Examples❯

Grid	Output	Description
[[1, 0], [0, 1]]	3	Flipping any 0 connects the two 1s into a single island of size 3
[[1, 1], [1, 0]]	4	Flipping the bottom-right 0 gives a full 2x2 island
[[0, 0], [0, 0]]	1	All sea — only one flip allowed, gives a single land cell
[[1, 1], [1, 1]]	4	All land — no flip needed, entire grid is one island
[[1, 0, 1], [0, 0, 0], [1, 0, 1]]	5	Flipping the center cell (1,1) connects four corner islands
[[1, 1, 0], [1, 0, 0], [0, 0, 1]]	5	Flipping (1,1) connects the top-left cluster to the bottom-right
[[0, 1, 0], [1, 0, 1], [0, 1, 0]]	5	Flipping center (1,1) connects all diagonally placed 1s into one island
[[1, 1, 1, 1], [1, 0, 0, 1], [1, 0, 0, 1], [1, 1, 1, 1]]	14	Flipping any center 0 expands the outer ring island inward
[[0, 1, 0], [0, 0, 0], [1, 0, 1]]	3	Flipping center (1,1) connects up to 3 separate 1s
[[1]]	1	Single land cell — already one island
[[0]]	1	Single sea cell — flipping gives one island of size 1

Visualization Player

Solution❯

Understanding the Problem

We are given a binary grid where 1 represents land and 0 represents water. An island is formed by connecting adjacent 1s either vertically or horizontally. Our goal is to flip at most one 0 to 1 and determine the size of the largest island possible after this operation.

To solve this efficiently, we use the Disjoint Set Union (DSU) data structure to track connected components (i.e., islands) and their sizes. We simulate flipping each 0 to a 1 and check which islands it could connect to, to maximize the resulting island size.

Step-by-Step Solution with Example

Step 1: Group All Existing Islands Using DSU

We iterate through each cell in the grid. Whenever we find a 1, we perform a union operation with its adjacent 1s (up, down, left, right). Each island is treated as a connected component in DSU.

Step 2: Track the Size of Each Island

We maintain a map that stores the size of each component, using the root representative as the key. This way, we know how big each island is, which is critical when we later evaluate the impact of flipping a 0.

Step 3: Evaluate Each 0 for Maximum Island Size

Now, we scan the grid again. For every 0 cell, we:

Look in the four directions (up, down, left, right).
Collect the root IDs of neighboring 1s (i.e., neighboring islands).
Make sure not to count the same island twice (use a set).
Sum up the sizes of these unique neighboring islands and add 1 (for the current 0 being flipped to 1).

This gives us the size of the island we can potentially form by flipping this specific 0.

Step 4: Track the Maximum Island Size

During the above evaluations, we keep updating the maximum island size encountered. This ensures we return the largest possible island size that can be formed with one flip.

Step 5: Handle the Case Where No 0 Exists

If the grid has no 0s, the largest island is the entire grid of 1s. In that case, we return the size of the whole grid.

Edge Cases

All 1s: No 0 to flip. The answer is the total count of 1s.
All 0s: Flipping any one 0 gives an island of size 1.
Disconnected 1s: Flipping a 0 between them can connect multiple islands.
Flipping a border 0: Still needs to check only valid neighbors within grid bounds.

Finally

This problem is a great example of how Disjoint Set Union can be used to manage groups of connected elements efficiently. Instead of recalculating connected components multiple times, we preprocess the island structure once and reuse the information for every possible 0 we might flip. The use of sets to avoid duplicate island counting ensures correctness, and edge cases are naturally handled through the logic flow.

Algorithm Steps❯

Initialize DSU for each cell in the grid with parent pointers and size mappings.
For each cell with value 1:
- Check its 4 neighbors.
- If the neighbor is also 1, union the current cell and neighbor in DSU.
Map each island's root parent to its size.
For each cell with value 0:
- Collect unique parent IDs of its 4-directional 1-neighbors.
- Sum their sizes + 1 to simulate flipping the 0 to 1.
- Update max island size accordingly.
If no 0s exist, return the size of the entire grid as the island.

Code

JavaScript

class DSU {
  constructor(n) {
    this.parent = Array(n).fill(0).map((_, i) => i);
    this.size = Array(n).fill(1);
  }

  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }

  union(x, y) {
    let px = this.find(x), py = this.find(y);
    if (px === py) return;
    if (this.size[px] < this.size[py]) [px, py] = [py, px];
    this.parent[py] = px;
    this.size[px] += this.size[py];
  }

  getSize(x) {
    return this.size[this.find(x)];
  }
}

function largestIsland(grid) {
  const n = grid.length;
  const dsu = new DSU(n * n);
  const dirs = [[0,1],[1,0],[-1,0],[0,-1]];

  const index = (i, j) => i * n + j;

  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j] === 1) {
        for (const [dx, dy] of dirs) {
          let ni = i + dx, nj = j + dy;
          if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] === 1) {
            dsu.union(index(i,j), index(ni,nj));
          }
        }
      }
    }
  }

  let maxIsland = 0;
  const seen = new Set();

  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j] === 0) {
        let total = 1;
        seen.clear();
        for (const [dx, dy] of dirs) {
          const ni = i + dx, nj = j + dy;
          if (ni >= 0 && nj >= 0 && ni < n && nj < n && grid[ni][nj] === 1) {
            let root = dsu.find(index(ni, nj));
            if (!seen.has(root)) {
              total += dsu.getSize(root);
              seen.add(root);
            }
          }
        }
        maxIsland = Math.max(maxIsland, total);
      }
    }
  }

  // If all 1s, no 0 to flip
  if (maxIsland === 0) {
    const rootSizes = new Map();
    for (let i = 0; i < n; ++i) {
      for (let j = 0; j < n; ++j) {
        if (grid[i][j] === 1) {
          let root = dsu.find(index(i, j));
          rootSizes.set(root, dsu.getSize(root));
        }
      }
    }
    for (const size of rootSizes.values()) maxIsland = Math.max(maxIsland, size);
  }

  return maxIsland;
}

const grid = [[1, 0], [0, 1]];
console.log("Largest island size:", largestIsland(grid)); // Output: 3

⬅ Previous TopicNumber of Islands II - Online Queries using DSU

Next Topic ⮕Bridges in Graph using Tarjan's Algorithm

Comments

Loading comments...