3619. Count Islands With Total Value Divisible by K

SourceBiweekly Contest 161 Q2DifficultyMediumRating1461

Description

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 <= 10⁵
0 <= grid[i][j] <= 10⁶
1 <= k <= 10⁶

Solutions

Solution 1: DFS

Thinking

An island is a 4-connected component of positive cells. We need each island's value sum modulo \(k\), not its shape. DFS accumulates the sum while zeroing visited cells, so a cell is never expanded twice.

Scan the grid and start \(\textit{dfs}\) from every still-positive cell; increment the answer when the returned sum is divisible by \(k\). The packed offsets \((-1,0,1,0,-1)\) generate the four neighbors.

Each cell is entered once, so the time matches the grid size.

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.

In the main function, we traverse the entire grid. For each unvisited position \((i, j)\), if its value is greater than 0, we call \(\textit{dfs}(i, j)\) to calculate the total value of that island. If the total value is divisible by \(k\), we increment the answer by one.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns of the grid, respectively.

Python3JavaC++GoTypeScript

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

class Solution {
    private int m;
    private int n;
    private int[][] grid;
    private final int[] dirs = {-1, 0, 1, 0, -1};

    public int countIslands(int[][] grid, int k) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] > 0 && dfs(i, j) % k == 0) {
                    ++ans;
                }
            }
        }
        return ans;
    }

    private long dfs(int i, int j) {
        long s = grid[i][j];
        grid[i][j] = 0;
        for (int d = 0; d < 4; ++d) {
            int x = i + dirs[d], y = j + dirs[d + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
                s += dfs(x, y);
            }
        }
        return s;
    }
}

class Solution {
public:
    int countIslands(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dirs = {-1, 0, 1, 0, -1};

        auto dfs = [&](this auto&& dfs, int i, int j) -> long long {
            long long s = grid[i][j];
            grid[i][j] = 0;
            for (int d = 0; d < 4; ++d) {
                int x = i + dirs[d], y = j + dirs[d + 1];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
                    s += dfs(x, y);
                }
            }
            return s;
        };

        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] && dfs(i, j) % k == 0) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

func countIslands(grid [][]int, k int) (ans int) {
    m, n := len(grid), len(grid[0])
    dirs := []int{-1, 0, 1, 0, -1}
    var dfs func(i, j int) int
    dfs = func(i, j int) int {
        s := grid[i][j]
        grid[i][j] = 0
        for d := 0; d < 4; d++ {
            x, y := i+dirs[d], j+dirs[d+1]
            if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0 {
                s += dfs(x, y)
            }
        }
        return s
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] > 0 && dfs(i, j)%k == 0 {
                ans++
            }
        }
    }
    return
}

function countIslands(grid: number[][], k: number): number {
    const m = grid.length,
        n = grid[0].length;
    const dirs = [-1, 0, 1, 0, -1];
    const dfs = (i: number, j: number): number => {
        let s = grid[i][j];
        grid[i][j] = 0;
        for (let d = 0; d < 4; d++) {
            const x = i + dirs[d],
                y = j + dirs[d + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > 0) {
                s += dfs(x, y);
            }
        }
        return s;
    };

    let ans = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] > 0 && dfs(i, j) % k === 0) {
                ans++;
            }
        }
    }

    return ans;
}

Solution 2: Explicit Stack

Thinking

An island is a 4-connected component of positive cells, and the answer depends only on whether each component sum is divisible by \(k\). A recursive walk that adds a cell and then zeroes it computes that sum and keeps the same cell out of a second island.

The product \(m \times n\) reaches \(10^5\). A snaking island makes one recursive call per cell, so the call stack overflows before the sum is finished. Zeroing a cell is only a visit mark; a neighbor still belongs to the island exactly when it is still positive.

The cells waiting to be expanded fit on an explicit stack. A cell’s value is added and the cell is zeroed before it is pushed, then its four still-positive neighbors are pushed after the pop. The sum matches the recursive walk, while the stack depth stays under our control. One island can total \(10^{11}\), so the accumulator is a 64-bit integer.

Scanning the grid and starting a walk from every remaining positive cell counts the islands whose sum is divisible by \(k\). Each cell is pushed at most once.

We walk each island with an explicit stack. Starting from a still-positive cell \((i, j)\), record its value in the sum \(s\), set the cell to \(0\), and push its coordinates. Each pop checks the four neighbors. A neighbor that is still positive is added into \(s\), zeroed, and pushed. When the stack is empty, \(s\) is the island’s total value. Zeroing before the push keeps a cell from being counted twice.

The main loop scans the grid. Every remaining positive cell starts one walk, and the answer increases when \(s \bmod k = 0\). The sum is stored in a 64-bit integer so that \(10^5\) cells of value up to \(10^6\) do not overflow.