Count Islands With Total Value Divisible by K

Medium
1734.

Count Islands With Total Value Divisible by K

Count Islands With Total Value Divisible by K is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon interviews.

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.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 10^5
  • 0 <= grid[i][j] <= 10^6
  • 1 <= k <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var countIslands = function(grid, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 10^5
  • 0 <= grid[i][j] <= 10^6
  • 1 <= k <= 10^6

Hints for Count Islands With Total Value Divisible by K

  1. Hint 1

    This is the classic island count with one extra number per island: its total value.

  2. Hint 2

    Flood-fill each unvisited positive cell (BFS or an explicit stack), adding up the values as you go.

  3. Hint 3

    An island can total about 10^11, so either keep the sum in 64 bits or keep it modulo k while 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

  1. Scan the grid; at each positive cell not yet visited, start a flood fill.
  2. Pop cells from a stack, add their value (modulo k) and push their unvisited positive neighbours.
  3. When the stack is empty the island is complete: count it if the accumulated value is 0 modulo k.

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 count

Java

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)