# Minimum Number of Days to Disconnect Island

This page explains Java solution to problem `Minimum Number of Days to Disconnect Island` using `Depth First Search` algorithm.

## Problem Statement

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.

Example 1:

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: [[1,1]]
Output: 1

Example 3:

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

Example 4:

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

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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);
}
}
}
}
``````

## Time Complexity

O((N * M)2) Where
N is number of Rows in an input grid
M is number of Columns in an input grid

## Space Complexity

O(N * M) Where
N is number of Rows in an input grid
M is number of Columns in an input grid