← All solutions
October 26Medium

Count islands with total value divisible by k

  • Array
  • DFS
  • BFS
  • Union-Find
  • Matrix

Problem

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.

Solution

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        ans = 0
        m, n = len(grid), len(grid[0])

        def compute(i,j):
            res = grid[i][j]
            grid[i][j] = 0
            for dx, dy in (1,0),(-1,0),(0,1),(0,-1):
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n:
                    if grid[x][y]:
                        res += compute(x,y)
            return res

        for i in range(m):
            for j in range(n):
                if grid[i][j] and not compute(i,j) % k:
                    ans += 1
        return ans