Watch 7 video solutions for Count Islands With Total Value Divisible by K, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by ExpertFunda has 196 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
| 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 |