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.

Examples

Example 1:

$$ \begin{bmatrix} \colorbox{blue} 0 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{blue} 0 \\ \colorbox{blue} 0 & \colorbox{orange} 1 & \colorbox{orange} 1 & \colorbox{blue} 0 \\ \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 \end{bmatrix} \Longrightarrow \begin{bmatrix} \colorbox{blue} 0 & \colorbox{orange} 1 & \colorbox{darkblue} 0 & \colorbox{blue} 0 \\ \colorbox{blue} 0 & \colorbox{darkblue} 0 & \colorbox{orange} 1 & \colorbox{blue} 0 \\ \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 \end{bmatrix} $$

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:

$$ \begin{bmatrix} \colorbox{orange} 1 & \colorbox{orange} 1 \end{bmatrix} \Longrightarrow \begin{bmatrix} \colorbox{navy} 0 & \colorbox{navy} 0 \end{bmatrix} $$

Input:
grid =[[1,1]]
Output:
 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.

Solution

This problem can be approached using graph traversal techniques such as Depth-First Search (DFS) or Breadth-First Search (BFS).

Method 1 - DFS

The key idea behind this problem is that answer is always less than equal to 2.

Why?

Consider the 3x3 grid island filled with the land (all 1s):

1 1 1
1 1 1
1 1 1

Now, lets focus on the center cell, and we chop of 2 edges connected to it, i.e. we sink 2 adjacent islands:

1 1 1
1 X 0
1 0 1

Now, the island is not connected. Read more about it here: https://en.wikipedia.org/wiki/Biconnected_component.

Steps

Here the cases we can handle:

  1. Check if the grid is already disconnected: If the grid has no land or more than one island, it is already disconnected, hence return 0.
  2. Check if removing one land cell will disconnect the grid immediately: Iterate through each land cell, temporarily remove it, and check the connectivity of the grid. If removing any single land cell results in more than one island, return 1.
  3. If not, return 2: If the above conditions are not met, then the minimum number of days required to disconnect the grid will be 2 under all other circumstances.

Video Explanation

Here is the video explaining above algorithm in detail:

Code

Java
public class Solution {
	private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int minDays(int[][] grid) {
        if (!isConnected(grid)) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0; // Temporarily remove the land
                    if (!isConnected(grid)) {
                        return 1;
                    }
                    grid[i][j] = 1; // Restore the land
                }
            }
        }

        return 2;
    }

    private boolean isConnected(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] start = findStart(grid);

        if (start == null) {
            return false; // No land found
        }
		
		boolean[][] visited = new boolean[m][n];
		// try to visit whole island from starting point
        dfs(grid, visited, start[0], start[1]);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
	            // if some cell is unvisited, island is disconnected
                if (grid[i][j] == 1 && !visited[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }

    private int[] findStart(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    private void dfs(int[][] grid, boolean[][] visited, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 ||  c >= grid[0].length || visited[r][c] || grid[r][c] == 0) {
            return;
        }

        visited[r][c] = true;

        for (int i = 0; i < 4; i++) {
	        int newR = r + DIRS[i][0];
	        int newC = c + DIRS[i][1];
            dfs(grid, visited, newR, newC);
        }
    }
}
Python
def minDays(grid):
    def is_connected(grid):
        rows, cols = len(grid), len(grid[0])
        visited = [[False] * cols for _ in range(rows)]

        def dfs(x, y):
            if (
                x < 0
                or x >= rows
                or y < 0
                or y >= cols
                or visited[x][y]
                or grid[x][y] == 0
            ):
                return
            visited[x][y] = True
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                dfs(x + dx, y + dy)

        # Find the first land cell and start DFS from there
        start = None
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    start = (i, j)
                    break
            if start:
                break

        if not start:
            return False  # No land found

        dfs(start[0], start[1])

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1 and not visited[i][j]:
                    return False  # Found unvisited land meaning disconnected
        return True

    # Initial check if already disconnected
    if not is_connected(grid):
        return 0

    # Try to disconnect by removing one land cell
    rows, cols = len(grid), len(grid[0])
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:
                grid[i][j] = 0
                if not is_connected(grid):
                    return 1
                grid[i][j] = 1  # Restore the land cell

    # If can't be disconnected by removing one cell, return 2
    return 2

Complexity

  • ⏰ Time complexity: O(m*n) ^ 2
    • isConnected takes O(m*n) time, it also calls DFS to determine connectivity.
    • Trying to sink 1 cell at a time, takes O(m*n) time, and for that we are calling isConnected function each time, so it takes O(m*n)^2 time
  • 🧺 Space complexity: O(m*n), for using auxiliary visited set.