Count Islands With Total Value Divisible by K — Solution
Count Islands With Total Value Divisible by K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Islands With Total Value Divisible by K is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Breadth-First Search, Union Find
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n matrix grid of non-negative integers and a positive integer k.
An island is a maximal group of cells holding positive values that are connected horizontally or vertically. The total value of an island is the sum of all its cells.
Return the number of islands whose total value is divisible by k.
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 total 8, 5, 15 and 8; only the ones totalling 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: Six single-cell islands of value 3, each divisible by 3.
Example 3
Input: grid = [[0,0],[0,0]], k = 4
Output: 0
Explanation: There is no positive cell, so there are no islands.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 10^50 <= grid[i][j] <= 10^61 <= k <= 10^6
Hints for Count Islands With Total Value Divisible by K
Hint 1
This is the classic island count with one extra number per island: its total value.
Hint 2
Flood-fill each unvisited positive cell (BFS or an explicit stack), adding up the values as you go.
Hint 3
An island can total about
10^11, so either keep the sum in 64 bits or keep it modulokwhile adding.
How to solve Count Islands With Total Value Divisible by K
Visit every island exactly once with a flood fill, accumulating its value, and test divisibility at the end of each fill.
Approach
- Scan the grid; at each positive cell not yet visited, start a flood fill.
- Pop cells from a stack, add their value (modulo
k) and push their unvisited positive neighbours. - When the stack is empty the island is complete: count it if the accumulated value is
0modulok.
Why it works
Each flood fill reaches exactly the cells connected to its start through positive cells, which is one island, and marking cells as visited guarantees no island is counted twice. Adding modulo k keeps the remainder exact.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Zero cells are water, not land of value 0.
- Diagonal neighbours do not connect islands.
- Recursive DFS over a 10^5-cell island can overflow the stack; use an explicit stack.
Reference solution
Python
from typing import List
def countIslands(grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
seen = [[False] * n for _ in range(m)]
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 0 or seen[r][c]:
continue
seen[r][c] = True
stack = [(r, c)]
rem = 0
while stack:
x, y = stack.pop()
rem = (rem + grid[x][y]) % k
for a, b in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= a < m and 0 <= b < n and grid[a][b] > 0 and not seen[a][b]:
seen[a][b] = True
stack.append((a, b))
if rem == 0:
count += 1
return countJava
public static int countIslands(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int[] DR = {1, -1, 0, 0}, DC = {0, 0, 1, -1};
boolean[] seen = new boolean[m * n];
int[] stack = new int[m * n];
int count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0 || seen[r * n + c]) continue;
seen[r * n + c] = true;
int top = 0;
stack[top++] = r * n + c;
long rem = 0;
while (top > 0) {
int cell = stack[--top], x = cell / n, y = cell % n;
rem = (rem + grid[x][y]) % k;
for (int d = 0; d < 4; d++) {
int a = x + DR[d], b = y + DC[d];
if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] > 0 && !seen[a * n + b]) {
seen[a * n + b] = true;
stack[top++] = a * n + b;
}
}
}
if (rem == 0) count++;
}
}
return count;
}C++
int countIslands(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
int DR[4] = {1, -1, 0, 0}, DC[4] = {0, 0, 1, -1};
vector<char> seen(m * n, 0);
vector<int> stack;
int count = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0 || seen[r * n + c]) continue;
seen[r * n + c] = 1;
stack.push_back(r * n + c);
long long rem = 0;
while (!stack.empty()) {
int cell = stack.back();
stack.pop_back();
int x = cell / n, y = cell % n;
rem = (rem + grid[x][y]) % k;
for (int d = 0; d < 4; d++) {
int a = x + DR[d], b = y + DC[d];
if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] > 0 && !seen[a * n + b]) {
seen[a * n + b] = 1;
stack.push_back(a * n + b);
}
}
}
if (rem == 0) count++;
}
}
return count;
}JavaScript
var countIslands = function(grid, k) {
var m = grid.length, n = grid[0].length;
var DR = [1, -1, 0, 0], DC = [0, 0, 1, -1];
var seen = [];
for (var i = 0; i < m * n; i++) seen.push(false);
var count = 0;
for (var r = 0; r < m; r++) {
for (var c = 0; c < n; c++) {
if (grid[r][c] === 0 || seen[r * n + c]) continue;
seen[r * n + c] = true;
var stack = [r * n + c], rem = 0;
while (stack.length > 0) {
var cell = stack.pop(), x = Math.floor(cell / n), y = cell % n;
rem = (rem + grid[x][y]) % k;
for (var d = 0; d < 4; d++) {
var a = x + DR[d], b = y + DC[d];
if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] > 0 && !seen[a * n + b]) {
seen[a * n + b] = true;
stack.push(a * n + b);
}
}
}
if (rem === 0) count++;
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)