Number of closed islands

Array Depth-First Search Breadth-First Search Union-Find Matrix

67.0% acceptance

Mar 1, 2026

4758

191

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s. Return the number of closed islands.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn closed_island(mut grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len() as i32;
    let n = grid[0].len() as i32;

    fn dfs(grid: &mut Vec<Vec<i32>>, r: i32, c: i32, m: i32, n: i32) -> bool {
      if r < 0 || r >= m || c < 0 || c >= n || grid[r as usize][c as usize] != 0 {
        return true;
      }
      grid[r as usize][c as usize] = 1;
      // Mark not-closed if on border, but always continue DFS to flood-fill the whole component
      let mut closed = !(r == 0 || r == m - 1 || c == 0 || c == n - 1);
      for (dr, dc) in [(-1i32, 0i32), (1, 0), (0, -1), (0, 1)] {
        if !dfs(grid, r + dr, c + dc, m, n) {
          closed = false;
        }
      }
      closed
    }

    let mut count = 0;
    for i in 0..m {
      for j in 0..n {
        if grid[i as usize][j as usize] == 0 {
          if dfs(&mut grid, i, j, m, n) {
            count += 1;
          }
        }
      }
    }
    count
  }
}