{x}
blog image

Minimum Number of Days to Disconnect Island

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.length
  • n == grid[i].length
  • 1 <= m, n <= 30
  • grid[i][j] is either 0 or 1.

Solution Explanation:

This problem asks for the minimum number of days to disconnect a given grid representing land (1) and water (0). A grid is disconnected if it has more than one island. The solution cleverly leverages Depth-First Search (DFS) to count islands and determine the minimum days needed.

Approach:

The core idea is to iteratively try removing single land cells and check if the resulting grid is disconnected.

  1. Island Counting: A count() function uses DFS to traverse and mark all connected land cells as visited. It returns the number of islands. Crucially, it restores the original grid state after counting.

  2. One-Day Check: The main logic iterates through each land cell. It temporarily changes the land cell to water, counts the islands. If the count is not 1 (meaning the grid is disconnected), it means we found a solution in one day, and we return 1. Otherwise, the cell is reset to land.

  3. Two-Day Case: If the single-cell removal doesn't disconnect the island, then at least two cells must be removed. The solution directly returns 2 in this case because it's impossible to disconnect the island in less than two days (considering the constraints).

  4. Zero-Island Case: If the initial grid has more than one island or zero islands, it's already disconnected, so it returns 0.

Time Complexity Analysis:

  • count() function: The DFS in count() visits each cell at most once. Therefore, its time complexity is O(M*N), where M and N are the dimensions of the grid.

  • Main loop: The main loop iterates through all cells of the grid (O(M*N)). Inside the loop, count() is called.

  • Overall: The overall time complexity is dominated by the nested loops and repeated calls to count(), resulting in O(M*N)^2. However, in practice, it's often less because disconnecting usually happens early.

Space Complexity Analysis:

The space complexity is determined by the recursive call stack of the DFS function which is at most O(MN) in the worst-case scenario where the grid is a single connected island. The additional space used by the visited array in the DFS is also O(MN). Thus, the overall space complexity is O(M*N).

Code Explanation (Python):

The provided Python code implements this approach clearly. The count() function employs DFS to identify connected components (islands). The main part iterates through all cells to test for one-day disconnection. If none is found, it implies that at least two days are needed.

Code Explanation (Other Languages):

The provided Java, C++, Go, TypeScript, and JavaScript codes follow the same algorithmic approach, differing only in syntax and specific library functions used. Each language version maintains the same core structure of the count() function and the main logic to check for one-day or two-day disconnections.