Making A Large Island — Hard Problem & Solution

You are given an n × n binary grid. You may change at most one 0 into a 1. Return the size of the largest island afterwards.

Difficulty: Hard
Topics: Arrays, Matrix, Breadth-First Search, Depth-First Search, Union Find
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an n × n binary grid. You may change at most one 0 into a 1.

Return the size of the largest island afterwards. An island is a group of 1s connected 4-directionally.

Example 1

Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Filling either `0` joins the two single cells.

Example 2

Input: grid = [[1,1],[1,0]]
Output: 4
Explanation: Filling the one `0` makes the whole grid an island.

Example 3

Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: There is no `0` to change; the island is already the whole grid.

Constraints

n == grid.length == grid[i].length
1 <= n <= 500
grid[i][j] is 0 or 1

How to solve Making A Large Island

Label every island with an id and its size in one pass. Then each candidate 0 is answered in O(1): the new island is the cell itself plus the distinct islands touching it.

Approach

Flood fill each island, writing an id (starting at 2, so it never collides with 0 or 1) into every cell and recording its size.
Start the answer at the largest existing island, which covers a grid with no 0.
For each 0, collect the distinct ids of its up-to-four neighbours, sum their sizes and add 1.
Return the best total.

Why it works

De-duplicating the neighbour ids is the crux: two neighbouring cells may belong to the same island, and counting it twice inflates the answer. Starting the answer at the largest existing island covers the case where the grid is all 1s and no change is possible.

Complexity

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

Pitfalls

Counting the same island twice around one 0 over-counts — at most four neighbours, so a small list is enough to de-duplicate.
Ids must start above 1 or they collide with the grid's own values.
An all-ones grid has no 0 to flip; seed the answer with the largest island.

Reference solution

Python

from typing import List

def largestIsland(grid: List[List[int]]) -> int:
    n = len(grid)
    label = [[0] * n for _ in range(n)]
    sizes = [0, 0]
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    ident = 2
    for i in range(n):
        for j in range(n):
            if grid[i][j] != 1 or label[i][j] != 0:
                continue
            size = 0
            stack = [(i, j)]
            label[i][j] = ident
            while stack:
                r, c = stack.pop()
                size += 1
                for di, dj in dirs:
                    nr, nc = r + di, c + dj
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1 and label[nr][nc] == 0:
                        label[nr][nc] = ident
                        stack.append((nr, nc))
            sizes.append(size)
            ident += 1
    best = max(sizes)
    for i in range(n):
        for j in range(n):
            if grid[i][j] != 0:
                continue
            near = set()
            for di, dj in dirs:
                nr, nc = i + di, j + dj
                if 0 <= nr < n and 0 <= nc < n and label[nr][nc]:
                    near.add(label[nr][nc])
            best = max(best, 1 + sum(sizes[k] for k in near))
    return best

JavaScript

var largestIsland = function(grid) {
    var n = grid.length, i, j, d;
    var label = [];
    for (i = 0; i < n; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(0);
        label.push(row);
    }
    var sizes = [0, 0];
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var id = 2;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (grid[i][j] !== 1 || label[i][j] !== 0) continue;
            var size = 0;
            var stack = [i * n + j];
            label[i][j] = id;
            while (stack.length > 0) {
                var cur = stack.pop();
                var r = Math.floor(cur / n), c = cur % n;
                size++;
                for (d = 0; d < 4; d++) {
                    var nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                    if (grid[nr][nc] !== 1 || label[nr][nc] !== 0) continue;
                    label[nr][nc] = id;
                    stack.push(nr * n + nc);
                }
            }
            sizes.push(size);
            id++;
        }
    }
    var best = 0;
    for (var k = 2; k < sizes.length; k++) if (sizes[k] > best) best = sizes[k];
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (grid[i][j] !== 0) continue;
            var total = 1;
            var near = [];
            for (d = 0; d < 4; d++) {
                var ar = i + dr[d], ac = j + dc[d];
                if (ar < 0 || ar >= n || ac < 0 || ac >= n) continue;
                var lb = label[ar][ac];
                if (lb === 0 || near.indexOf(lb) >= 0) continue;
                near.push(lb);
                total += sizes[lb];
            }
            if (total > best) best = total;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue