3619. Count Islands With Total Value Divisible by K

2026, Oct 25 2 mins read

1. Description

Given an m x n matrix grid and a positive integer k, treat cells with positive values as land and cells containing 0 as water.
An island is a maximal group of land cells connected horizontally or vertically. Its total value is obtained by adding the values of every cell in the group.
Count the islands whose total value is divisible by k.

2. Example

Example 1

Input: grid = [[0,2,1,0,0],[0,5,0,0,5],[0,0,1,0,0],[0,1,4,7,0],[0,2,0,0,8]], k = 5
Output: 2
Explanation: The four islands have total values 8, 5, 15, and 8. Only 5 and 15 are divisible by 5.

Example 2

Input: grid = [[3,0,3,0],[0,3,0,3],[3,0,3,0]], k = 3
Output: 6
Explanation: Each positive cell forms its own island. All six islands have total value 3, so all are counted.

3. Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10$^5$
0 <= grid[i][j] <= 10$^6$
1 <= k <= 10$^6$

4. Solutions

Breadth-First Search

m = grid.size(), n = grid.front().size()
Time complexity: O(mn)
Space complexity: O(mn)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int countIslands(vector<vector<int>> &grid, int k) {
        const int m = grid.size(), n = grid.front().size();
        const array<pair<int, int>, 4> directions{{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}};

        vector<pair<int, int>> nodes;
        int count = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 0) {
                    continue;
                }

                nodes.clear();
                nodes.emplace_back(i, j);

                uint64_t sum = grid[i][j];
                grid[i][j] = 0;

                for (size_t head = 0; head < nodes.size(); ++head) {
                    auto [r, c] = nodes[head];

                    for (auto [dr, dc] : directions) {
                        int nr = r + dr, nc = c + dc;

                        if (0 <= nr && nr < m && 0 <= nc && nc < n && grid[nr][nc] > 0) {
                            sum += grid[nr][nc];
                            grid[nr][nc] = 0;
                            nodes.emplace_back(nr, nc);
                        }
                    }
                }

                count += sum % k == 0;
            }
        }

        return count;
    }
};