Watch 10 video solutions for Minimum Number of Days to Disconnect Island, a hard level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by NeetCodeIO has 17,245 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 either 0 or 1.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 | 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. |