Minimum number of days to disconnect island

Array Depth-First Search Breadth-First Search Matrix Strongly Connected Component

58.8% acceptance

Feb 25, 2026

1299

224

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_days(grid: Vec<Vec<i32>>) -> i32 {
    fn count_islands(g: &Vec<Vec<i32>>) -> i32 {
      let m = g.len();
      let n = g[0].len();
      let mut visited = vec![vec![false; n]; m];
      let mut count = 0;
      for r in 0..m {
        for c in 0..n {
          if g[r][c] == 1 && !visited[r][c] {
            count += 1;
            // BFS
            let mut queue = std::collections::VecDeque::new();
            queue.push_back((r, c));
            visited[r][c] = true;
            while let Some((row, col)) = queue.pop_front() {
              for (dr, dc) in [(-1i32, 0), (1, 0), (0, -1i32), (0, 1)] {
                let nr = row as i32 + dr;
                let nc = col as i32 + dc;
                if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 {
                  let nr = nr as usize;
                  let nc = nc as usize;
                  if g[nr][nc] == 1 && !visited[nr][nc] {
                    visited[nr][nc] = true;
                    queue.push_back((nr, nc));
                  }
                }
              }
            }
          }
        }
      }
      count
    }

    // Already disconnected or no island?
    let islands = count_islands(&grid);
    if islands != 1 {
      return 0;
    }

    // Try removing 1 cell
    let m = grid.len();
    let n = grid[0].len();
    for r in 0..m {
      for c in 0..n {
        if grid[r][c] == 1 {
          let mut g2 = grid.clone();
          g2[r][c] = 0;
          if count_islands(&g2) != 1 {
            return 1;
          }
        }
      }
    }

    // Any connected island can be disconnected in at most 2 moves
    2
  }
}