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 Search Breadth-First Search

Data structures

Array Matrix

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

Implement a helper function countIslands(grid) using a standard graph traversal algorithm like Depth First Search (DFS) or Breadth First Search (BFS).
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.
If there is exactly one island, iterate through every land cell (r, c) in the grid.
For each land cell, temporarily change its value from 1 (land) to 0 (water).
After this change, call countIslands() again on the modified grid.
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.
Important: After checking, revert the cell's value back to 1 to restore the grid for the next iteration.
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.

1class Solution {2    private int m, n;3    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};4 5    public int minDays(int[][] grid) {6        m = grid.length;7        n = grid[0].length;8 9        if (countIslands(grid) != 1) {10            return 0;11        }12 13        for (int i = 0; i < m; i++) {14            for (int j = 0; j < n; j++) {15                if (grid[i][j] == 1) {16                    grid[i][j] = 0;17                    if (countIslands(grid) != 1) {18                        return 1;19                    }20                    grid[i][j] = 1; // backtrack21                }22            }23        }24 25        return 2;26    }27 28    private int countIslands(int[][] grid) {29        boolean[][] visited = new boolean[m][n];30        int count = 0;31        for (int i = 0; i < m; i++) {32            for (int j = 0; j < n; j++) {33                if (grid[i][j] == 1 && !visited[i][j]) {34                    dfs(grid, i, j, visited);35                    count++;36                }37            }38        }39        return count;40    }41 42    private void dfs(int[][] grid, int r, int c, boolean[][] visited) {43        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {44            return;45        }46        visited[r][c] = true;47        for (int[] dir : dirs) {48            dfs(grid, r + dir[0], c + dir[1], visited);49        }50    }51}

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.

This approach significantly optimizes the check for the 1-day scenario. After handling the 0-day case (by checking if the initial island count is not 1), it uses a more sophisticated graph algorithm to find 'articulation points' or 'cut vertices'. An articulation point is a land cell whose removal would split the single island into two or more smaller islands. Instead of removing each cell and recounting, this method finds all such critical cells in a single pass (a single DFS traversal).

If the algorithm finds even one articulation point, it means the island can be disconnected in 1 day. If the traversal completes and no such points are found, it proves that no single cell removal can disconnect the island, so the answer must be 2.

Algorithm

Implement a helper function to count the number of islands and the total number of land cells simultaneously.
Call this helper function. If the island count is not 1, return 0.
If the total land cell count is 1 or 2, return the land cell count. (A 1-cell island takes 1 day; a 2-cell island takes 2 days).
If there's one island with more than two cells, check for articulation points using a single DFS traversal based on Tarjan's algorithm.
During the DFS, maintain discovery and low-link values for each cell.
An articulation point u is found if it's the DFS root with more than one child, or if it's a non-root node with a child v such that low[v] >= discovery[u].
If an articulation point is found at any time during the traversal, we know the answer is 1. We can stop and return 1.
If the entire traversal completes without finding any articulation points, it means the island is 2-vertex-connected. Return 2.

Walkthrough

The logic is refined to handle all cases efficiently.

Step 1: Initial Analysis. First, count the number of islands and the total number of land cells. A single DFS/BFS pass can achieve this. If the island count is not 1 (i.e., 0 or >1), the grid is already disconnected, so return 0.
Step 2: Handle Small Islands. If there is exactly one island, but it's very small, the answer is trivial. If there's only one land cell, it takes 1 day to remove it. If there are two land cells, it takes 2 days. So if land_count <= 2, return land_count.
Step 3: Articulation Point Search (1 day). For a single island with more than two cells, we check for articulation points. This is done using a single DFS traversal. For each cell u, we maintain two values:
- disc[u]: The discovery time of u (when u is first visited).
- low[u]: The lowest discovery time reachable from u (including itself) through its DFS subtree, possibly using one back-edge to an ancestor.
An articulation point u is detected if either of these conditions is met:
- u is the root of the DFS tree and has more than one child.
- u is not the root, and it has a child v such that low[v] >= disc[u].
If we find an articulation point, we can immediately return 1.
Step 4: Default Case (2 days). If the DFS completes and no articulation points are found, the island is 2-vertex-connected. This means no single cell removal can disconnect it. Thus, the answer is 2.

1class Solution {2    private int m, n;3    private int[][] grid;4    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};5    private int[] disc, low;6    private int time;7    private boolean isArticulationPoint;8 9    public int minDays(int[][] grid) {10        this.grid = grid;11        m = grid.length;12        n = grid[0].length;13 14        if (countIslands() != 1) {15            return 0;16        }17 18        disc = new int[m * n];19        low = new int[m * n];20        java.util.Arrays.fill(disc, -1);21        time = 0;22        isArticulationPoint = false;23 24        // Find first land cell to start DFS25        for (int i = 0; i < m; i++) {26            boolean found = false;27            for (int j = 0; j < n; j++) {28                if (grid[i][j] == 1) {29                    findArticulation(i, j, -1, -1);30                    found = true;31                    break;32                }33            }34            if (found) break;35        }36 37        return isArticulationPoint ? 1 : 2;38    }39 40    private void findArticulation(int r, int c, int pr, int pc) {41        int u = r * n + c;42        disc[u] = low[u] = time++;43        int children = 0;44 45        for (int[] dir : dirs) {46            int nr = r + dir[0];47            int nc = c + dir[1];48 49            if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] == 0) {50                continue;51            }52            53            if (nr == pr && nc == pc) {54                continue;55            }56 57            int v = nr * n + nc;58            if (disc[v] != -1) { // Visited node (back-edge)59                low[u] = Math.min(low[u], disc[v]);60            } else { // Not visited (tree-edge)61                children++;62                findArticulation(nr, nc, r, c);63                low[u] = Math.min(low[u], low[v]);64 65                if (pr == -1 && children > 1) {66                    isArticulationPoint = true;67                }68                if (pr != -1 && low[v] >= disc[u]) {69                    isArticulationPoint = true;70                }71            }72        }73    }74 75    private int countIslands() {76        boolean[][] visited = new boolean[m][n];77        int count = 0;78        for (int i = 0; i < m; i++) {79            for (int j = 0; j < n; j++) {80                if (grid[i][j] == 1 && !visited[i][j]) {81                    dfsCount(i, j, visited);82                    count++;83                }84            }85        }86        return count;87    }88 89    private void dfsCount(int r, int c, boolean[][] visited) {90        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0) {91            return;92        }93        visited[r][c] = true;94        for (int[] dir : dirs) {95            dfsCount(r + dir[0], c + dir[1], visited);96        }97    }98}

Complexity

Time

O(M * N). The initial island counting takes O(M*N). The articulation point finding algorithm is a single DFS traversal over the graph of land cells, which also takes O(V+E) = O(M*N) time. The total complexity is therefore linear in the size of the grid.

Space

O(M * N). This space is required for the `visited`, `disc`, and `low` arrays, as well as the recursion stack for DFS.

Trade-offs

Pros

Highly efficient with a linear time complexity of O(M*N).
Avoids redundant computations by checking for all possible 1-day disconnections in a single pass.

Cons

The implementation is significantly more complex than the brute-force approach.
Requires understanding of advanced graph algorithms (Tarjan's algorithm for articulation points).

Solutions

Solution

1class Solution {2private3  static final int[] DIRS = new int[]{-1, 0, 1, 0, -1};4private5  int[][] grid;6private7  int m;8private9  int n;10public11  int minDays(int[][] grid) {12    this.grid = grid;13    m = grid.length;14    n = grid[0].length;15    if (count() != 1) {16      return 0;17    }18    for (int i = 0; i < m; ++i) {19      for (int j = 0; j < n; ++j) {20        if (grid[i][j] == 1) {21          grid[i][j] = 0;22          if (count() != 1) {23            return 1;24          }25          grid[i][j] = 1;26        }27      }28    }29    return 2;30  }31private32  int count() {33    int cnt = 0;34    for (int i = 0; i < m; ++i) {35      for (int j = 0; j < n; ++j) {36        if (grid[i][j] == 1) {37          dfs(i, j);38          ++cnt;39        }40      }41    }42    for (int i = 0; i < m; ++i) {43      for (int j = 0; j < n; ++j) {44        if (grid[i][j] == 2) {45          grid[i][j] = 1;46        }47      }48    }49    return cnt;50  }51private52  void dfs(int i, int j) {53    grid[i][j] = 2;54    for (int k = 0; k < 4; ++k) {55      int x = i + DIRS[k], y = j + DIRS[k + 1];56      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {57        dfs(x, y);58      }59    }60  }61}

1/** * @param {number[][]} grid * @return {number} */ var minDays = function (2  grid,3) {4  const directions = [5    [0, 1],6    [1, 0],7    [0, -1],8    [-1, 0],9  ];10  const rows = grid.length;11  const cols = grid[0].length;12  function dfs(x, y, visited) {13    visited[x][y] = true;14    for (let [dx, dy] of directions) {15      const nx = x + dx,16        ny = y + dy;17      if (18        nx >= 0 &&19        ny >= 0 &&20        nx < rows &&21        ny < cols &&22        grid[nx][ny] === 1 &&23        !visited[nx][ny]24      ) {25        dfs(nx, ny, visited);26      }27    }28  }29  function countIslands() {30    let visited = Array.from({ length: rows }, () => Array(cols).fill(false));31    let count = 0;32    for (let i = 0; i < rows; i++) {33      for (let j = 0; j < cols; j++) {34        if (grid[i][j] === 1 && !visited[i][j]) {35          count++;36          dfs(i, j, visited);37        }38      }39    }40    return count;41  }42  if (countIslands() !== 1) return 0;43  for (let i = 0; i < rows; i++) {44    for (let j = 0; j < cols; j++) {45      if (grid[i][j] === 1) {46        grid[i][j] = 0;47        if (countIslands() !== 1) return 1;48        grid[i][j] = 1;49      }50    }51  }52  return 2;53};

1class Solution {2public:3  const vector<int> dirs = {-1, 0, 1, 0, -1};4  int m, n;5  int minDays(vector<vector<int>> &grid) {6    m = grid.size(), n = grid[0].size();7    if (count(grid) != 1) {8      return 0;9    }10    for (int i = 0; i < m; ++i) {11      for (int j = 0; j < n; ++j) {12        if (grid[i][j] == 1) {13          grid[i][j] = 0;14          if (count(grid) != 1) {15            return 1;16          }17          grid[i][j] = 1;18        }19      }20    }21    return 2;22  }23  int count(vector<vector<int>> &grid) {24    int cnt = 0;25    for (int i = 0; i < m; ++i) {26      for (int j = 0; j < n; ++j) {27        if (grid[i][j] == 1) {28          dfs(i, j, grid);29          ++cnt;30        }31      }32    }33    for (int i = 0; i < m; ++i) {34      for (int j = 0; j < n; ++j) {35        if (grid[i][j] == 2) {36          grid[i][j] = 1;37        }38      }39    }40    return cnt;41  }42  void dfs(int i, int j, vector<vector<int>> &grid) {43    grid[i][j] = 2;44    for (int k = 0; k < 4; ++k) {45      int x = i + dirs[k], y = j + dirs[k + 1];46      if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {47        dfs(x, y, grid);48      }49    }50  }51};

1class Solution:2    def minDays(self, grid: List[List[int]]) -> int: if self . count(grid) != 1: return 0 m, n = len(grid), len(grid[0]) for i in range(m): for j in range(n): if grid[i][j] == 1: grid[i][j] = 0 if self . count(grid) != 1: return 1 grid[i][j] = 1 return 2 def count(self, grid): def dfs(i, j): grid[i][j] = 2 for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y] == 1: dfs(x, y) m, n = len(grid), len(grid[0]) cnt = 0 for i in range(m): for j in range(n): if grid[i][j] == 1: dfs(i, j) cnt += 1 for i in range(m): for j in range(n): if grid[i][j] == 2: grid[i][j] = 1 return cnt

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 problem