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.
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.
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.
Python
JavaScript
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.
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.
The program starts by implementing a union-find class to handle connected components effectively. The isConnected function sets up the union-find structure, uniting land cells that are connected. Through union-find's efficiency, we can quickly assess if the grid is disconnected. If the initial grid has multiple islands, it returns 0. The function evaluates single cell changes using union-find as a checker for grid disconnection, ensuring optimized performance.
Time Complexity: O((m*n))
Space Complexity: O(m*n)
Python
Java
C++
Go
TypeScript
JavaScript
| 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 | — |
| 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. |
Minimum Number of Days to Disconnect Island - Leetcode 1568 - Python • NeetCodeIO • 17,245 views views
Watch 9 more video solutions →Practice Minimum Number of Days to Disconnect Island with our built-in code editor and test cases.
Practice on FleetCode