> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/graphs-bfs-and-dfs/minimum-number-of-days-to-disconnect-island.md).

# Minimum Number of Days to Disconnect Island

Given a 2D `grid` consisting of `1`s (land) and `0`s (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.leetcode.com/uploads/2020/08/13/1926_island.png)

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

**Example 3:**

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

**Example 4:**

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

**Example 5:**

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

**Constraints:**

* `1 <= grid.length, grid[i].length <= 30`
* `grid[i][j]` is `0` or `1`.

```java
class Solution {
    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int[][] dis, low;
    int time, size;

    public int minDays(int[][] grid) {
        // Count number of islands
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int count = 0;
        int x = -1, y = -1;
        size = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count++;
                    dfs(grid, visited, i, j);
                    // x & y are just used to store one pint of the island
                    // for articulation point
                    x = i;
                    y = j;
                }
            }
        }

        if (count == 0 || count > 1)
            return 0;
        if (size <= 2)
            return size;
        // Check for articulation point
        time = 0;
        dis = new int[grid.length][grid[0].length];
        low = new int[grid.length][grid[0].length];
        visited = new boolean[grid.length][grid[0].length];
        boolean isPresent = findAP(grid, visited, x, y, -1, -1);
        if (isPresent)
            return 1;
        // Else : Only 2 parts need to be removed to convert into multi islands
        return 2;
    }

    public boolean findAP(int[][] grid, boolean[][] visited, int x, int y, int px, int py) {
        time++;
        visited[x][y] = true;
        low[x][y] = time;
        dis[x][y] = time;
        int dfsCalls = 0;
        boolean AP = false;
        for (int[] dir : dirs) {
            int i = x + dir[0], j = y + dir[1];
            if (i == px && j == py)
                continue;
            if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1) {
                if (visited[i][j])
                    low[x][y] = Math.min(low[x][y], dis[i][j]);
                else {
                    AP = AP || findAP(grid, visited, i, j, x, y);
                    low[x][y] = Math.min(low[x][y], low[i][j]);
                    dfsCalls++;
                    // Additional conditions for starting node
                    if (dis[x][y] <= low[i][j] && px != -1 && py != -1)
                        AP = true;
                }
            }
        }
        // If it is the starting node
        if (px == -1 && py == -1 && dfsCalls > 1)
            AP = true;
        return AP;
    }

    public void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        size++;
        visited[x][y] = true;
        for (int[] dir : dirs) {
            int i = x + dir[0], j = y + dir[1];
            if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && !visited[i][j] && grid[i][j] == 1) {
                dfs(grid, visited, i, j);
            }
        }
    }
}
```