# Minimum Number of Days to Disconnect Island
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-days-to-disconnect-island
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-number-of-days-to-disconnect-island/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/minimum-number-of-days-to-disconnect-island/image1.jpg) 

**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`.

# Approaches
## Brute-Force Removal and Island Counting
This approach directly simulates the process described in the problem. It first checks the initial state of the grid. If the grid is already disconnected (meaning it has 0 or more than 1 island), the answer is 0 days. If the grid consists of a single island, the approach then tries to disconnect it by removing one land cell at a time. It iterates through every land cell, temporarily flipping it to water, and then recounts the number of islands. If the island count changes from one, it means we've successfully disconnected the grid in one day, and the answer is 1. If after trying to remove every single land cell, the island remains connected, we can conclude that the answer must be 2. This is because it's always possible to disconnect any island by removing at most two cells.
**Time:** O((M*N)^2). The `countIslands` function takes O(M*N) time. In the worst-case scenario for the 1-day check, we iterate through all M*N cells, and for each land cell, we call `countIslands`. This results in a total time complexity of O(M*N * M*N). · **Space:** O(M * N), where M and N are the dimensions of the grid. This space is used for the `visited` array in the `countIslands` function and for the recursion stack of the DFS, which in the worst case can be of size M*N.
**Pros:** Simple to understand and implement.; Directly models the problem statement without requiring complex algorithms.
**Cons:** The time complexity is high, O((M*N)^2), which might be too slow for larger grids, although it passes for the given constraints.; It performs a lot of redundant work by re-calculating the number of islands from scratch in each iteration.
### Explanation
The core of this method is a helper function, `countIslands(grid)`, which traverses the grid using DFS or BFS to count the number of separate islands.

- **Step 1: Initial Check (0 days).** Call `countIslands()` on the original grid. If the result is not 1, the grid is already disconnected. Return 0.

- **Step 2: Single Removal Check (1 day).** If there is exactly one island, iterate through every cell `(r, c)` of the grid.
    - If `grid[r][c]` is a land cell (value 1):
        - Temporarily change `grid[r][c]` to 0 (water).
        - Call `countIslands()` on the modified grid.
        - If the new island count is not 1 (i.e., 0 or >1), it means removing this single cell disconnects the island. We have found the solution. Return 1.
        - **Important:** Change `grid[r][c]` back to 1 to restore the grid for the next iteration.

- **Step 3: Default Case (2 days).** If the loop completes without finding any single cell that disconnects the island, it implies that at least two removals are necessary. The problem guarantees that 2 removals are always sufficient. Therefore, return 2.

```java
class Solution {
    private int m, n;
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public int minDays(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        if (countIslands(grid) != 1) {
            return 0;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    if (countIslands(grid) != 1) {
                        return 1;
                    }
                    grid[i][j] = 1; // backtrack
                }
            }
        }

        return 2;
    }

    private int countIslands(int[][] grid) {
        boolean[][] visited = new boolean[m][n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    dfs(grid, i, j, visited);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfs(int[][] grid, int r, int c, boolean[][] visited) {
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {
            return;
        }
        visited[r][c] = true;
        for (int[] dir : dirs) {
            dfs(grid, r + dir[0], c + dir[1], visited);
        }
    }
}
```
### Algorithm
1. Implement a helper function `countIslands(grid)` using a standard graph traversal algorithm like Depth First Search (DFS) or Breadth First Search (BFS).
2. Call `countIslands()` on the initial grid. If the number of islands is not equal to 1, the grid is already disconnected, so the answer is 0.
3. If there is exactly one island, iterate through every land cell `(r, c)` in the grid.
4. For each land cell, temporarily change its value from `1` (land) to `0` (water).
5. After this change, call `countIslands()` again on the modified grid.
6. If the new count of islands is not 1 (i.e., it's 0 or greater than 1), it means removing this single cell was enough to disconnect the island. Return 1.
7. **Important:** After checking, revert the cell's value back to `1` to restore the grid for the next iteration.
8. If the loop completes without finding any single cell removal that disconnects the island, it implies that at least two removals are necessary. Since it's always possible to disconnect an island with two removals, return 2.

## Efficient Check using Tarjan's Algorithm
This approach significantly optimizes the check for the 1-day scenario. After handling the 0-day case (by checking if the initial island count is not 1), it uses a more sophisticated graph algorithm to find 'articulation points' or 'cut vertices'. An articulation point is a land cell whose removal would split the single island into two or more smaller islands. Instead of removing each cell and recounting, this method finds all such critical cells in a single pass (a single DFS traversal).

If the algorithm finds even one articulation point, it means the island can be disconnected in 1 day. If the traversal completes and no such points are found, it proves that no single cell removal can disconnect the island, so the answer must be 2.
**Time:** O(M * N). The initial island counting takes O(M*N). The articulation point finding algorithm is a single DFS traversal over the graph of land cells, which also takes O(V+E) = O(M*N) time. The total complexity is therefore linear in the size of the grid. · **Space:** O(M * N). This space is required for the `visited`, `disc`, and `low` arrays, as well as the recursion stack for DFS.
**Pros:** Highly efficient with a linear time complexity of O(M*N).; Avoids redundant computations by checking for all possible 1-day disconnections in a single pass.
**Cons:** The implementation is significantly more complex than the brute-force approach.; Requires understanding of advanced graph algorithms (Tarjan's algorithm for articulation points).
### Explanation
The logic is refined to handle all cases efficiently.

- **Step 1: Initial Analysis.** First, count the number of islands and the total number of land cells. A single DFS/BFS pass can achieve this. If the island count is not 1 (i.e., 0 or >1), the grid is already disconnected, so return 0.

- **Step 2: Handle Small Islands.** If there is exactly one island, but it's very small, the answer is trivial. If there's only one land cell, it takes 1 day to remove it. If there are two land cells, it takes 2 days. So if `land_count <= 2`, return `land_count`.

- **Step 3: Articulation Point Search (1 day).** For a single island with more than two cells, we check for articulation points. This is done using a single DFS traversal. For each cell `u`, we maintain two values:
    - `disc[u]`: The discovery time of `u` (when `u` is first visited).
    - `low[u]`: The lowest discovery time reachable from `u` (including itself) through its DFS subtree, possibly using one back-edge to an ancestor.

    An articulation point `u` is detected if either of these conditions is met:
    - `u` is the root of the DFS tree and has more than one child.
    - `u` is not the root, and it has a child `v` such that `low[v] >= disc[u]`.

    If we find an articulation point, we can immediately return 1.

- **Step 4: Default Case (2 days).** If the DFS completes and no articulation points are found, the island is 2-vertex-connected. This means no single cell removal can disconnect it. Thus, the answer is 2.

```java
class Solution {
    private int m, n;
    private int[][] grid;
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private int[] disc, low;
    private int time;
    private boolean isArticulationPoint;

    public int minDays(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;

        if (countIslands() != 1) {
            return 0;
        }

        disc = new int[m * n];
        low = new int[m * n];
        java.util.Arrays.fill(disc, -1);
        time = 0;
        isArticulationPoint = false;

        // Find first land cell to start DFS
        for (int i = 0; i < m; i++) {
            boolean found = false;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    findArticulation(i, j, -1, -1);
                    found = true;
                    break;
                }
            }
            if (found) break;
        }

        return isArticulationPoint ? 1 : 2;
    }

    private void findArticulation(int r, int c, int pr, int pc) {
        int u = r * n + c;
        disc[u] = low[u] = time++;
        int children = 0;

        for (int[] dir : dirs) {
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] == 0) {
                continue;
            }
            
            if (nr == pr && nc == pc) {
                continue;
            }

            int v = nr * n + nc;
            if (disc[v] != -1) { // Visited node (back-edge)
                low[u] = Math.min(low[u], disc[v]);
            } else { // Not visited (tree-edge)
                children++;
                findArticulation(nr, nc, r, c);
                low[u] = Math.min(low[u], low[v]);

                if (pr == -1 && children > 1) {
                    isArticulationPoint = true;
                }
                if (pr != -1 && low[v] >= disc[u]) {
                    isArticulationPoint = true;
                }
            }
        }
    }

    private int countIslands() {
        boolean[][] visited = new boolean[m][n];
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    dfsCount(i, j, visited);
                    count++;
                }
            }
        }
        return count;
    }

    private void dfsCount(int r, int c, boolean[][] visited) {
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {
            return;
        }
        visited[r][c] = true;
        for (int[] dir : dirs) {
            dfsCount(r + dir[0], c + dir[1], visited);
        }
    }
}
```
### Algorithm
1. Implement a helper function to count the number of islands and the total number of land cells simultaneously.
2. Call this helper function. If the island count is not 1, return 0.
3. If the total land cell count is 1 or 2, return the land cell count. (A 1-cell island takes 1 day; a 2-cell island takes 2 days).
4. If there's one island with more than two cells, check for articulation points using a single DFS traversal based on Tarjan's algorithm.
5. During the DFS, maintain `discovery` and `low-link` values for each cell.
6. An articulation point `u` is found if it's the DFS root with more than one child, or if it's a non-root node with a child `v` such that `low[v] >= discovery[u]`.
7. If an articulation point is found at any time during the traversal, we know the answer is 1. We can stop and return 1.
8. If the entire traversal completes without finding any articulation points, it means the island is 2-vertex-connected. Return 2.

# Solutions
### Java

```java
class Solution {
private
  static final int[] DIRS = new int[]{-1, 0, 1, 0, -1};
private
  int[][] grid;
private
  int m;
private
  int n;
public
  int minDays(int[][] grid) {
    this.grid = grid;
    m = grid.length;
    n = grid[0].length;
    if (count() != 1) {
      return 0;
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          grid[i][j] = 0;
          if (count() != 1) {
            return 1;
          }
          grid[i][j] = 1;
        }
      }
    }
    return 2;
  }
private
  int count() {
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          dfs(i, j);
          ++cnt;
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 2) {
          grid[i][j] = 1;
        }
      }
    }
    return cnt;
  }
private
  void dfs(int i, int j) {
    grid[i][j] = 2;
    for (int k = 0; k < 4; ++k) {
      int x = i + DIRS[k], y = j + DIRS[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
        dfs(x, y);
      }
    }
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} grid * @return {number} */ var minDays = function (
  grid,
) {
  const directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];
  const rows = grid.length;
  const cols = grid[0].length;
  function dfs(x, y, visited) {
    visited[x][y] = true;
    for (let [dx, dy] of directions) {
      const nx = x + dx,
        ny = y + dy;
      if (
        nx >= 0 &&
        ny >= 0 &&
        nx < rows &&
        ny < cols &&
        grid[nx][ny] === 1 &&
        !visited[nx][ny]
      ) {
        dfs(nx, ny, visited);
      }
    }
  }
  function countIslands() {
    let visited = Array.from({ length: rows }, () => Array(cols).fill(false));
    let count = 0;
    for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
        if (grid[i][j] === 1 && !visited[i][j]) {
          count++;
          dfs(i, j, visited);
        }
      }
    }
    return count;
  }
  if (countIslands() !== 1) return 0;
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        grid[i][j] = 0;
        if (countIslands() !== 1) return 1;
        grid[i][j] = 1;
      }
    }
  }
  return 2;
};

```

### CPP

```cpp
class Solution {
public:
  const vector<int> dirs = {-1, 0, 1, 0, -1};
  int m, n;
  int minDays(vector<vector<int>> &grid) {
    m = grid.size(), n = grid[0].size();
    if (count(grid) != 1) {
      return 0;
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          grid[i][j] = 0;
          if (count(grid) != 1) {
            return 1;
          }
          grid[i][j] = 1;
        }
      }
    }
    return 2;
  }
  int count(vector<vector<int>> &grid) {
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          dfs(i, j, grid);
          ++cnt;
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 2) {
          grid[i][j] = 1;
        }
      }
    }
    return cnt;
  }
  void dfs(int i, int j, vector<vector<int>> &grid) {
    grid[i][j] = 2;
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
        dfs(x, y, grid);
      }
    }
  }
};

```

### Python

```python
class Solution:
    def minDays(self, grid: List[List[int]]) -> int: if self . count(grid) != 1: return 0 m, n = len(grid), len(grid[0]) for i in range(m): for j in range(n): if grid[i][j] == 1: grid[i][j] = 0 if self . count(grid) != 1: return 1 grid[i][j] = 1 return 2 def count(self, grid): def dfs(i, j): grid[i][j] = 2 for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y] == 1: dfs(x, y) m, n = len(grid), len(grid[0]) cnt = 0 for i in range(m): for j in range(n): if grid[i][j] == 1: dfs(i, j) cnt += 1 for i in range(m): for j in range(n): if grid[i][j] == 2: grid[i][j] = 1 return cnt

```