Paths in matrix whose sum is divisible by k

Array Dynamic Programming Matrix

58.7% acceptance

Feb 25, 2026

1340

You are given a 0-indexed m x n integer matrix grid and an integer k. You are currently at position (0, 0) and you want to reach position (m - 1, n - 1) moving only down or right. * Return the number of paths where the sum of the elements on the path is divis ible by k. Since the answer may be very large, return it modulo 109 + 7. *

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_paths(grid: Vec<Vec<i32>>, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let k = k as usize;
    let m = grid.len();
    let n = grid[0].len();
    // dp[i][j][r] = number of paths to (i,j) with sum mod k == r
    let mut dp = vec![vec![vec![0i64; k]; n]; m];
    dp[0][0][(grid[0][0] as usize) % k] = 1;
    for i in 0..m {
      for j in 0..n {
        if i == 0 && j == 0 { continue; }
        let g = grid[i][j] as usize;
        for r in 0..k {
          let mut val = 0i64;
          if i > 0 { val += dp[i-1][j][r]; }
          if j > 0 { val += dp[i][j-1][r]; }
          dp[i][j][(r + g) % k] = (dp[i][j][(r + g) % k] + val) % MOD;
        }
      }
    }
    dp[m-1][n-1][0] as i32
  }
}