Skip to main content
Talentd

Count Islands With Total Value Divisible by K - Solution & Explanation

MediumArrayDepth-First SearchBreadth-First SearchUnion Find10 min readAsked at: Intuit, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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).

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Component SumO(m*n)O(m*n)General case for grid island problems; simple to implement
BFS Flood FillO(m*n)O(m*n)When recursion depth may be large or iterative traversal is preferred
Union-Find ComponentsO(m*n α(n))O(m*n)Useful when multiple connectivity queries or dynamic merges are required

Video Solution

Count Islands With Total Value Divisible by K | DFS | Biweekly Contest 161 | Q2 | Leetcode 3619 • ExpertFunda • 198 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Count Islands With Total Value Divisible by K easy or hard?
The problem is typically rated Medium. The main challenge is recognizing that it is a standard island traversal problem combined with summing component values and applying a divisibility check.
Count Islands With Total Value Divisible by K Python/Java solution
Implement a DFS that explores four directions from each land cell and accumulates the island's value. After the DFS completes, check if the sum modulo k equals zero. The same logic works across Python, Java, C++, Go, and TypeScript with O(m*n) time complexity.
How to solve Count Islands With Total Value Divisible by K in O(n)?
Treat the grid as a graph and run DFS or BFS from every unvisited land cell. While traversing an island, accumulate the total value of its cells. After finishing the component, check if the sum modulo k equals zero and increment the island count if true. Each cell is visited once, giving O(m*n) total work.
What is the best approach for Count Islands With Total Value Divisible by K?
Depth-First Search (DFS) flood fill is the most practical approach. Traverse each unvisited land cell, sum all values in the connected component, and check if the total is divisible by k. The algorithm visits every cell once, giving O(m*n) time and O(m*n) space.
Is Count Islands With Total Value Divisible by K asked at Google/Amazon/Meta?
Island-style grid traversal problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants such as Number of Islands, Max Area of Island, and island sum calculations are common. This problem combines the same traversal pattern with modular arithmetic.
What data structure is used in Count Islands With Total Value Divisible by K?
The solution models the grid as a graph and uses DFS or BFS for traversal. A visited matrix or in-place marking prevents revisiting cells, and recursion or a queue manages the traversal order. Union-Find can also be used to group cells into connected components.
What is the time complexity of Count Islands With Total Value Divisible by K?
The optimal DFS or BFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is processed once during the traversal. Space complexity is O(m*n) due to the visited grid or recursion/queue storage.

Ready to solve this problem?

Practice Count Islands With Total Value Divisible by K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Islands