hard Minimum Number of Days to Disconnect Island

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

1. 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.

2. 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.

3. 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.

4. 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).

5. 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.

6. 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:

1. Initialize Variables:

   • numRows = 3, numCols = 3.
   • separationInfo is initialized with hasCriticalPoint = false, discoveryTime = 0.
   • discoveryTime, lowestTimeReachable, and parentCell arrays are all initialized to -1.

2. Set Default Values:

   • All cells in discoveryTime, lowestTimeReachable, and parentCell are set to -1.

3. 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.

4. 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.

5. End of DFS:

   • All cells are visited, and articulation points are found at (2, 1) and (1, 1).

6. Final Decision:

   • Since hasCriticalPoint is true, return 1 day to disconnect the grid.

Output:

Output: 1

Code

import java.util.Arrays;

public class Solution {

  // Directions to check adjacent cells
  private static final int[][] DIRECTIONS = {
    { 0, 1 },
    { 1, 0 },
    { 0, -1 },
    { -1, 0 },
  };

  public int minDays(int[][] grid) {
    int numRows = grid.length,
      numCols = grid[0].length;
    IslandSeparationInfo separationInfo = new IslandSeparationInfo(false, 0); // To keep track of articulation points
    int totalLandCells = 0,
      totalIslands = 0;

    // Arrays to store discovery time, the lowest reachable time, and the parent cell in DFS
    int[][] discoveryTime = new int[numRows][numCols];
    int[][] lowestTimeReachable = new int[numRows][numCols];
    int[][] parentCell = new int[numRows][numCols];

    // Initialize arrays with default values
    for (int i = 0; i < numRows; i++) {
      Arrays.fill(discoveryTime[i], -1); // Set discovery time as not visited
      Arrays.fill(lowestTimeReachable[i], -1); // Set the lowest reachable time
      Arrays.fill(parentCell[i], -1); // Set parent of each cell to be undefined
    }

    // Loop through the grid to find all land cells and discover islands
    for (int row = 0; row < numRows; row++) {
      for (int col = 0; col < numCols; col++) {
        if (grid[row][col] == 1) {
          // If it's a land cell
          totalLandCells++; // Count total land cells
          if (discoveryTime[row][col] == -1) {
            // If this cell is not visited
            // Perform DFS to find articulation points and islands
            findCriticalPoints(
              grid,
              row,
              col,
              discoveryTime,
              lowestTimeReachable,
              parentCell,
              separationInfo
            );
            totalIslands++; // Count the number of islands
          }
        }
      }
    }

    // Determine the minimum number of days required to disconnect the grid
    if (totalIslands == 0 || totalIslands >= 2) return 0; // Already disconnected or no land
    if (totalLandCells == 1) return 1; // Only one land cell present
    if (separationInfo.hasCriticalPoint) return 1; // At least one critical point found
    return 2; // No critical point, need to remove any two land cells
  }

  private void findCriticalPoints(
    int[][] grid,
    int row,
    int col,
    int[][] discoveryTime,
    int[][] lowestTimeReachable,
    int[][] parentCell,
    IslandSeparationInfo separationInfo
  ) {
    int numRows = grid.length,
      numCols = grid[0].length;
    discoveryTime[row][col] = separationInfo.discoveryTime; // Set discovery time
    separationInfo.discoveryTime++; // Increment the time for the next cell
    lowestTimeReachable[row][col] = discoveryTime[row][col]; // Initially, lowest reachable is the discovery time itself
    int childCount = 0; // Count children in DFS tree

    // Explore all four directions
    for (int[] direction : DIRECTIONS) {
      int newRow = row + direction[0]; // New row position
      int newCol = col + direction[1]; // New column position
      if (isValidLand(grid, newRow, newCol)) {
        // Check if the new cell is valid
        if (discoveryTime[newRow][newCol] == -1) {
          // If the new cell is not yet visited
          childCount++; // Increment child count
          parentCell[newRow][newCol] = row * numCols + col; // Set parent for the new cell
          findCriticalPoints(
            grid,
            newRow,
            newCol,
            discoveryTime,
            lowestTimeReachable,
            parentCell,
            separationInfo
          );

          // Update the lowest reachable time based on the child's lowest reachable time
          lowestTimeReachable[row][col] = Math.min(
            lowestTimeReachable[row][col],
            lowestTimeReachable[newRow][newCol]
          );

          // Check if the current cell is a critical point
          if (
            lowestTimeReachable[newRow][newCol] >= discoveryTime[row][col] &&
            parentCell[row][col] != -1
          ) {
            separationInfo.hasCriticalPoint = true; // Mark that a critical point exists
          }
        } else if (newRow * numCols + newCol != parentCell[row][col]) {
          // Update the lowest reachable time considering a back edge
          lowestTimeReachable[row][col] = Math.min(
            lowestTimeReachable[row][col],
            discoveryTime[newRow][newCol]
          );
        }
      }
    }

    // Root of DFS tree is a critical point if it has more than one child
    if (parentCell[row][col] == -1 && childCount > 1) {
      separationInfo.hasCriticalPoint = true;
    }
  }

  // Check if the cell is a valid land cell
  private boolean isValidLand(int[][] grid, int row, int col) {
    int numRows = grid.length,
      numCols = grid[0].length;
    return (
      row >= 0 &&
      col >= 0 &&
      row < numRows &&
      col < numCols &&
      grid[row][col] == 1
    );
  }

  // Helper class to store information about grid separation
  private class IslandSeparationInfo {

    boolean hasCriticalPoint; // To indicate if there is any critical point
    int discoveryTime; // To keep track of discovery time

    IslandSeparationInfo(boolean hasCriticalPoint, int discoveryTime) {
      this.hasCriticalPoint = hasCriticalPoint;
      this.discoveryTime = discoveryTime;
    }
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int[][] grid1 = { { 1, 1, 0 }, { 1, 1, 0 }, { 0, 1, 1 } };
    System.out.println("Output: " + solution.minDays(grid1)); // Expected Output: 1

    // Example 2
    int[][] grid2 = { { 1, 0, 0, 1 }, { 0, 1, 1, 0 }, { 1, 0, 0, 1 } };
    System.out.println("Output: " + solution.minDays(grid2)); // Expected Output: 0

    // Example 3
    int[][] grid3 = { { 1, 1, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 1 } };
    System.out.println("Output: " + solution.minDays(grid3)); // Expected Output: 2
  }
}

Complexity Analysis

Time Complexity

• The time complexity of the solution is , 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 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 .

Space Complexity

• The space complexity of the solution is .
• 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 in the worst case, depending on the layout of the grid.