Minimum Number of Days to Disconnect Island

Hard
956.

Minimum Number of Days to Disconnect Island

Minimum Number of Days to Disconnect Island is a hard coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Microsoft interviews.

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
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 minDays = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Days to Disconnect Island — Solution

Minimum Number of Days to Disconnect Island solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Days to Disconnect Island is a hard coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Microsoft interviews.

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

Hints for Minimum Number of Days to Disconnect Island

  1. Hint 1

    Check first whether the grid is already disconnected — that costs 0 days.

  2. Hint 2

    Try turning each single land cell to water and re-count the islands.

  3. Hint 3

    If no single removal works, is more than two days ever needed?

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

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

Java

private static int mdIslands(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    boolean[][] seen = new boolean[m][n];
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    int count = 0;
    int[] stack = new int[m * n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 1 || seen[i][j]) continue;
            count++;
            int top = 0;
            stack[top++] = i * n + j;
            seen[i][j] = true;
            while (top > 0) {
                int cur = stack[--top];
                int r = cur / n, c = cur % n;
                for (int k = 0; k < 4; k++) {
                    int 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[top++] = nr * n + nc;
                }
            }
        }
    }
    return count;
}

public static int minDays(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    if (mdIslands(grid) != 1) return 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 1) continue;
            grid[i][j] = 0;
            int cnt = mdIslands(grid);
            grid[i][j] = 1;
            if (cnt != 1) return 1;
        }
    }
    return 2;
}

C++

static int mdIslands(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<vector<char>> seen(m, vector<char>(n, 0));
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    int count = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 1 || seen[i][j]) continue;
            count++;
            vector<int> stack = { i * n + j };
            seen[i][j] = 1;
            while (!stack.empty()) {
                int cur = stack.back();
                stack.pop_back();
                int r = cur / n, c = cur % n;
                for (int k = 0; k < 4; k++) {
                    int 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] = 1;
                    stack.push_back(nr * n + nc);
                }
            }
        }
    }
    return count;
}

int minDays(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    if (mdIslands(grid) != 1) return 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] != 1) continue;
            grid[i][j] = 0;
            int cnt = mdIslands(grid);
            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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

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