Scale Engineer

Minimum Number of Days to Disconnect Island

Hard
#1443Time: O((M*N)^2). The `countIslands` function takes O(M*N) time. In the worst-case scenario for the 1-day check, we iterate through all M*N cells, and for each land cell, we call `countIslands`. This results in a total time complexity of O(M*N * M*N).Space: O(M * N), where M and N are the dimensions of the grid. This space is used for the `visited` array in the `countIslands` function and for the recursion stack of the DFS, which in the worst case can be of size M*N.
Algorithms
Depth-First SearchBreadth-First Search
Data structures
ArrayMatrix

Prompt

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.

 

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: grid = [[1,1]]
Output: 2
Explanation: Grid of full water is also disconnected ([[1,1]] -> [[0,0]]), 0 islands.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 30
  • grid[i][j] is either 0 or 1.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It first checks the initial state of the grid. If the grid is already disconnected (meaning it has 0 or more than 1 island), the answer is 0 days. If the grid consists of a single island, the approach then tries to disconnect it by removing one land cell at a time. It iterates through every land cell, temporarily flipping it to water, and then recounts the number of islands. If the island count changes from one, it means we've successfully disconnected the grid in one day, and the answer is 1. If after trying to remove every single land cell, the island remains connected, we can conclude that the answer must be 2. This is because it's always possible to disconnect any island by removing at most two cells.

Algorithm

  1. Implement a helper function countIslands(grid) using a standard graph traversal algorithm like Depth First Search (DFS) or Breadth First Search (BFS).
  2. Call countIslands() on the initial grid. If the number of islands is not equal to 1, the grid is already disconnected, so the answer is 0.
  3. If there is exactly one island, iterate through every land cell (r, c) in the grid.
  4. For each land cell, temporarily change its value from 1 (land) to 0 (water).
  5. After this change, call countIslands() again on the modified grid.
  6. If the new count of islands is not 1 (i.e., it's 0 or greater than 1), it means removing this single cell was enough to disconnect the island. Return 1.
  7. Important: After checking, revert the cell's value back to 1 to restore the grid for the next iteration.
  8. If the loop completes without finding any single cell removal that disconnects the island, it implies that at least two removals are necessary. Since it's always possible to disconnect an island with two removals, return 2.

Walkthrough

The core of this method is a helper function, countIslands(grid), which traverses the grid using DFS or BFS to count the number of separate islands.

  • Step 1: Initial Check (0 days). Call countIslands() on the original grid. If the result is not 1, the grid is already disconnected. Return 0.

  • Step 2: Single Removal Check (1 day). If there is exactly one island, iterate through every cell (r, c) of the grid.

    • If grid[r][c] is a land cell (value 1):
      • Temporarily change grid[r][c] to 0 (water).
      • Call countIslands() on the modified grid.
      • If the new island count is not 1 (i.e., 0 or >1), it means removing this single cell disconnects the island. We have found the solution. Return 1.
      • Important: Change grid[r][c] back to 1 to restore the grid for the next iteration.

  • Step 3: Default Case (2 days). If the loop completes without finding any single cell that disconnects the island, it implies that at least two removals are necessary. The problem guarantees that 2 removals are always sufficient. Therefore, return 2.

class Solution {    private int m, n;    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};     public int minDays(int[][] grid) {        m = grid.length;        n = grid[0].length;         if (countIslands(grid) != 1) {            return 0;        }         for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 1) {                    grid[i][j] = 0;                    if (countIslands(grid) != 1) {                        return 1;                    }                    grid[i][j] = 1; // backtrack                }            }        }         return 2;    }     private int countIslands(int[][] grid) {        boolean[][] visited = new boolean[m][n];        int count = 0;        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 1 && !visited[i][j]) {                    dfs(grid, i, j, visited);                    count++;                }            }        }        return count;    }     private void dfs(int[][] grid, int r, int c, boolean[][] visited) {        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {            return;        }        visited[r][c] = true;        for (int[] dir : dirs) {            dfs(grid, r + dir[0], c + dir[1], visited);        }    }}

Complexity

Time

O((M*N)^2). The `countIslands` function takes O(M*N) time. In the worst-case scenario for the 1-day check, we iterate through all M*N cells, and for each land cell, we call `countIslands`. This results in a total time complexity of O(M*N * M*N).

Space

O(M * N), where M and N are the dimensions of the grid. This space is used for the `visited` array in the `countIslands` function and for the recursion stack of the DFS, which in the worst case can be of size M*N.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly models the problem statement without requiring complex algorithms.

Cons

  • The time complexity is high, O((M*N)^2), which might be too slow for larger grids, although it passes for the given constraints.

  • It performs a lot of redundant work by re-calculating the number of islands from scratch in each iteration.

Solutions

class Solution {private  static final int[] DIRS = new int[]{-1, 0, 1, 0, -1};private  int[][] grid;private  int m;private  int n;public  int minDays(int[][] grid) {    this.grid = grid;    m = grid.length;    n = grid[0].length;    if (count() != 1) {      return 0;    }    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 1) {          grid[i][j] = 0;          if (count() != 1) {            return 1;          }          grid[i][j] = 1;        }      }    }    return 2;  }private  int count() {    int cnt = 0;    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 1) {          dfs(i, j);          ++cnt;        }      }    }    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 2) {          grid[i][j] = 1;        }      }    }    return cnt;  }private  void dfs(int i, int j) {    grid[i][j] = 2;    for (int k = 0; k < 4; ++k) {      int x = i + DIRS[k], y = j + DIRS[k + 1];      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {        dfs(x, y);      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem