Minimum Number of Days to Disconnect Island — Hard Problem & Solution

A binary grid holds 1 for land and 0 for water. An island is a group of land cells connected 4-directionally, and the grid is connected when it holds…

Difficulty: Hard
Topics: Arrays, Matrix, Breadth-First Search, Depth-First Search, Biconnected Component
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

A binary grid holds 1 for land and 0 for water. An island is a group of land cells connected 4-directionally, and the grid is connected when it holds exactly one island.

In one day you may turn any single land cell into water. Return the minimum number of days needed to leave the grid disconnected — either with no island at all, or with two or more.

Example 1

Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]
Output: 2
Explanation: Remove any single cell and the 2 × 2 block stays one island; two removals split it.

Example 2

Input: grid = [[1,1]]
Output: 2
Explanation: Removing one cell leaves a single land cell — still one island.

Example 3

Input: grid = [[1,0,1,0]]
Output: 0
Explanation: Already two islands.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 30
grid[i][j] is 0 or 1

How to solve Minimum Number of Days to Disconnect Island

The answer is always 0, 1 or 2. Test 0 by counting islands, test 1 by trying every single removal, and otherwise answer 2.

Approach

Count the islands; if the count is not exactly 1, the grid is already disconnected — return 0.
For each land cell, set it to water, re-count, and restore it. If any removal leaves a count other than 1, return 1.
Otherwise return 2.

Why it works

Two days always suffice: take any corner-most land cell of the island; it has at most two land neighbours, and removing them isolates or erases it. So the search never needs to go past 2, which is what makes brute force over single removals a complete algorithm rather than a heuristic.

Complexity

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

Pitfalls

A grid with no land is already disconnected and answers 0.
Removing a cell can also leave zero islands — that counts as disconnected.
Restore the cell after each trial or later trials see a corrupted grid.

Reference solution

Python

from typing import List

def minDays(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))

    def islands() -> int:
        seen = [[False] * n for _ in range(m)]
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] != 1 or seen[i][j]:
                    continue
                count += 1
                stack = [(i, j)]
                seen[i][j] = True
                while stack:
                    r, c = stack.pop()
                    for di, dj in dirs:
                        nr, nc = r + di, c + dj
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1 and not seen[nr][nc]:
                            seen[nr][nc] = True
                            stack.append((nr, nc))
        return count

    if islands() != 1:
        return 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] != 1:
                continue
            grid[i][j] = 0
            cnt = islands()
            grid[i][j] = 1
            if cnt != 1:
                return 1
    return 2

JavaScript

var minDays = function(grid) {
    var m = grid.length, n = grid[0].length;
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var islands = function() {
        var seen = [], i, j;
        for (i = 0; i < m; i++) {
            var row = [];
            for (j = 0; j < n; j++) row.push(false);
            seen.push(row);
        }
        var count = 0;
        for (i = 0; i < m; i++) {
            for (j = 0; j < n; j++) {
                if (grid[i][j] !== 1 || seen[i][j]) continue;
                count++;
                var stack = [i * n + j];
                seen[i][j] = true;
                while (stack.length > 0) {
                    var cur = stack.pop();
                    var r = Math.floor(cur / n), c = cur % n;
                    for (var k = 0; k < 4; k++) {
                        var nr = r + dr[k], nc = c + dc[k];
                        if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                        if (grid[nr][nc] !== 1 || seen[nr][nc]) continue;
                        seen[nr][nc] = true;
                        stack.push(nr * n + nc);
                    }
                }
            }
        }
        return count;
    };
    if (islands() !== 1) return 0;
    for (var i = 0; i < m; i++) {
        for (var j = 0; j < n; j++) {
            if (grid[i][j] !== 1) continue;
            grid[i][j] = 0;
            var cnt = islands();
            grid[i][j] = 1;
            if (cnt !== 1) return 1;
        }
    }
    return 2;
};

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

All 667 arrays problems · the whole catalogue