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