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.
- Difficulty: Hard
- Topics: Arrays, Depth-First Search, Matrix, Breadth-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.lengthn == grid[i].length1 <= m, n <= 30grid[i][j] is 0 or 1
Hints for Minimum Number of Days to Disconnect Island
Hint 1
Check first whether the grid is already disconnected — that costs 0 days.
Hint 2
Try turning each single land cell to water and re-count the islands.
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
- 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 2Java
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)