3619: Count Islands With Total Value Divisible by K

Difficulty: Medium

Topics: Matrix, DFS, BFS, Flood Fill

Companies: Amazon, Google, Microsoft

Count Islands With Total Value Divisible by K visualization

Pro Tip: For grid problems with connectivity, always consider using DFS, BFS, or Union-Find. DFS is simpler for small grids, but BFS is safer for large grids to avoid stack overflow.

Problem Statement

Given an m x n matrix grid and a positive integer k, count the number of islands where:

An island is a group of positive integers (land) connected 4-directionally (up, down, left, right)
The total value of an island is the sum of all its land cells
The island count is incremented when total_value % k == 0

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

Island sums: 1+5+1+1+4+7+2 = 21 (not divisible by 5), 5 = 5 (divisible), 8 = 8 (not divisible)

Problem Link: View on LeetCode ↗

Key Insight

The problem requires:

Identifying connected components (islands) in a grid
Calculating the sum of values for each island
Counting islands where the sum is divisible by k

Note: Water cells (0) are not part of any island and should be skipped during traversal.

Approach 1: Depth-First Search (DFS)

Recursively explore each island starting from unvisited land cells.

Algorithm Steps

Create a visited matrix to track visited cells
Iterate through each cell in the grid
If cell is land (value > 0) and not visited:
- Initialize sum to 0
- Perform DFS to explore all connected land cells
- Add current cell's value to sum
- Mark cell as visited
- Recursively visit all 4-directional neighbors
After DFS completes, check if sum % k == 0
If yes, increment island count

Complexity Analysis

Time Complexity	Space Complexity
O(mn)	O(mn)

Each cell is visited once. Space is used for visited matrix and recursion stack.

DFS Solution

class Solution {
public:
    int m, n;
    vector<vector<bool>> visited;
    
    long dfs(vector<vector<int>>& grid, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0)
            return 0;
            
        visited[r][c] = true;
        long sum = grid[r][c];
        sum += dfs(grid, r+1, c);
        sum += dfs(grid, r-1, c);
        sum += dfs(grid, r, c+1);
        sum += dfs(grid, r, c-1);
        return sum;
    }
    
    int countIslands(vector<vector<int>>& grid, int k) {
        m = grid.size();
        n = grid[0].size();
        visited = vector<vector<bool>>(m, vector<bool>(n, false));
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] > 0) {
                    long islandSum = dfs(grid, i, j);
                    if (islandSum % k == 0) count++;
                }
            }
        }
        return count;
    }
};

class Solution {
    private int m, n;
    private boolean[][] visited;
    
    private long dfs(int[][] grid, int r, int c) {
        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || grid[r][c] == 0)
            return 0;
            
        visited[r][c] = true;
        long sum = grid[r][c];
        sum += dfs(grid, r+1, c);
        sum += dfs(grid, r-1, c);
        sum += dfs(grid, r, c+1);
        sum += dfs(grid, r, c-1);
        return sum;
    }
    
    public int countIslands(int[][] grid, int k) {
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        int count = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] > 0) {
                    long islandSum = dfs(grid, i, j);
                    if (islandSum % k == 0) count++;
                }
            }
        }
        return count;
    }
}

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        count = 0
        
        def dfs(r, c):
            if r < 0 or r >= m or c < 0 or c >= n or visited[r][c] or grid[r][c] == 0:
                return 0
            visited[r][c] = True
            total = grid[r][c]
            total += dfs(r+1, c)
            total += dfs(r-1, c)
            total += dfs(r, c+1)
            total += dfs(r, c-1)
            return total
        
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] > 0:
                    island_sum = dfs(i, j)
                    if island_sum % k == 0:
                        count += 1
        return count

Implementation Note: DFS is concise but may cause stack overflow for large grids. Use iterative DFS or BFS for production systems.

Approach 2: Breadth-First Search (BFS)

Iteratively explore each island using a queue to avoid recursion depth issues.

Algorithm Steps

Create a visited matrix to track visited cells
Iterate through each cell in the grid
If cell is land (value > 0) and not visited:
- Initialize sum to 0
- Create a queue and add current cell
- Mark cell as visited
- While queue is not empty:
  - Dequeue a cell
  - Add its value to sum
  - Check all 4-directional neighbors
  - If neighbor is valid land cell, add to queue
After BFS completes, check if sum % k == 0
If yes, increment island count

Complexity Analysis

Time Complexity	Space Complexity
O(mn)	O(mn)

Same as DFS but avoids recursion stack limitations.

BFS Solution

class Solution {
public:
    int countIslands(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int count = 0;
        vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] > 0) {
                    long islandSum = 0;
                    queue<pair<int,int>> q;
                    q.push({i, j});
                    visited[i][j] = true;
                    
                    while (!q.empty()) {
                        auto [r, c] = q.front();
                        q.pop();
                        islandSum += grid[r][c];
                        
                        for (auto [dr, dc] : directions) {
                            int nr = r + dr, nc = c + dc;
                            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] > 0) {
                                visited[nr][nc] = true;
                                q.push({nr, nc});
                            }
                        }
                    }
                    if (islandSum % k == 0) count++;
                }
            }
        }
        return count;
    }
};

class Solution {
    public int countIslands(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int count = 0;
        int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] > 0) {
                    long islandSum = 0;
                    Queue<int[]> q = new LinkedList<>();
                    q.offer(new int[]{i, j});
                    visited[i][j] = true;
                    
                    while (!q.isEmpty()) {
                        int[] cell = q.poll();
                        int r = cell[0], c = cell[1];
                        islandSum += grid[r][c];
                        
                        for (int[] d : directions) {
                            int nr = r + d[0], nc = c + d[1];
                            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] > 0) {
                                visited[nr][nc] = true;
                                q.offer(new int[]{nr, nc});
                            }
                        }
                    }
                    if (islandSum % k == 0) count++;
                }
            }
        }
        return count;
    }
}

from collections import deque

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        count = 0
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] > 0:
                    island_sum = 0
                    q = deque()
                    q.append((i, j))
                    visited[i][j] = True
                    
                    while q:
                        r, c = q.popleft()
                        island_sum += grid[r][c]
                        for dr, dc in directions:
                            nr, nc = r + dr, c + dc
                            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] > 0:
                                visited[nr][nc] = True
                                q.append((nr, nc))
                    
                    if island_sum % k == 0:
                        count += 1
        return count

Implementation Note: BFS is iterative and avoids recursion depth issues, making it suitable for large grids (m*n ≤ 10^5).

Approach 3: Iterative DFS with Stack

Implement DFS iteratively using a stack for better memory control.

Algorithm Steps

Create a visited matrix to track visited cells
Iterate through each cell in the grid
If cell is land (value > 0) and not visited:
- Initialize sum to 0
- Create a stack and push current cell
- Mark cell as visited
- While stack is not empty:
  - Pop a cell
  - Add its value to sum
  - Check all 4-directional neighbors
  - If neighbor is valid land cell, push to stack
After DFS completes, check if sum % k == 0
If yes, increment island count

Complexity Analysis

Time Complexity	Space Complexity
O(mn)	O(mn)

Same as BFS but uses stack instead of queue.

Iterative DFS Solution

class Solution {
public:
    int countIslands(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int count = 0;
        vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] > 0) {
                    long islandSum = 0;
                    stack<pair<int,int>> st;
                    st.push({i, j});
                    visited[i][j] = true;
                    
                    while (!st.empty()) {
                        auto [r, c] = st.top();
                        st.pop();
                        islandSum += grid[r][c];
                        
                        for (auto [dr, dc] : directions) {
                            int nr = r + dr, nc = c + dc;
                            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] > 0) {
                                visited[nr][nc] = true;
                                st.push({nr, nc});
                            }
                        }
                    }
                    if (islandSum % k == 0) count++;
                }
            }
        }
        return count;
    }
};

class Solution {
    public int countIslands(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int count = 0;
        int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] > 0) {
                    long islandSum = 0;
                    Stack<int[]> stack = new Stack<>();
                    stack.push(new int[]{i, j});
                    visited[i][j] = true;
                    
                    while (!stack.isEmpty()) {
                        int[] cell = stack.pop();
                        int r = cell[0], c = cell[1];
                        islandSum += grid[r][c];
                        
                        for (int[] d : directions) {
                            int nr = r + d[0], nc = c + d[1];
                            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && grid[nr][nc] > 0) {
                                visited[nr][nc] = true;
                                stack.push(new int[]{nr, nc});
                            }
                        }
                    }
                    if (islandSum % k == 0) count++;
                }
            }
        }
        return count;
    }
}

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        count = 0
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] > 0:
                    island_sum = 0
                    stack = [(i, j)]
                    visited[i][j] = True
                    
                    while stack:
                        r, c = stack.pop()
                        island_sum += grid[r][c]
                        for dr, dc in directions:
                            nr, nc = r + dr, c + dc
                            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and grid[nr][nc] > 0:
                                visited[nr][nc] = True
                                stack.append((nr, nc))
                    
                    if island_sum % k == 0:
                        count += 1
        return count

Implementation Note: Iterative DFS gives DFS-like traversal with BFS-like memory characteristics, avoiding recursion limits.

Approach Comparison

Approach	Pros	Cons	Best For
Recursive DFS	Concise code, easy to understand	Stack overflow risk for large grids	Small grids (m,n < 100)
BFS	No recursion limits, predictable memory	Slightly more code	Large grids (m*n ≤ 10^5)
Iterative DFS	DFS traversal without recursion	Uses stack, memory similar to BFS	When DFS order is important

Important: For production systems, always prefer BFS or iterative DFS to avoid stack overflow exceptions.

Edge Cases and Testing

1. Single Cell Islands

Input: [[5]], k = 5 → Output: 1

2. No Islands

Input: [[0,0],[0,0]], k = 5 → Output: 0

3. All Cells Form One Island

Input: [[3,3],[3,3]], k = 3 → Output: 1 (since 12%3==0)

4. Large Values

Input: [[1000000]], k = 1000000 → Output: 1

Warning: Always use long for sum calculations to prevent integer overflow with large values (up to 10^6 per cell).

Frequently Asked Questions

1. What defines an "island" in this problem?

An island is a group of positive integers (values > 0) connected 4-directionally (up, down, left, right). Water cells (0) are not part of any island.

2. Why use visited matrix instead of modifying grid?

Modifying the grid might be acceptable in some cases, but using a visited matrix preserves input data and is cleaner for production code.

3. How to handle large sums that might overflow?

Use long (64-bit integer) for sum calculations since maximum sum could be 10^5 cells * 10^6 value = 10^11, which fits in long but not in 32-bit int.

4. Can we use Union-Find for this problem?

Union-Find is possible but less efficient for this scenario since we need to compute the sum for each island. DFS/BFS are more straightforward.

5. Why are we using 4-directional instead of 8-directional?

The problem specifies 4-directional connectivity (horizontal and vertical). Diagonal connections are not considered.

6. How does BFS avoid stack overflow?

BFS uses a queue and iterative processing, avoiding deep recursion stacks that can cause overflow in large grids.

7. What is the maximum grid size we can handle?

With O(mn) space complexity, we can handle grids up to 10^5 cells (as per constraints). For larger grids, we'd need more optimized approaches.

8. Can we optimize the space further?

We could modify the grid to mark visited cells (e.g., set to 0 or negative), reducing space to O(1), but this alters input data.

9. How to handle k=1?

Since any integer mod 1 is 0, all islands would be counted. The solution naturally handles this case.

10. Why use directions array?

Using a directions array makes code cleaner and easier to modify if 8-directional movement is needed later.

Final Insight: This problem combines grid traversal with mathematical checks. Understanding flood fill algorithms is crucial for solving similar matrix connectivity problems efficiently.