LeetCode 3619 - Count Islands With Total Value Divisible by K

The problem is asking us to count islands in a 2D grid where the sum of the values in each island is divisible by a given integer k.

leetcodemediumarraydepth-first-searchbreadth-first-searchunion-findmatrix

LeetCode Problem 3619

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

The problem is asking us to count islands in a 2D grid where the sum of the values in each island is divisible by a given integer k. An island is defined as a group of positive integers that are 4-directionally connected, meaning we can move horizontally or vertically between adjacent positive integers. The grid may contain zeros, which represent water, and these zeros act as boundaries for islands.

The input consists of a 2D matrix grid of size m x n where 1 <= m, n <= 1000 and the values in the cells are between 0 and 10^6. The integer k is a positive number up to 10^6. The output is a single integer representing the number of islands whose total sum of values is divisible by k.

The constraints indicate that we cannot afford an overly naive solution that repeatedly checks each cell inefficiently, because the total number of cells can be up to 10^5. Important edge cases include grids with all zeros, grids with one large island, grids where each positive number is isolated, and grids where the sum of a large island might exceed standard integer ranges (especially in languages with fixed integer sizes like Go).

Approaches

A brute-force approach would iterate over each cell in the grid, and whenever a positive number is found that has not been visited, start a depth-first search (DFS) or breadth-first search (BFS) to find all connected positive cells, calculate the sum of the island, and then check if it is divisible by k. While this approach is correct, it requires marking visited cells and computing sums repeatedly, which is feasible but could be slow if implemented naively for the largest grids.

The key insight to optimize is to perform a single traversal of each island using DFS or BFS while maintaining a running sum. This ensures we only visit each cell once and compute the total sum efficiently. Using a visited matrix or marking cells in-place allows us to avoid revisiting cells, making the algorithm linear in the number of cells.

Approach Time Complexity Space Complexity Notes
Brute Force O(m_n_(average island size)) O(m*n) DFS/BFS from each unvisited cell, recomputing sums repeatedly
Optimal O(m*n) O(m*n) DFS/BFS, visiting each cell once, maintaining a running sum

Algorithm Walkthrough

  1. Initialize a counter count to track the number of islands divisible by k. Create a visited matrix of size m x n initialized to False to mark cells that have been processed.
  2. Iterate through each cell (i, j) in the grid. If the cell is positive and not visited, it is part of a new island.
  3. Start a DFS (or BFS) from this cell. Initialize a local total sum for the island.
  4. In the DFS, mark the current cell as visited. Add its value to the running total.
  5. Explore the four 4-directionally connected neighbors (up, down, left, right). For each neighbor, if it is within bounds, positive, and not visited, recursively continue the DFS on that neighbor.
  6. Once DFS completes for the starting cell, check if total % k == 0. If true, increment the count.
  7. Continue iterating over the grid until all cells are processed.
  8. Return count.

Why it works: Each cell is visited exactly once, ensuring every island is counted exactly once. The running sum guarantees we correctly calculate the total value of each island, and the modulo check ensures we only count islands divisible by k.

Python Solution

from typing import List

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        if not grid or not grid[0]:
            return 0
        
        m, n = len(grid), len(grid[0])
        visited = [[False]*n for _ in range(m)]
        
        def dfs(x: int, y: int) -> int:
            if x < 0 or x >= m or y < 0 or y >= n or visited[x][y] or grid[x][y] == 0:
                return 0
            visited[x][y] = True
            total = grid[x][y]
            total += dfs(x+1, y)
            total += dfs(x-1, y)
            total += dfs(x, y+1)
            total += dfs(x, y-1)
            return total
        
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] > 0 and not visited[i][j]:
                    island_sum = dfs(i, j)
                    if island_sum % k == 0:
                        count += 1
        return count

Explanation: The dfs function recursively explores all connected positive cells while accumulating the total value of the island. The visited matrix ensures each cell is processed exactly once. After each DFS call, we check if the sum is divisible by k and update the count.

Go Solution

func countIslands(grid [][]int, k int) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }
    m, n := len(grid), len(grid[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }

    var dfs func(x, y int) int
    dfs = func(x, y int) int {
        if x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || grid[x][y] == 0 {
            return 0
        }
        visited[x][y] = true
        total := grid[x][y]
        total += dfs(x+1, y)
        total += dfs(x-1, y)
        total += dfs(x, y+1)
        total += dfs(x, y-1)
        return total
    }

    count := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] > 0 && !visited[i][j] {
                islandSum := dfs(i, j)
                if islandSum%k == 0 {
                    count++
                }
            }
        }
    }
    return count
}

Explanation: The Go solution mirrors the Python version with explicit slice initialization for the visited matrix and function literal for DFS. Go handles integers safely up to the constraints since the sum will not overflow int64 limits.

Worked Examples

Example 1

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

Iteration and DFS results:

Island Cells Sum Divisible by 5?
1 (0,1),(0,2),(1,1),(2,2),(3,1),(3,2),(3,3) 20 Yes
2 (1,4) 5 Yes
3 (4,1) 2 No
4 (4,4) 8 No

Output: 2

Example 2

grid = [
 [3,0,3,0],
 [0,3,0,3],
 [3,0,3,0]
]
k = 3

Each 3 is an isolated island, total 6 islands, all divisible by 3. Output: 6

Complexity Analysis

Measure Complexity Explanation
Time O(m*n) Each cell is visited exactly once in DFS
Space O(m*n) The visited matrix and recursion stack for DFS can both reach O(m*n) in worst-case

The algorithm is linear with respect to the number of cells, which fits comfortably within the constraints of up to 10^5 cells.

Test Cases

solution = Solution()

# Provided examples
assert solution.countIslands([[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]], 5) == 2
assert solution.countIslands([[3,0,3,0],[0,3,0,3],[3,0,3,0]], 3) == 6

# Edge cases
assert solution.countIslands([[0,0],[0,0]], 1) == 0  # All water
assert solution.countIslands([[1]], 1) == 1          # Single cell island divisible by 1
assert solution.countIslands([[2]], 3) == 0          # Single cell island not divisible
assert solution.countIslands([[1,1],[1,1]], 2) == 1  # Entire grid is one island
assert solution.countIslands([[1,0,2],[0,3,0],[4,0,5]], 1) == 5