Making A Large Island

Hard
923.

Making A Large Island

Making A Large Island is a hard coding problem on arrays, depth-first search and matrix, asked in Amazon, Google, Microsoft and Snapchat interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Making A Large Island — Solution in Python, Java & C++

Making A Large Island solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Making A Large Island is a hard coding problem on arrays, depth-first search and matrix, asked in Amazon, Google, Microsoft and Snapchat interviews.

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

Hints for Making A Large Island

  1. Hint 1

    Re-running a flood fill for every 0 is O(n^4).

  2. Hint 2

    Label the islands once and record each one's size.

  3. Hint 3

    For each 0, add up the sizes of the distinct island labels around it, plus one for the cell itself.

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

  1. 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.
  2. Start the answer at the largest existing island, which covers a grid with no 0.
  3. For each 0, collect the distinct ids of its up-to-four neighbours, sum their sizes and add 1.
  4. 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

Java

public static int largestIsland(int[][] grid) {
    int n = grid.length;
    int[][] label = new int[n][n];
    List<Integer> sizes = new ArrayList<>();
    sizes.add(0);
    sizes.add(0);
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    int[] stack = new int[n * n];
    int id = 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 1 || label[i][j] != 0) continue;
            int size = 0, top = 0;
            stack[top++] = i * n + j;
            label[i][j] = id;
            while (top > 0) {
                int cur = stack[--top];
                int r = cur / n, c = cur % n;
                size++;
                for (int d = 0; d < 4; d++) {
                    int 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[top++] = nr * n + nc;
                }
            }
            sizes.add(size);
            id++;
        }
    }
    int best = 0;
    for (int k = 2; k < sizes.size(); k++) best = Math.max(best, sizes.get(k));
    int[] near = new int[4];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 0) continue;
            int total = 1, cnt = 0;
            for (int d = 0; d < 4; d++) {
                int nr = i + dr[d], nc = j + dc[d];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                int lb = label[nr][nc];
                if (lb == 0) continue;
                boolean dup = false;
                for (int k = 0; k < cnt; k++) if (near[k] == lb) dup = true;
                if (dup) continue;
                near[cnt++] = lb;
                total += sizes.get(lb);
            }
            best = Math.max(best, total);
        }
    }
    return best;
}

C++

int largestIsland(vector<vector<int>>& grid) {
    int n = (int) grid.size();
    vector<vector<int>> label(n, vector<int>(n, 0));
    vector<int> sizes = { 0, 0 };
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    int id = 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 1 || label[i][j] != 0) continue;
            int size = 0;
            vector<int> stack;
            stack.push_back(i * n + j);
            label[i][j] = id;
            while (!stack.empty()) {
                int cur = stack.back();
                stack.pop_back();
                int r = cur / n, c = cur % n;
                size++;
                for (int d = 0; d < 4; d++) {
                    int 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_back(nr * n + nc);
                }
            }
            sizes.push_back(size);
            id++;
        }
    }
    int best = 0;
    for (size_t k = 2; k < sizes.size(); k++) best = max(best, sizes[k]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 0) continue;
            int total = 1, cnt = 0, near[4] = { 0, 0, 0, 0 };
            for (int d = 0; d < 4; d++) {
                int nr = i + dr[d], nc = j + dc[d];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                int lb = label[nr][nc];
                if (lb == 0) continue;
                bool dup = false;
                for (int k = 0; k < cnt; k++) if (near[k] == lb) dup = true;
                if (dup) continue;
                near[cnt++] = lb;
                total += sizes[lb];
            }
            best = max(best, total);
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Depth-First Search (DFS)