3619.Count_Islands_With_Total_Value_Divisible_by_K(Medium).md

3619. Count Islands With Total Value Divisible by K (Medium)

Link: https://leetcode.com/problems/count-islands-with-total-value-divisible-by-k

Date	Stopwatch	Y/N	Feedback
Jul 19, 2025	Y

Edge Cases:

Edge Case 1:

Input: grid = [[0,0,0],[0,0,1],[11,0,6],[0,10,2],[0,0,0],[8,0,0]], k = 19
Output: 1

Walk-through:

Run BFS to find each island with global variable values to keep track of each island's total values, then values % k to check if we should increment ans += 1.

Python:

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        # Run BFS over grid, for each island, calculate if total values % k == 0, if so, ans += 1
        # TC: O(m*n), SC: O(m*n)

        visited = set()
        ans = 0
        values = 0
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        rows, cols = len(grid), len(grid[0])
        def bfs(r, c):
            nonlocal values
            visited.add((r, c))
            values += grid[r][c]
            for dr, dc in directions:
                new_r, new_c = r+dr, c+dc
                if new_r in range(rows) and new_c in range(cols) and ((new_r, new_c)) not in visited and grid[new_r][new_c] > 0:
                    bfs(new_r, new_c)
        
        for r in range(rows):
            for c in range(cols):
                if (r, c) not in visited and grid[r][c] > 0:
                    bfs(r, c)
                    if values % k == 0:
                        ans += 1
                    values = 0
        return ans

Time Complexity: $O(m * n)$
Space Complexity: $O(m * n)$