Solution: Minimum Number of Days to Disconnect Island

Advanced Coding Patterns for Interviews

0% completed

Problem Statement

You are given a binary grid of size m x n, where each cell can either be land (marked as 1) or water (marked as 0). An island is a group of connected land cells (1s) that are adjacent either horizontally or vertically.

The grid is considered connected if it contains exactly one island.

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.

Examples

Example 1:

Input: grid =
```
[[1, 1, 0], 
 [1, 1, 0], 
 [0, 1, 1]]
```
Expected Output: 1

Justification: Changing any of the land cells in the first island (like grid[1][1] or grid[2][1]) will break the connection, creating two separate islands or making it impossible to connect. Therefore, only one day is needed.

Example 2:

Input: grid =

[[1, 0, 0, 1], 
 [0, 1, 1, 0], 
 [1, 0, 0, 1]]

Expected Output: 0

Justification: There are a total 5 islands. So, we don't need 0 days to disconnect them.

Example 3:

Input: grid =

[[1, 1, 1, 1], 
 [1, 1, 1, 1], 
 [1, 1, 1, 1]]

Expected Output: 2

Justification: We need 2 days to change land to water cell at position grid[0][1] and grid[1][0].

Solution

To solve this problem, we will use Tarjan's Algorithm for finding articulation points in a graph. In this problem, each land cell (1) in the grid represents a vertex in the graph, and an edge exists between two vertices if their corresponding cells are adjacent (either horizontally or vertically). The goal is to find the minimum number of days required to disconnect the grid by turning land cells (1) into water cells (0).

Our approach involves running a Depth-First Search (DFS) on the grid to identify these articulation points. The DFS traversal allows us to calculate the discovery time (when a cell is first visited) and the lowest time reachable (the earliest visited vertex reachable from the subtree rooted at that cell). If an articulation point is found, the minimum number of days required to disconnect the grid is 1; otherwise, we may need to turn two land cells into water to achieve disconnection. If there is more than one island initially or no land cells, the grid is already disconnected.

Step-by-Step Algorithm

Initialize Variables:
- Set numRows to the number of rows in the grid and numCols to the number of columns.
- Create an instance of IslandSeparationInfo named separationInfo to keep track of whether an articulation point (critical point) is found (hasCriticalPoint) and the discovery time (discoveryTime).
- Define 2D arrays discoveryTime, lowestTimeReachable, and parentCell to store the discovery time, lowest reachable discovery time, and parent cell in the DFS tree for each cell in the grid.
- Initialize totalLandCells and totalIslands to zero.
Set Default Values:
- Loop through each cell in the grid and set the values of discoveryTime, lowestTimeReachable, and parentCell to -1 to indicate that these cells are unvisited and undefined.
Count Islands and Perform DFS:
- Loop through each cell in the grid:
  - For every land cell (grid[row][col] == 1), increment totalLandCells.
  - If the cell has not been visited (discoveryTime[row][col] == -1), initiate a DFS from this cell by calling findCriticalPoints function.
  - Each DFS traversal identifies articulation points and counts the number of islands. Increment totalIslands after each DFS traversal.
Determine Minimum Days to Disconnect:
- Check the total number of islands:
  - If totalIslands is 0 or greater than 1, return 0 (the grid is already disconnected).
  - If there is only one land cell (totalLandCells == 1), return 1 (one day is sufficient to disconnect the grid).
  - If an articulation point (hasCriticalPoint) is found, return 1 (removing the critical point will disconnect the grid).
  - Otherwise, return 2 (disconnecting the grid will require removing at least two land cells).
Depth-First Search for Articulation Points (findCriticalPoints):
- Set the discovery time of the current cell (discoveryTime[row][col]) to the current discovery time from separationInfo.
- Increment the global discovery time (separationInfo.discoveryTime).
- Initialize the lowest reachable time of the current cell (lowestTimeReachable[row][col]) to its discovery time.
- Set childCount to 0 to keep track of the number of child nodes for this DFS.
- Explore all four possible directions (right, down, left, up):
  - For each valid adjacent land cell that hasn't been visited:
    - Increment childCount.
    - Set the parent of the adjacent cell to the current cell.
    - Recursively call findCriticalPoints on the adjacent cell.
    - After returning from recursion, update the lowest reachable time for the current cell using the child’s lowest reachable time.
    - Check if the current cell is a critical point. If the lowest reachable time of the child is greater than or equal to the discovery time of the current cell and it's not the root, mark it as an articulation point. It means current cell doesn't have any back edge.
  - For already visited adjacent cells that are not the parent of the current cell, update the lowest reachable time of the current cell using the discovery time of the adjacent cell. Here, we ignore back edge to the parent cell.
- After checking all directions, if the current cell is the root of the DFS tree and has more than one child, mark it as an articulation point.
Utility Function (isValidLand):
- Check if a given cell is within the bounds of the grid and is a land cell (1).

Algorithm Walkthrough

Let's demonstrate a step-by-step walkthrough for the input grid:

Input:

[[1, 1, 0], 
 [1, 1, 0], 
 [0, 1, 1]]

Steps:

Initialize Variables:
- numRows = 3, numCols = 3.
- separationInfo is initialized with hasCriticalPoint = false, discoveryTime = 0.
- discoveryTime, lowestTimeReachable, and parentCell arrays are all initialized to -1.
Set Default Values:
- All cells in discoveryTime, lowestTimeReachable, and parentCell are set to -1.
Count Islands and Perform DFS:
- Start at grid[0][0] (first cell, which is land 1):
  - Increment totalLandCells to 1.
  - Since discoveryTime[0][0] == -1, start DFS from this cell.
DFS from grid[0][0]:
- Set discoveryTime[0][0] = 0, increment global discoveryTime to 1.
- Set lowestTimeReachable[0][0] = 0.
- Explore adjacent cells:
  - Right to grid[0][1] (land 1):
    - Increment child count to 1.
    - Start DFS from grid[0][1].
    - Set discoveryTime[0][1] = 1, increment global discoveryTime to 2.
    - Set lowestTimeReachable[0][1] = 1.
    - Explore further:
      - Down to grid[1][1] (land 1):
        
        Increment child count to 1.
        
        Start DFS from grid[1][1].
        
        Set discoveryTime[1][1] = 2, increment global discoveryTime to 3.
        
        Set lowestTimeReachable[1][1] = 2.
        
        Explore further:
        
        Down to grid[2][1] (land 1):
        
        Increment child count to 1.
        
        Start DFS from grid[2][1].
        
        Set discoveryTime[2][1] = 3, increment global discoveryTime to 4.
        
        Set lowestTimeReachable[2][1] = 3.
        
        Explore further:
        
        Right to grid[2][2] (land 1):
        
        Increment child count to 1.
        
        Start DFS from grid[2][2].
        
        Set discoveryTime[2][2] = 4, increment global discoveryTime to 5.
        
        Set lowestTimeReachable[2][2] = 4.
        
        No more valid cells to explore.
        
        Backtrack to grid[2][1]:
        
        Update lowestTimeReachable[2][1] = min(3, 4) = 3.
        
        Check articulation point condition:
        
        lowestTimeReachable[2][2] >= discoveryTime[2][1] (4 >= 3) and parentCell[0][1] != -1.
        
        Mark grid[2][1] as an articulation point (separationInfo.hasCriticalPoint = true).
      - No more valid cells to explore.
        
        Backtrack to grid[1][1]:
        
        Update lowestTimeReachable[1][1] = min(2, 3) = 2.
        
        Check articulation point condition:
        
        lowestTimeReachable[2][1] >= discoveryTime[1][1] (3 >= 2) and parentCell[1][1] != -1.
        
        Mark grid[1][1] as an articulation point (separationInfo.hasCriticalPoint = true).
        
        Backtrack to grid[0][1]:
        
        Update lowestTimeReachable[0][1] = min(1, 2) = 1.
  - Back to grid[0][0], continue exploration:
    - All nodes are visited.
End of DFS:
- All cells are visited, and articulation points are found at (2, 1) and (1, 1).
Final Decision:
- Since hasCriticalPoint is true, return 1 day to disconnect the grid.

Output:

Output: 1

Code

Python3

. . . .

Complexity Analysis

Time Complexity

The time complexity of the solution is O((m * n)), where m is the number of rows and n is the number of columns in the grid.
- Depth-First Search (DFS): Each DFS traversal takes $O(m * n)$ time in the worst case, as we may need to visit every cell in the grid.
So, the overall time complexity of the algorithm is $O(m * n)$ .

Space Complexity

The space complexity of the solution is $O(m * n)$ .
This includes:
- Auxiliary Arrays: discoveryTime, lowestTimeReachable, and parentCell, each of which has a size of m * n.
- Recursive Stack: The depth of the recursion can go up to $O(m * n)$ in the worst case, depending on the layout of the grid.

.....

Like the course? Get enrolled and start learning!