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.
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 grid contains four islands. The islands highlighted in blue have a total value that is divisible by 5, while the islands highlighted in red do not.
Example 2:
Input: grid = [[3,0,3,0], [0,3,0,3], [3,0,3,0]], k = 3
Output: 6
Explanation:
The grid contains six islands, each with a total value that is divisible by 3.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 1050 <= grid[i][j] <= 1061 <= k <= 106Problem Overview: You are given a matrix where each cell contains a value. Adjacent land cells form an island. For every island, compute the total sum of its cell values and count how many islands have a sum divisible by k.
Approach 1: Depth-First Search (DFS) Component Sum (O(m*n) time, O(m*n) space)
Treat the grid as a graph where each cell connects to its four neighbors. Iterate through the matrix and start a Depth-First Search whenever you find an unvisited land cell. During the DFS traversal, accumulate the values of all cells belonging to the same island and mark them as visited to avoid reprocessing. After finishing the traversal for that island, check sum % k == 0; if true, increment the answer. Every cell is visited once, giving O(m*n) time and O(m*n) space for the visited structure and recursion stack.
Approach 2: Breadth-First Search (BFS) Flood Fill (O(m*n) time, O(m*n) space)
This approach replaces recursion with a queue-based traversal. Start a Breadth-First Search from each unvisited land cell and push neighbors into a queue while accumulating the island’s total value. BFS processes nodes level by level but ultimately visits the same connected component as DFS. The advantage is avoiding recursion depth limits in large grids. Time complexity remains O(m*n) because each cell enters the queue once, and space complexity is also O(m*n) in the worst case.
Approach 3: Union-Find Component Aggregation (O(m*n α(n)) time, O(m*n) space)
Another option uses Union Find to group connected land cells into components. Iterate through the matrix and union adjacent land cells. Maintain an array or map that tracks the cumulative value for each component root. After processing all unions, iterate through the roots and count how many component sums are divisible by k. Path compression keeps operations close to constant time, resulting in roughly O(m*n α(n)).
Recommended for interviews: DFS or BFS is what interviewers expect. The grid is naturally modeled as a graph, and a flood-fill traversal directly computes the island sum in one pass. Explaining the brute-force idea of scanning components shows understanding, but implementing the DFS/BFS solution demonstrates solid graph traversal skills and clean complexity of O(m*n).
We define a function dfs(i, j), which performs DFS traversal starting from position (i, j) and returns the total value of that island. We add the current position's value to the total value, then mark that position as visited (for example, by setting its value to 0). Next, we recursively visit the adjacent positions in four directions (up, down, left, right). If an adjacent position has a value greater than 0, we continue the DFS and add its value to the total value. Finally, we return the total value.
In the main function, we traverse the entire grid. For each unvisited position (i, j), if its value is greater than 0, we call dfs(i, j) to calculate the total value of that island. If the total value is divisible by k, we increment the answer by one.
The time complexity is O(m times n), and the space complexity is O(m times n), where m and n are the number of rows and columns of the grid, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Component Sum | O(m*n) | O(m*n) | General case for grid island problems; simple to implement |
| BFS Flood Fill | O(m*n) | O(m*n) | When recursion depth may be large or iterative traversal is preferred |
| Union-Find Components | O(m*n α(n)) | O(m*n) | Useful when multiple connectivity queries or dynamic merges are required |
Count Islands With Total Value Divisible by K | DFS | Biweekly Contest 161 | Q2 | Leetcode 3619 • ExpertFunda • 196 views views
Watch 6 more video solutions →Practice Count Islands With Total Value Divisible by K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor