Count Islands With Total Value Divisible by K

Count Islands With Total Value Divisible by K

What is this problem about?

This "Medium" difficulty problem is a variation of the classic "Number of Islands" question. You are given a 2D grid of integers and a divisor $k$. An "island" is a group of adjacent (horizontal or vertical) non-zero cells. You need to count the number of islands where the sum of all values within that island is perfectly divisible by $k$.

Why is this asked in interviews?

Companies like Intuit ask this to see if you can extend a standard algorithm with additional state management. It combines Graph Traversal (identifying connected components) with arithmetic properties. It tests your ability to maintain a running sum during a search and ensure that every cell is visited exactly once.

Algorithmic pattern used

This problem uses the Connected Components pattern, implemented via Depth-First Search (DFS), Breadth-First Search (BFS), or Union Find. As you traverse each island, you accumulate the values of its cells. Once the traversal for an island is complete, you check if total_sum % k == 0. Using a "visited" array or modifying the grid in-place prevents counting the same island twice.

Example explanation

Grid:

[ [1, 2, 0],
  [0, 0, 3],
  [4, 0, 0] ]
k = 3

1. Island 1: Cells (0,0) and (0,1). Values: 1, 2. Sum = 3. 3 % 3 == 0. (Good!)
2. Island 2: Cell (1,2). Value: 3. Sum = 3. 3 % 3 == 0. (Good!)
3. Island 3: Cell (2,0). Value: 4. Sum = 4. 4 % 3 != 0. (Bad.) Total Count: 2.

Common mistakes candidates make

A common error is resetting the "visited" state incorrectly, leading to infinite recursion or duplicate counts. Another mistake is failing to handle large grids efficiently, causing a Stack Overflow if using DFS without increasing the limit. Candidates also occasionally forget to check the divisibility condition only after the entire island has been explored.

Interview preparation tip

When modifying a classic problem like "Number of Islands," clearly separate the logic for traversal from the logic for aggregation. This makes your code modular and easier to adapt if the interviewer changes the condition (e.g., "count islands with more than 5 cells").