LeetCode in Kotlin

3619. Count Islands With Total Value Divisible by K

Medium

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.

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

Explanation:

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

Explanation:

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

class Solution {
    private var m = 0
    private var n = 0

    fun countIslands(grid: Array<IntArray>, k: Int): Int {
        var count = 0
        m = grid.size
        n = grid[0].size
        for (i in 0..<m) {
            for (j in 0..<n) {
                if (grid[i][j] != 0) {
                    val curr = dfs(i, j, grid)
                    if (curr % k == 0) {
                        count++
                    }
                }
            }
        }
        return count
    }

    private fun dfs(i: Int, j: Int, grid: Array<IntArray>): Int {
        if (i >= m || j >= n || i < 0 || j < 0 || grid[i][j] == 0) {
            return Int.Companion.MAX_VALUE
        }
        var count = grid[i][j]
        grid[i][j] = 0
        val x = dfs(i + 1, j, grid)
        val y = dfs(i, j + 1, grid)
        val a = dfs(i - 1, j, grid)
        val b = dfs(i, j - 1, grid)
        if (x != Int.Companion.MAX_VALUE) {
            count += x
        }
        if (y != Int.Companion.MAX_VALUE) {
            count += y
        }
        if (a != Int.Companion.MAX_VALUE) {
            count += a
        }
        if (b != Int.Companion.MAX_VALUE) {
            count += b
        }
        return count
    }
}

This site is open source. Improve this page.