Facebook Pixel

3619. Count Islands With Total Value Divisible by K

MediumDepth-First SearchBreadth-First SearchUnion FindArrayMatrix
Leetcode Link

Problem 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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To solve this problem, notice that each island is a group of connected positive values. We need a way to visit every cell that forms an island and sum their values. Depth-first search (DFS) is a good fit for finding and exploring all cells that belong to one island, moving in four directions from each land cell. As we traverse, we can accumulate the sum of cell values for each island and mark each cell as visited, so we don't count it more than once. After exploring one island, we just check if the sum found is divisible by k and move to the next island. Repeating this process for every cell in the grid ensures all islands are checked.

Solution Approach

A depth-first search (DFS) approach helps to identify and process each island. The idea is to loop through the grid, and whenever a positive integer (land) is found, perform DFS to traverse the entire island and sum its values.

Here's the step-by-step approach:

  1. Directions for Movement: Define possible movements using four directions: up, down, left, and right. These can be stored as coordinate offsets or tuples.

  2. DFS Traversal: Create a recursive dfs(i, j) function. For a starting cell (i, j) with positive value, add its value to the sum, and mark it as visited by setting it to 0. Then, for each of the four directions, check if the adjacent cell is inside the grid and positive. If so, recursively visit it and add its result to the total sum. The function returns the final sum of the current island.

  3. Grid Traversal: Iterate through every cell in the grid.

    • For each cell that is positive, call dfs(i, j) to find the total sum for that island.
    • If the sum returned is divisible by k, increment the answer counter.

  4. Output: After traversing the whole grid, return the total number of islands whose values are divisible by k.

Here’s a summary in code-like pseudocode:

for i in 0..m-1:
    for j in 0..n-1:
        if grid[i][j] > 0:
            total = dfs(i, j)
            if total % k == 0:
                count += 1

The DFS ensures each land cell is only visited once, both for marking and for calculating the sum. Setting visited cells to 0 prevents revisiting.

This approach leverages:

  • Depth-First Search (DFS) for traversing connected components (islands).
  • 2D array manipulation for grid-based problems.
  • Simple arithmetic for divisibility checking.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Suppose the input grid and k are as follows:

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

Let's walk through the solution step by step:

Step 1: Initialization

We set up a counter to keep track of qualifying islands. We'll perform DFS from every unvisited positive cell.

Step 2: First Island Discovery (Top-left cluster of '2's)

  • Start at (0,0): grid[0][0] = 2 (positive)
  • Begin DFS: mark (0,0) as visited (set to 0) and accumulate sum = 2
  • Visit right ((0,1)): grid[0][1]=2, mark as 0, sum = 4
  • Visit down ((1,1)): grid[1][1]=2, mark as 0, sum = 6
    • From here, all adjacent cells are 0 or out of bounds.
  • Island sum = 6
  • 6 % 4 = 2 (not divisible), so counter remains 0

Step 3: Next Positive Cell (0,3), Starts Second Island

  • Start at (0,3): grid[0][3]=3, mark as 0, sum=3
  • No connected positive cells in four directions.
  • Island sum = 3
  • 3 % 4 = 3 (not divisible), counter is still 0

Step 4: Next Positive Cell (2,0), Third Island

  • Start at (2,0): grid[2][0]=4, mark as 0, sum=4
  • No connected positive cells in four directions.
  • Island sum = 4
  • 4 % 4 = 0 (divisible), increment counter to 1

Step 5: Next Positive Cell (2,2), Fourth Island

  • Start at (2,2): grid[2][2]=3, mark as 0, sum=3
  • Visit right ((2,3)): grid[2][3]=3, mark as 0, sum=6
  • No more connected positives in four directions.
  • Island sum = 6
  • 6 % 4 = 2 (not divisible), counter is 1

Step 6: Complete Traversal

No more positive cells. Algorithm finishes.

Result: Only one island (cell (2,0)) has sum divisible by 4.

Final Answer: 1

Solution Implementation

1from typing import List
2
3class Solution:
4    def countIslands(self, grid: List[List[int]], k: int) -> int:
5        # Helper to traverse current island and calculate its total value
6        def dfs(row: int, col: int) -> int:
7            total = grid[row][col]
8            grid[row][col] = 0  # Mark cell as visited
9            # Explore all 4-directional neighbors
10            for d in range(4):
11                new_row = row + dir_row[d]
12                new_col = col + dir_col[d]
13                if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col]:
14                    total += dfs(new_row, new_col)
15            return total
16
17        rows, cols = len(grid), len(grid[0])
18        # Directions for row and col offset (up, right, down, left)
19        dir_row = [-1, 0, 1, 0]
20        dir_col = [0, 1, 0, -1]
21
22        islands_count = 0
23        for r in range(rows):
24            for c in range(cols):
25                # If land cell is found, start DFS traversal
26                if grid[r][c]:
27                    if dfs(r, c) % k == 0:  # Check divisibility criterion
28                        islands_count += 1
29
30        return islands_count
31
1class Solution {
2    private int rows;                  // Number of rows in the grid
3    private int cols;                  // Number of columns in the grid
4    private int[][] grid;              // Reference to the input grid
5    private final int[] dirOffsets = {-1, 0, 1, 0, -1}; // Direction offsets for 4 directions (up, right, down, left)
6
7    // Main method to count islands where the sum of island cells is divisible by k
8    public int countIslands(int[][] grid, int k) {
9        this.rows = grid.length;
10        this.cols = grid[0].length;
11        this.grid = grid;
12        int islandCount = 0;
13
14        for (int i = 0; i < rows; ++i) {
15            for (int j = 0; j < cols; ++j) {
16                // If the current cell is land (positive) and the sum of the island is divisible by k
17                if (grid[i][j] > 0 && dfs(i, j) % k == 0) {
18                    islandCount++;
19                }
20            }
21        }
22        return islandCount;
23    }
24
25    // Depth-First Search to compute the sum of values in an island and mark them as visited
26    private long dfs(int row, int col) {
27        long sum = grid[row][col]; // Store the value of the current cell
28        grid[row][col] = 0;        // Mark the cell as visited by setting it to 0
29
30        // Explore all 4 directions: up, right, down, left
31        for (int d = 0; d < 4; ++d) {
32            int nextRow = row + dirOffsets[d];
33            int nextCol = col + dirOffsets[d + 1];
34            // Check bounds and whether the neighboring cell is part of the island
35            if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] > 0) {
36                sum += dfs(nextRow, nextCol); // Accumulate the sum recursively
37            }
38        }
39        return sum;
40    }
41}
42
1class Solution {
2public:
3    // Counts the number of islands whose sum of values is divisible by k
4    int countIslands(std::vector<std::vector<int>>& grid, int k) {
5        int rows = grid.size();
6        int cols = grid[0].size();
7        std::vector<int> directions = {-1, 0, 1, 0, -1}; // for navigating four adjacent cells
8
9        // Recursive DFS lambda to compute island sum.
10        auto dfs = [&](auto&& self, int x, int y) -> long long {
11            long long sum = grid[x][y];    // start sum with current cell's value
12            grid[x][y] = 0;                // mark cell as visited by setting to 0
13
14            // Explore all 4 directions (up, right, down, left)
15            for (int d = 0; d < 4; ++d) {
16                int newX = x + directions[d];
17                int newY = y + directions[d + 1];
18
19                // Check bounds and whether cell is part of the current island
20                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY]) {
21                    sum += self(self, newX, newY);
22                }
23            }
24            return sum;
25        };
26
27        int islandCount = 0;
28
29        // Traverse every cell in the grid
30        for (int x = 0; x < rows; ++x) {
31            for (int y = 0; y < cols; ++y) {
32                // If cell is non-zero, it's a new island
33                if (grid[x][y]) {
34                    long long islandSum = dfs(dfs, x, y);
35                    // If the island's sum is divisible by k, increment count
36                    if (islandSum % k == 0) {
37                        ++islandCount;
38                    }
39                }
40            }
41        }
42        return islandCount;
43    }
44};
45
1/**
2 * Counts the number of islands in a grid where the sum of the island's cell values is divisible by k.
3 * @param grid - A 2D array of numbers representing the grid.
4 * @param k - The divisor for the sum of each island's cells.
5 * @returns The number of islands whose total values are divisible by k.
6 */
7function countIslands(grid: number[][], k: number): number {
8    const rows = grid.length;
9    const cols = grid[0].length;
10
11    // Directions for moving up, right, down, left
12    const directions = [-1, 0, 1, 0, -1];
13
14    /**
15     * Performs a DFS to visit all cells in the current island and returns their sum.
16     * @param row - The current row index.
17     * @param col - The current column index.
18     * @returns The sum of this island's cells.
19     */
20    function dfs(row: number, col: number): number {
21        let total = grid[row][col];
22        // Mark the cell as visited by setting to 0
23        grid[row][col] = 0;
24
25        // Explore all four directions
26        for (let d = 0; d < 4; d++) {
27            const newRow = row + directions[d];
28            const newCol = col + directions[d + 1];
29
30            // Continue DFS if the adjacent cell is within bounds and has a positive value
31            if (
32                newRow >= 0 && newRow < rows &&
33                newCol >= 0 && newCol < cols &&
34                grid[newRow][newCol] > 0
35            ) {
36                total += dfs(newRow, newCol);
37            }
38        }
39        return total;
40    }
41
42    let islandCount = 0;
43
44    // Traverse each cell in the grid
45    for (let row = 0; row < rows; row++) {
46        for (let col = 0; col < cols; col++) {
47            // Start DFS if the cell is positive (unvisited land)
48            if (grid[row][col] > 0) {
49                // Compute sum of island and check if it's divisible by k
50                if (dfs(row, col) % k === 0) {
51                    islandCount++;
52                }
53            }
54        }
55    }
56
57    return islandCount;
58}
59

Time and Space Complexity

The time complexity of the code is O(m * n). This is because each cell in the grid is visited at most once during the DFS traversal. For each cell, the DFS may traverse all connected cells but never revisits any, ensuring the total number of operations is proportional to the number of cells in the grid.

The space complexity is also O(m * n). This comes from the recursion stack in the DFS calls, which in the worst case (if all cells form a single large island) can reach up to O(m * n) depth, in addition to the space used by the grid itself.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Recommended Readings

DFS Fundamentals

https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests

BFS Fundamentals

https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More