Count islands with total value divisible by k

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

56.3% acceptance

Feb 25, 2026

You are given an m x n matrix grid and a positive integer k. An island is a group of positive integers (representing land) that are 4-directionally connected (horizontally or vertically). The total value of an island is the sum of the values of all cells in the island. Return the number of islands with a total value divisible by k.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn count_islands(grid: Vec<Vec<i32>>, k: i32) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut visited = vec![vec![false; n]; m];
    let mut result = 0;
    for i in 0..m {
      for j in 0..n {
        if grid[i][j] > 0 && !visited[i][j] {
          let total = Self::bfs(&grid, &mut visited, i, j, m, n);
          if total % k as i64 == 0 { result += 1; }
        }
      }
    }
    result
  }

  fn bfs(grid: &Vec<Vec<i32>>, visited: &mut Vec<Vec<bool>>, si: usize, sj: usize, m: usize, n: usize) -> i64 {
    let mut stack = vec![(si, sj)];
    visited[si][sj] = true;
    let mut total: i64 = 0;
    while let Some((i, j)) = stack.pop() {
      total += grid[i][j] as i64;
      for (di, dj) in [(!0usize, 0usize), (1, 0), (0, !0usize), (0, 1)] {
        let ni = i.wrapping_add(di);
        let nj = j.wrapping_add(dj);
        if ni < m && nj < n && grid[ni][nj] > 0 && !visited[ni][nj] {
          visited[ni][nj] = true;
          stack.push((ni, nj));
        }
      }
    }
    total
  }
}