Making A Large Island

HardGraph DFS · Component Labeling🧩 Graph DFS LeetCode #827 ↗Updated Oct 30, 2026

Problem

You are given an n x n binary grid where 1 is land and 0 is water. You may turn at most one water cell into land. Return the size of the largest island you can end up with, where an island is a group of land cells connected up, down, left or right.

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

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

Inputgrid = [[1,1],[1,1]]Output4

1 ≤ n ≤ 500 · grid[i][j] is 0 or 1

Try it yourself

Java

class Solution {
    public int largestIsland(int[][] grid) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Flipping a water cell merges the islands touching it. So measure every island once, tag each land cell with its island id, and the score of a water cell is 1 + the sizes of its distinct neighbouring ids — no re-flooding per flip.

PatternGraph DFS

Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.

Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.

Open the Graph DFS guide →

Approaches

Brute ForceFlip Each Zero, Flood-Fill from It

Time O(n⁴)Space O(n²)

Try every water cell: set it to 1, flood-fill from it to measure the island it now belongs to, then set it back. If the grid has no water at all, the whole grid is one island of size n². (If any water exists, the best island always contains a flipped cell, because any island smaller than the grid borders water.)

Java

private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public int largestIsland(int[][] grid) {
    int n = grid.length, best = 0;
    boolean hasWater = false;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != 0) continue;
            hasWater = true;
            grid[r][c] = 1; // try this flip
            best = Math.max(best, islandSize(grid, r, c));
            grid[r][c] = 0; // undo
        }
    }
    return hasWater ? best : n * n;
}
private int islandSize(int[][] grid, int sr, int sc) {
    int n = grid.length, size = 0;
    boolean[][] seen = new boolean[n][n];
    Deque<int[]> stack = new ArrayDeque<>();
    stack.push(new int[]{sr, sc});
    seen[sr][sc] = true;
    while (!stack.isEmpty()) {
        int[] cell = stack.pop();
        size++;
        for (int[] d : DIRS) {
            int r = cell[0] + d[0], c = cell[1] + d[1];
            if (r >= 0 && r < n && c >= 0 && c < n && !seen[r][c] && grid[r][c] == 1) {
                seen[r][c] = true;
                stack.push(new int[]{r, c});
            }
        }
    }
    return size;
}

Direct simulation, but up to n² flips × n² per flood is ~6·10¹⁰ at n = 500.

BetterUnion-Find with Component Sizes

Time O(n² · α(n²))Space O(n²)

Treat each cell as a DSU element and union every pair of adjacent land cells, tracking component sizes at the roots. Then, for each water cell, collect the distinct roots of its up to four land neighbours and add their sizes plus one. The largest existing component covers the “no flip helps” case.

Java

private int[] parent, size;

public int largestIsland(int[][] grid) {
    int n = grid.length, best = 0;
    parent = new int[n * n];
    size = new int[n * n];
    for (int i = 0; i < n * n; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 0) continue;
            if (r + 1 < n && grid[r + 1][c] == 1) union(r * n + c, (r + 1) * n + c);
            if (c + 1 < n && grid[r][c + 1] == 1) union(r * n + c, r * n + c + 1);
        }
    }
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 1) {
                best = Math.max(best, size[find(r * n + c)]);
                continue;
            }
            int[] roots = new int[4];
            int count = 0, total = 1;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 0) continue;
                int root = find(nr * n + nc);
                boolean dup = false;
                for (int i = 0; i < count; i++) dup |= roots[i] == root;
                if (!dup) {
                    roots[count++] = root;
                    total += size[root];
                }
            }
            best = Math.max(best, total);
        }
    }
    return best;
}
private int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]]; // path halving
        x = parent[x];
    }
    return x;
}
private void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra; // attach smaller under larger
    size[ra] += size[rb];
}

Near-linear and reusable, but carries parent/size arrays and find() calls.

OptimalLabel Islands In-Place, Then Score Each Zero

Time O(n²)Space O(n²)

Pass 1 flood-fills each island, overwriting its cells with a fresh id (2, 3, …) and recording area[id]. Pass 2 looks at each water cell's four neighbours, adds the areas of the distinct ids among them, plus 1. Every cell is filled once and inspected once, so the work is strictly linear in the grid size.

Java

public int largestIsland(int[][] grid) {
    int n = grid.length, best = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    List<Integer> area = new ArrayList<>(List.of(0, 0)); // ids start at 2
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != 1) continue;
            int id = area.size(), cells = 0;
            Deque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[]{r, c});
            grid[r][c] = id;
            while (!stack.isEmpty()) {
                int[] cell = stack.pop();
                cells++;
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                        grid[nr][nc] = id; // label when pushed
                        stack.push(new int[]{nr, nc});
                    }
                }
            }
            area.add(cells);
            best = Math.max(best, cells);
        }
    }
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != 0) continue;
            int[] seen = new int[4];
            int count = 0, total = 1;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] < 2) continue;
                int id = grid[nr][nc];
                boolean dup = false;
                for (int i = 0; i < count; i++) dup |= seen[i] == id;
                if (!dup) {
                    seen[count++] = id;
                    total += area.get(id);
                }
            }
            best = Math.max(best, total);
        }
    }
    return best;
}

Two linear passes and a plain list of areas — the expected interview answer.

Pro tip

Start ids at 2 so labels can never be confused with water (0) or unlabelled land (1) — the grid itself becomes the visited array.

At a glance

Level	Approach	Time	Space
Brute Force	Flip Each Zero, Flood-Fill from It	`O(n⁴)`	`O(n²)`
Better	Union-Find with Component Sizes	`O(n² · α(n²))`	`O(n²)`
Optimal	Label Islands In-Place, Then Score Each Zero	`O(n²)`	`O(n²)`

Common pitfalls

Adding the same island twice when it touches the flipped cell on two sides — dedupe ids.
Returning 0 (or forgetting) the all-land grid where no flip is possible — answer is n².
Recursive DFS on a 500×500 island can overflow the stack — prefer an explicit stack.

Interview tips

Start from “try every flip”, then ask what work is repeated (re-flooding islands).
Explain why a flipped cell contributes 1 + sum of distinct neighbour islands.
Mention that labelling mutates the grid; copy it if the caller needs it intact.

Pattern

Connected-component labelling + per-cell merge scoring → “change one cell, maximise a component” grid questions.

My notes saved in this browser