LeetCode 2435 - Paths in Matrix Whose Sum Is Divisible by K

This problem asks us to count the number of paths in a 2D integer matrix from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1) such that the sum of the values along the path is divisible by a given integer k.

leetcodehardarraydynamic-programmingmatrix

LeetCode Problem 2435

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

This problem asks us to count the number of paths in a 2D integer matrix from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1) such that the sum of the values along the path is divisible by a given integer k. Movement is restricted to only down or right at each step.

The input grid is a 2D array of integers representing the matrix, and k is a positive integer between 1 and 50. The output is an integer representing the count of valid paths, modulo 10^9 + 7.

The constraints indicate that while the total number of cells can be up to 5 * 10^4, each dimension individually can also reach 5 * 10^4. Each cell contains a non-negative integer less than or equal to 100. These constraints suggest that a brute-force approach enumerating all paths would be computationally infeasible, as the number of paths can grow exponentially with the grid size.

Important edge cases include small grids (1x1, 1xN, Nx1), grids with all zeros, and the case where k = 1, which means all paths are valid because every sum is divisible by 1.

Approaches

Brute Force Approach

The brute-force approach would recursively explore all possible paths from (0, 0) to (m - 1, n - 1), keeping track of the running sum along each path. Whenever we reach the bottom-right corner, we check if the sum is divisible by k and increment a counter if it is. While correct, this approach is exponential in the number of cells, O(2^(m+n)), because each cell branches into two possibilities: moving right or down. This is far too slow given the constraints.

Optimal Approach

The optimal approach leverages dynamic programming with modular arithmetic. Instead of tracking the absolute sum along each path, we track the sum modulo k at each cell. Specifically, we define a 3D DP array dp[i][j][r] representing the number of paths to cell (i, j) with sum modulo k equal to r.

We can compute each dp[i][j] using values from the cell above (i-1, j) and the cell to the left (i, j-1), updating the modulo sums accordingly. This reduces the state space to O(m * n * k) which is feasible given the constraints, since k is at most 50.

The key insight is that sum % k behaves well under addition: (a + b) % k = ((a % k) + (b % k)) % k. This allows us to propagate path counts efficiently without storing actual sums.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(m+n)) O(m+n) Explore all paths recursively, track sum
Optimal O(m * n * k) O(n * k) DP using sum modulo k; can optimize space by storing only one row at a time

Algorithm Walkthrough

  1. Initialize a 2D DP array of size [n][k] to represent the current row. Each element dp[j][r] stores the number of paths to cell (i, j) with sum modulo k equal to r. Initialize all to 0.
  2. Set the starting cell (0, 0) such that dp[0][grid[0][0] % k] = 1 because there is one path with that modulo.
  3. Iterate over each row i from 0 to m-1.
  4. For each cell in the row (i, j), iterate over all possible previous modulo sums r from the cell above (i-1, j) and left (i, j-1) if they exist.
  5. For each previous sum r, calculate the new modulo as (r + grid[i][j]) % k and update the current dp[j][new_mod] by adding the number of paths from the previous cell.
  6. Apply modulo 10^9 + 7 during each update to avoid overflow.
  7. After processing the last row, the answer is stored in dp[n-1][0], the number of paths to the bottom-right cell with sum divisible by k.

Why it works: Each dp[j][r] correctly counts all paths ending at (i, j) with sum modulo k equal to r. The modulo operation preserves the divisibility property, and combining results from the left and above ensures all paths are counted exactly once.

Python Solution

from typing import List

class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        MOD = 10**9 + 7
        m, n = len(grid), len(grid[0])
        dp = [[0] * k for _ in range(n)]
        dp[0][grid[0][0] % k] = 1
        
        for i in range(m):
            new_dp = [[0] * k for _ in range(n)]
            for j in range(n):
                for r in range(k):
                    if i > 0:
                        new_mod = (r + grid[i][j]) % k
                        new_dp[j][new_mod] = (new_dp[j][new_mod] + dp[j][r]) % MOD
                    if j > 0:
                        new_mod = (r + grid[i][j]) % k
                        new_dp[j][new_mod] = (new_dp[j][new_mod] + new_dp[j-1][r]) % MOD
                if i == 0 and j == 0:
                    new_dp[j][grid[0][0] % k] = 1
            dp = new_dp
        return dp[n-1][0]

Explanation: We maintain a rolling DP array representing each row. For each cell, we combine counts from the top and left cells, updating modulo sums. Using a temporary new_dp ensures we do not overwrite current row values prematurely. Finally, dp[n-1][0] contains the number of valid paths.

Go Solution

func numberOfPaths(grid [][]int, k int) int {
    MOD := int(1e9 + 7)
    m, n := len(grid), len(grid[0])
    dp := make([][]int, n)
    for j := 0; j < n; j++ {
        dp[j] = make([]int, k)
    }
    dp[0][grid[0][0] % k] = 1
    
    for i := 0; i < m; i++ {
        newDp := make([][]int, n)
        for j := 0; j < n; j++ {
            newDp[j] = make([]int, k)
        }
        for j := 0; j < n; j++ {
            for r := 0; r < k; r++ {
                if i > 0 {
                    newMod := (r + grid[i][j]) % k
                    newDp[j][newMod] = (newDp[j][newMod] + dp[j][r]) % MOD
                }
                if j > 0 {
                    newMod := (r + grid[i][j]) % k
                    newDp[j][newMod] = (newDp[j][newMod] + newDp[j-1][r]) % MOD
                }
            }
            if i == 0 && j == 0 {
                newDp[j][grid[0][0]%k] = 1
            }
        }
        dp = newDp
    }
    return dp[n-1][0]
}

Go-specific notes: Slices are dynamically allocated. We handle modulo operations similarly to Python. The initialization of newDp ensures previous row values are not overwritten. Overflow is prevented by applying modulo at each addition.

Worked Examples

Example 1

grid = [[5,2,4],
        [3,0,5],
        [0,7,2]], k = 3
  • Start at (0,0) with sum modulo k = 2 (5 % 3 = 2).
  • Moving right (0,1) sum modulo 3: (2 + 2) % 3 = 1
  • Moving down (1,0) sum modulo 3: (2 + 3) % 3 = 2
  • Continue until (2,2). Paths with modulo 0 are counted.
  • Final count: 2 paths.

The DP array at (2,2) shows:

Modulo Count
0 2
1 0
2 2

Answer: 2

Example 2

grid = [[0,0]], k = 5
  • Only one path (0,0) -> (0,1). Sum = 0, divisible by 5.
  • DP at (0,1): modulo 0 → count = 1
  • Answer: 1

Example 3

grid = [[7,3,4,9],
        [2,3,6,2],
        [2,3,7,0]], k =