Making a Large Island
Using Disjoint Set Union (DSU)

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