☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

Making a large island

Hard TUF ID 512 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an n x n binary grid, where 1 is land and 0 is water. You may change at most one 0 into a 1. Return the size of the largest island possible afterwards. An island is a group of 1s connected horizontally or vertically.

Constraints: 1 ≤ n ≤ 500, every cell is 0 or 1.

Example 1

grid = [[1,0],
        [0,1]]
answer = 3          // flip either 0; it touches both single-cell islands: 1 + 1 + 1

Example 2

grid = [[1,1],
        [1,1]]
answer = 4          // there is no 0 to flip; the whole grid is already one island

Example 3

grid = [[1,1,0],
        [0,0,0],
        [0,1,1]]
answer = 5          // flip the centre: it joins the top island (2) and the bottom island (2)

Approach 1: Brute force, try every flip

Intuition. There are only as many choices as there are 0s. For each one, flip it, measure the island that now contains it with a BFS, and flip it back. Only the island containing the flipped cell can have grown, and any island not touching it is no larger than the island we would get by flipping a cell next to it, so the maximum over all flips is the answer. The one case this misses is a grid with no 0 at all; then the whole grid is one island of size n^2.

Algorithm.

  1. For every cell (r, c) with value 0: set it to 1, compute componentSize(r, c) with BFS, restore it to 0, and keep the maximum.
  2. If no 0 was found, return n * n.
static int bruteForce(int[][] grid) {
    int n = grid.length, best = 0;
    boolean hasZero = false;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) continue;
            hasZero = true;
            grid[r][c] = 1;                              // flip, measure, restore
            best = Math.max(best, componentSize(grid, r, c));
            grid[r][c] = 0;
        }
    }
    return hasZero ? best : n * n;                       // no 0 to flip: the whole grid is one island
}

static int componentSize(int[][] grid, int sr, int sc) {
    int n = grid.length, size = 0;
    boolean[][] seen = new boolean[n][n];
    Deque<int[]> queue = new ArrayDeque<>();
    seen[sr][sc] = true;
    queue.add(new int[]{sr, sc});
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        size++;
        for (int k = 0; k < 4; k++) {
            int nr = cell[0] + DR[k], nc = cell[1] + DC[k];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1 && !seen[nr][nc]) {
                seen[nr][nc] = true;
                queue.add(new int[]{nr, nc});
            }
        }
    }
    return size;
}

Complexity. Time O(n^4): up to n^2 zeros, and each BFS can visit all n^2 cells. Space O(n^2) for the seen array and the queue. For n = 500 that is around 6 × 10^10 steps, hopeless.

The waste is that every BFS rediscovers the same islands again and again. The islands never change; only the cell we flip does.

Approach 2: Optimal, Disjoint Set with island sizes

Intuition. Precompute the islands once. Then, for a 0 cell, flipping it creates an island made of the cell itself plus every island it touches. If we know which island each neighbour belongs to and how big each island is, the result is

1 + sum of sizes of the distinct islands among its four neighbours

and that takes constant time per cell.

A Disjoint Set with union by size gives both pieces of information for free: find(cell) names the island, and size[root] is how many cells it has. The important word in the formula is distinct. A 0 cell surrounded on several sides by the same island must count that island once, which is why the roots are collected in a Set.

static final class DisjointSet {
    final int[] parent, size;

    DisjointSet(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                         // already in the same set
        if (size[ra] < size[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;                                    // hang the smaller tree under the larger
        size[ra] += size[rb];
        return true;
    }
}

Algorithm.

  1. Number the cells r * n + c and create a Disjoint Set over all n^2 of them.
  2. Pass 1: for every land cell, union it with its land neighbour below and to the right. Looking in only these two directions is enough because every adjacent pair is then examined exactly once.
  3. Pass 2: for every cell:
    • If it is land, update the answer with the size of its island. This handles a grid with no 0.
    • If it is water, collect the roots of its land neighbours in a set, add their sizes to 1, and update the answer.
  4. Return the best value.
static int optimal(int[][] grid) {
    int n = grid.length;
    DisjointSet ds = new DisjointSet(n * n);
    for (int r = 0; r < n; r++) {                           // step 1: union every pair of adjacent 1s
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 0) continue;
            if (r + 1 < n && grid[r + 1][c] == 1) ds.union(r * n + c, (r + 1) * n + c);
            if (c + 1 < n && grid[r][c + 1] == 1) ds.union(r * n + c, r * n + c + 1);
        }
    }
    int best = 0;
    for (int r = 0; r < n; r++) {                           // step 2: evaluate every cell
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                best = Math.max(best, ds.size[ds.find(r * n + c)]);   // covers the all-ones grid
                continue;
            }
            Set<Integer> roots = new HashSet<>();           // distinct islands around this 0
            for (int k = 0; k < 4; k++) {
                int nr = r + DR[k], nc = c + DC[k];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1) roots.add(ds.find(nr * n + nc));
            }
            int total = 1;                                  // the flipped cell itself
            for (int root : roots) total += ds.size[root];
            best = Math.max(best, total);
        }
    }
    return best;
}

Dry run on example 3. Pass 1 builds island A = {(0,0), (0,1)} with size 2 and island B = {(2,1), (2,2)} with size 2. Pass 2 on the water cells:

cell land neighbours distinct roots total
(0,2) (0,1) A 1 + 2 = 3
(1,0) (0,0) A 3
(1,1) (0,1), (2,1) A, B 1 + 2 + 2 = 5
(1,2) (2,2) B 3
(2,0) (2,1) B 3

The best is 5, from flipping the centre.

Complexity. Time O(n^2 · α(n^2)): each pass touches every cell once and does at most four find calls per cell. Space O(n^2) for the Disjoint Set arrays; the per-cell root set has at most four entries.

The same plan works without a Disjoint Set: run a DFS that paints each island with a distinct id (say starting from 2) and records its size in a map, then do pass 2 with those ids. Both versions are O(n^2); the Disjoint Set version avoids recursion and reuses the structure from the other problems in this section.

Why de-duplication matters

Consider this grid:

1 1 1
1 0 1
1 1 1

The ring is a single island of size 8 and the centre touches it on all four sides. Without the Set, the formula would compute 1 + 8 + 8 + 8 + 8 = 33, which is larger than the grid. With the set, there is one distinct root and the answer is 1 + 8 = 9, the whole grid. The Java tests include this case.

Edge cases and pitfalls