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.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.
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.
Java
Time Complexity: O((m*n))
Space Complexity: O(m*n)
| 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) |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,632 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