Minimum Number of Days to Disconnect Island solution and explanation
Google
9 more videos on this problem
Minimum Number of Days to Disconnect Island - Leetcode 1568 - PythonNeetCodeIO · 15:46 · 17K views
Minimum Number of Days to Disconnect Island | Studied Concept | Leetcode 1568 | codestorywithMIKcodestorywithMIK · 24:20 · 12K views
LeetCode 1568. Minimum Number of Days to Disconnect IslandHappy Coding · 17:56 · 3K views
LEETCODE 1568. Minimum Number of Days to Disconnect IslandAbrar Sher · 11:59 · 1K views
1568. Minimum Number of Days to Disconnect Island | LeetCode | Weekly Contest 204CP Addict · 16:46 · 1K views
1568. Minimum Number of Days to Disconnect Island (Leetcode Medium)Programming Live with Larry · 20:06 · 730 views
LeetCode 1568 - Minimum Number of Days to Disconnect Island - JavaAlpha-Code · 15:03 · 673 views
Minimum Number of Days to Disconnect Island (LeetCode 1568) (HARD) (DFS) (GRAPH)CodeWithARB · 37:49 · 607 views
LeetCode 1568. [Medium] Minimum Number of Days to Disconnect IslandFrancesco Manicardi · 5:04 · 453 views
Leetcode Daily Challenge Solution |1568 Minimum Number of Days To Disconnect Island | DFS | JAVA SoCakot Coding · 21:52 · 390 views
The problem
You are given an m x n binary grid grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally (horizontal or vertical) connected group of 1's.
The grid is said to be connected if we have exactly one island, otherwise is said disconnected.
In one day, we are allowed to change any single land cell (1) into a water cell (0).
Return the minimum number of days to disconnect the grid.
Example 1:
Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]] Output: 2 Explanation: We need at least 2 days to get a disconnected grid. Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.
Example 2:
Input: grid = [[1,1]] Output: 2 Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 30grid[i][j]is either0or1.
Approach overview
Problem Overview: You are given a binary grid where 1 represents land and 0 represents water. Each day you can convert one land cell into water. The task is to compute the minimum number of days required so the grid no longer contains exactly one connected island.
Approach 1: BFS/DFS Island Counting with Cell Removal (O((m*n)^2) time, O(m*n) space)
The key observation: the answer is always 0, 1, or 2. First count islands using a standard traversal like Depth-First Search or Breadth-First Search. If the grid already has 0 or more than 1 island, it is already disconnected, so return 0. Otherwise, iterate through every land cell, temporarily flip it to water, and run BFS/DFS again to recount islands. If the grid becomes disconnected after removing that cell, return 1. Restore the cell after each test. If no single removal works, the answer must be 2. This brute-force check works because a connected island graph can always be disconnected by removing at most two vertices.
This approach relies on repeated traversal of the matrix. Each island count takes O(m*n), and you may test up to m*n cells.
Approach 2: Union-Find Connectivity Tracking (O((m*n)^2) time, O(m*n) space)
A second strategy models the grid as a graph and tracks connectivity using a Union-Find (Disjoint Set Union) structure. Initially union adjacent land cells to build connected components. If more than one component already exists, return 0. Then simulate removing each land cell: rebuild the union structure for the remaining grid and check the number of connected components. If removing a single cell splits the island into multiple components, return 1. If every single removal still leaves exactly one island, the grid requires two removals.
Union-Find simplifies connectivity checks and avoids recursive traversal logic, but rebuilding the structure for each removal still leads to O((m*n)^2) time.
Recommended for interviews: The BFS/DFS island-count approach is the expected solution. It is straightforward, easy to reason about, and directly demonstrates graph traversal skills. Mentioning why the answer cannot exceed two days shows deeper understanding of connectivity properties, which interviewers value in grid graph problems.
Approach 1: Using BFS for island count and cell transformation
This approach employs a breadth-first search (BFS) to explore the grid, counting the number of islands. Initially, it checks if the grid is already disconnected. If not, it attempts to disconnect the grid by changing each land cell to water one-by-one, checking the number of islands created each time. If the transformation disconnects the grid, the process stops early. This approach is based on the premise that if converting any one land cell to water does not suffice, converting two will.
def minDays(grid):
def connected():
seen = set()
def dfs(r, c):
if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0 or (r, c) in seen:
return 0
seen.add((r, c))
for x, y in ((r, c+1), (r+1, c), (r, c-1), (r-1, c)):
dfs(x, y)
return 1
cnt = sum(dfs(r, c) for r in range(len(grid)) for c in range(len(grid[0])))
return cnt != 1
if connected():
return 0
rows, cols = len(grid), len(grid[0])
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
grid[r][c] = 0
if connected():
return 1
grid[r][c] = 1
return 2function minDays(grid) {
const directions = [[0,1],[1,0],[0,-1],[-1,0]];
function disconnected() {
const visited = new Array(grid.length).fill().map(() => new Array(grid[0].length).fill(false));
let islands = 0;
function dfs(r, c) {
const stack = [[r, c]];
while (stack.length) {
const [x, y] = stack.pop();
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || visited[x][y] || grid[x][y] === 0) continue;
visited[x][y] = true;
for (const [dx, dy] of directions) stack.push([x + dx, y + dy]);
}
}
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] === 1 && !visited[r][c]) {
dfs(r, c);
islands++;
}
}
}
return islands !== 1;
}
if (disconnected()) return 0;
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
if (grid[r][c] === 1) {
grid[r][c] = 0;
if (disconnected()) return 1;
grid[r][c] = 1;
}
}
}
return 2;
}The function connected() uses BFS to count the number of islands. Initially, if the grid is already disconnected (more than one island), it returns 0. Otherwise, it tries flipping each 1 to 0 and checks again if the grid becomes disconnected. If so, it returns 1. If no single flip works, it's guaranteed disconnect happens after flipping two cells, hence returning 2.
Time Complexity: O((m*n)^2), where m and n are grid dimensions due to the nested loop and re-evaluation of the grid connect status for each cell transformation.
Space Complexity: O(m*n) for the BFS queue and visited marker.
Approach 2: Using Union-Find Structure
This approach utilizes a union-find (disjoint set union, DSU) data structure to efficiently manage and check connected components within the grid. Initially, it checks the number of islands using the union-find approach. Then, it assesses the effect of converting each land cell to water, employing union-find to determine if it results in a disconnected structure.
class Solution {
private class UnionFind {
int[] parent, size;
UnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (size[rootX] < size[rootY]) {
parent[rootX] = rootY;
size[rootY] += size[rootX];
} else {
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
}
}
}
public int minDays(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
UnionFind uf = new UnionFind(rows * cols);
if (!isConnected(grid, uf, rows, cols, directions)) return 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 1) {
grid[r][c] = 0;
uf = new UnionFind(rows * cols);
if (!isConnected(grid, uf, rows, cols, directions)) return 1;
grid[r][c] = 1;
}
}
}
return 2;
}
private boolean isConnected(int[][] grid, UnionFind uf, int rows, int cols, int[][] directions) {
int islandCount = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 1) {
int idx = r * cols + c;
for (int[] d : directions) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && grid[nr][nc] == 1) {
uf.unite(idx, nr * cols + nc);
}
}
if (uf.find(idx) == idx) islandCount++;
if (islandCount > 1) return false;
}
}
}
return islandCount == 1;
}
}#include <vector>
#include <numeric>
using namespace std;
class UnionFind {
vector<int> parent, rank;
public:
UnionFind(int n) : parent(n), rank(n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int u) {
if (u != parent[u]) {
parent[u] = find(parent[u]);
}
return parent[u];
}
bool unite(int u, int v) {
int rootU = find(u), rootV = find(v);
if (rootU != rootV) {
if (rank[rootU] > rank[rootV]) parent[rootV] = rootU;
else if (rank[rootU] < rank[rootV]) parent[rootU] = rootV;
else { parent[rootV] = rootU; rank[rootU]++; }
return true;
}
return false;
}
};
int minDays(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
auto withinGrid = [&](int i, int j) { return i >= 0 && j >= 0 && i < m && j < n; };
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
function<bool()> isConnected = [&]() {
UnionFind uf(m * n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
for (auto &dir : directions) {
int ni = i + dir[0], nj = j + dir[1];
if (withinGrid(ni, nj) && grid[ni][nj] == 1) {
uf.unite(i*n + j, ni*n + nj);
}
}
}
}
}
int islandCount = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1 && uf.find(i*n + j) == i*n + j) {
islandCount++;
if (islandCount > 1) return false;
}
}
}
return islandCount == 1;
};
if (!isConnected()) return 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
grid[i][j] = 0;
if (!isConnected()) return 1;
grid[i][j] = 1;
}
}
}
return 2;
}The Java solution mirrors the C++ implementation using a Union-Find class. Each land cell is checked for connectivity to its neighbors through union operations. This approach ensures disjoint set operations handle cell grouping efficiently. The method validates the current connectivity state, attempts pivotal cell transformations, and concludes on the minimum transformations required.
Time Complexity: O((m*n))
Space Complexity: O(m*n)
Approach 3: Default Approach
function minDays(grid: number[][]): number {
const [m, n] = [grid.length, grid[0].length];
const dfs = (i: number, j: number) => {
if (i < 0 || m <= i || j < 0 || n <= j || [0, 2].includes(grid[i][j])) return;
grid[i][j] = 2;
const dir = [-1, 0, 1, 0, -1];
for (let k = 0; k < 4; k++) {
const [y, x] = [i + dir[k], j + dir[k + 1]];
dfs(y, x);
}
};
const count = () => {
let c = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
dfs(i, j);
c++;
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) {
grid[i][j] = 1;
}
}
}
return c;
};
if (count() !== 1) return 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
grid[i][j] = 0;
if (count() !== 1) return 1;
grid[i][j] = 1;
}
}
}
return 2;
}func minDays(grid [][]int) int {
m, n := len(grid), len(grid[0])
dirs := []int{-1, 0, 1, 0, -1}
var dfs func(i, j int)
dfs = func(i, j int) {
grid[i][j] = 2
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 {
dfs(x, y)
}
}
}
count := func() int {
cnt := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
dfs(i, j)
cnt++
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 2 {
grid[i][j] = 1
}
}
}
return cnt
}
if count() != 1 {
return 0
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
grid[i][j] = 0
if count() != 1 {
return 1
}
grid[i][j] = 1
}
}
}
return 2
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using BFS for island count and cell transformation | Time Complexity: O((m*n)^2), where m and n are grid dimensions due to the nested loop and re-evaluation of the grid connect status for each cell transformation. Space Complexity: O(m*n) for the BFS queue and visited marker. |
| Using Union-Find Structure | Time Complexity: O((m*n)) Space Complexity: O(m*n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS/DFS Island Counting with Cell Removal | O((m*n)^2) | O(m*n) | Best general solution. Simple traversal and easy to explain in interviews. |
| Union-Find Connectivity Simulation | O((m*n)^2) | O(m*n) | Useful if you prefer disjoint-set connectivity modeling instead of repeated DFS/BFS. |
Frequently asked questions
Is Minimum Number of Days to Disconnect Island easy or hard?
The problem is rated Hard because it combines grid traversal with graph connectivity reasoning. While island counting itself is straightforward, recognizing that the answer is limited to 0, 1, or 2 days and efficiently testing cell removals requires deeper graph intuition.
Minimum Number of Days to Disconnect Island Python/Java solution
Python solutions typically implement DFS or BFS to count islands and simulate removing each land cell. Java implementations often follow the same traversal approach or use Union-Find to track connectivity. Both approaches achieve O((m*n)^2) time complexity and O(m*n) auxiliary space.
How to solve Minimum Number of Days to Disconnect Island in O(n)?
An O(n) solution is generally not used for this problem because you must evaluate connectivity after potential cell removals. The practical solution performs island counting multiple times, leading to O((m*n)^2) time. More advanced graph concepts like articulation points can theoretically reduce checks but add significant implementation complexity for grid graphs.
What is the best approach for Minimum Number of Days to Disconnect Island?
The most practical approach counts islands using BFS or DFS and simulates removing each land cell. First check if the grid already has zero or multiple islands. If it has exactly one island, temporarily remove each land cell and recount islands. This approach runs in O((m*n)^2) time and O(m*n) space and is the most commonly accepted interview solution.
Is Minimum Number of Days to Disconnect Island asked at Google/Amazon/Meta?
Grid connectivity and island problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving island counting, articulation points, and grid graph traversal are common because they test graph fundamentals, DFS/BFS implementation, and reasoning about connectivity.
What data structure is used in Minimum Number of Days to Disconnect Island?
The primary structures are a grid matrix and traversal structures used by DFS or BFS such as recursion stacks or queues. Some implementations also use a Union-Find (Disjoint Set Union) structure to track connected components dynamically.
What is the time complexity of Minimum Number of Days to Disconnect Island?
The standard solution runs in O((m*n)^2) time. Counting islands using DFS or BFS takes O(m*n), and in the worst case you attempt this check for every land cell in the grid. The space complexity is O(m*n) due to the visited matrix or recursion stack.