#3619

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Count Islands With Total Value Divisible by K

Count the number of islands in a grid where the sum of each island's values is divisible by a given integer k.

array depth first search breadth first search union find matrix

Problem Statement

You are given an m x n grid filled with non-negative integers and an integer k. An island is a group of adjacent cells containing positive values that are connected either horizontally or vertically. Each island has a total value which is the sum of all its land cell values. Your task is to count how many islands have a total value divisible by k.

Use DFS or BFS to explore the grid and find all connected components (islands). For each island, calculate its total value and check if it's divisible by k. Return the number of such islands where the total value satisfies this condition.

Examples

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

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

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

Solution Approach

DFS/BFS to Find Islands

To solve the problem, start by iterating through the grid. For each unvisited land cell, use a DFS or BFS approach to explore the connected land cells and identify an island. Mark the cells as visited during the traversal.

Calculate Total Value of Each Island

During the DFS or BFS traversal, keep track of the sum of all land values within an island. After identifying an island, check if the total value is divisible by k.

Count Valid Islands

For every island found, if its total value is divisible by k, increment a counter. Finally, return the counter value as the result.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depend on the size of the grid and the approach used. In the worst case, the algorithm will traverse every cell once. Hence, the time complexity is O(m * n) where m is the number of rows and n is the number of columns. Space complexity will depend on the recursive depth for DFS or the queue size for BFS, both of which could also be O(m * n).

What Interviewers Usually Probe

Candidate understands how to identify islands using DFS/BFS.
Candidate calculates the total value of islands correctly.
Candidate can handle large grid sizes efficiently with proper space-time complexity analysis.

Common Pitfalls or Variants

Common pitfalls

Forgetting to mark cells as visited, causing redundant calculations.
Not correctly handling islands that touch the grid boundaries.
Incorrectly summing the values of an island, leading to wrong divisibility checks.

Follow-up variants

Using Union-Find to track connected components instead of DFS/BFS.
Using different grid traversal techniques like spiral or wave traversal.
Handling negative or zero values in the grid while adjusting divisibility checks.

FAQ

What is the primary algorithm used to solve the Count Islands With Total Value Divisible by K problem?

The problem is primarily solved using Depth-First Search (DFS) or Breadth-First Search (BFS) to find connected components (islands) in the grid.

How do I check if an island's total value is divisible by k?

Once an island is identified, sum the values of all its cells and check if the sum modulo k equals zero.

Can I solve the Count Islands With Total Value Divisible by K problem using a different approach?

Yes, you can use the Union-Find algorithm instead of DFS/BFS for finding connected components in the grid.

What is the time complexity for solving the Count Islands With Total Value Divisible by K problem?

The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the grid.

What common mistake should I avoid when solving this problem?

A common mistake is forgetting to mark cells as visited during DFS/BFS, which could result in counting the same island multiple times.

terminal

Solution

Solution 1: DFS

We define a function $\textit{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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        def dfs(i: int, j: int) -> int:
            s = grid[i][j]
            grid[i][j] = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    s += dfs(x, y)
            return s

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] and dfs(i, j) % k == 0:
                    ans += 1
        return ans

Continue Practicing

#2658 maximum number of fish in a grid #3607 power grid maintenance #3493 properties graph