This page explains Java solution to problem `Minimum Number of Days to Disconnect Island`

using `Depth First Search`

algorithm.

Given a `2D`

grid consisting of `1s`

(land) and `0s`

(water). An island is a maximal 4-directionally (horizontal or vertical) connected group of `1s`

.

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.

Input: grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]Output: 2Explanation: 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.

Input: [[1,1]]Output: 1

Input: [[1,0,1,0]]Output: 0

Input: [[1,1,0,1,1], [1,1,1,1,1], [1,1,0,1,1],[1,1,1,1,1]]Output: 2

```
package com.vc.hard;
class MinimumNumberOfDaysToDisconnectIsland {
public int minDays(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0) return 0;
if(islandCount(grid) != 1) return 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == 1) {
grid[i][j] = 0;
if(islandCount(grid) != 1) return 1;
grid[i][j] = 1;
}
}
}
/**
At most it will take 2 days to disconnect island,
because you can just disconnect one island on bottom left as below
Let's say we have:
1 1 1
1 1 1
1 1 1
Disconnect bottome left island like so:
1 1 1
0 1 1
1 0 1
*/
return 2;
}
private int islandCount(int[][] grid) {
int count = 0;
boolean[][] visited = new boolean[grid.length][grid[0].length];
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == 1 && !visited[i][j]) {
dfs(grid, visited, i, j);
count++;
}
}
}
return count;
}
private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private void dfs(int[][] grid, boolean[][] visited, int row, int col) {
if(visited[row][col]) return;
visited[row][col] = true;
for(int[] dir: dirs) {
int rowNew = row + dir[0];
int colNew = col + dir[1];
if(rowNew >= 0 && rowNew < grid.length && colNew >= 0 && colNew < grid[0].length &&
grid[rowNew][colNew] == 1) {
dfs(grid, visited, rowNew, colNew);
}
}
}
}
```

O((N * M)

^{2}) Where

N is number of Rows in an input grid

M is number of Columns in an input grid

O(N * M) Where

N is number of Rows in an input grid

M is number of Columns in an input grid