Skip to content

2435. Paths in Matrix Whose Sum Is Divisible by K 👍

Approach 1: Top-down

  • Time: $O(mnk)$
  • Space: $O(mnk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int numberOfPaths(vector<vector<int>>& grid, int k) {
    m = grid.size();
    n = grid[0].size();
    // dp[i][j][sum] : = the number of paths to(i, j), where the sum / k == sum
    dp.resize(m, vector<vector<int>>(n, vector<int>(k, -1)));
    return numberOfPaths(grid, 0, 0, 0, k);
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  int m;
  int n;
  vector<vector<vector<int>>> dp;

  int numberOfPaths(const vector<vector<int>>& grid, int i, int j, int sum,
                    int k) {
    if (i == m || j == n)
      return 0;
    if (i == m - 1 && j == n - 1)
      return (sum + grid[i][j]) % k == 0;
    if (dp[i][j][sum] != -1)
      return dp[i][j][sum];
    const int newSum = (sum + grid[i][j]) % k;
    return dp[i][j][sum] = (numberOfPaths(grid, i + 1, j, newSum, k) +
                            numberOfPaths(grid, i, j + 1, newSum, k)) %
                           kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public int numberOfPaths(int[][] grid, int k) {
    m = grid.length;
    n = grid[0].length;
    // dp[i][j][sum] := the number of paths to (i, j), where the sum / k == sum
    dp = new Integer[m][n][k];
    return numberOfPaths(grid, 0, 0, 0, k);
  }

  private static final int kMod = 1_000_000_007;
  private int m;
  private int n;
  private Integer[][][] dp;

  private int numberOfPaths(int[][] grid, int i, int j, int sum, int k) {
    if (i == m || j == n)
      return 0;
    if (i == m - 1 && j == n - 1)
      return (sum + grid[i][j]) % k == 0 ? 1 : 0;
    if (dp[i][j][sum] != null)
      return dp[i][j][sum];
    final int newSum = (sum + grid[i][j]) % k;
    return dp[i][j][sum] = (numberOfPaths(grid, i + 1, j, newSum, k) +
                            numberOfPaths(grid, i, j + 1, newSum, k)) %
                           kMod;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
    kMod = 1_000_000_007
    m = len(grid)
    n = len(grid[0])

    @functools.lru_cache(None)
    def dp(i: int, j: int, summ: int) -> int:
      """
      Returns the number of paths to (i, j), where the sum / k == sum.
      """
      if i == m or j == n:
        return 0
      if i == m - 1 and j == n - 1:
        return 1 if (summ + grid[i][j]) % k == 0 else 0
      newSum = (summ + grid[i][j]) % k
      return (dp(i + 1, j, newSum) + dp(i, j + 1, newSum)) % kMod

    return dp(0, 0, 0)

Approach 2: Bottom-up

  • Time: $O(mnk)$
  • Space: $O(mnk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int numberOfPaths(vector<vector<int>>& grid, int k) {
    constexpr int kMod = 1'000'000'007;
    const int m = grid.size();
    const int n = grid[0].size();
    // dp[i][j][sum] : = the number of paths to(i, j), where the sum / k == sum
    vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k)));
    dp[0][0][grid[0][0] % k] = 1;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int sum = 0; sum < k; ++sum) {
          const int newSum = (sum + grid[i][j]) % k;
          if (i > 0)
            dp[i][j][newSum] += dp[i - 1][j][sum];
          if (j > 0)
            dp[i][j][newSum] += dp[i][j - 1][sum];
          dp[i][j][newSum] %= kMod;
        }

    return dp[m - 1][n - 1][0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int numberOfPaths(int[][] grid, int k) {
    final int kMod = 1_000_000_007;
    final int m = grid.length;
    final int n = grid[0].length;
    // dp[i][j][sum] : = the number of paths to(i, j), where the sum / k == sum
    int[][][] dp = new int[m][n][k];
    dp[0][0][grid[0][0] % k] = 1;

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        for (int sum = 0; sum < k; ++sum) {
          final int newSum = (sum + grid[i][j]) % k;
          if (i > 0)
            dp[i][j][newSum] += dp[i - 1][j][sum];
          if (j > 0)
            dp[i][j][newSum] += dp[i][j - 1][sum];
          dp[i][j][newSum] %= kMod;
        }

    return dp[m - 1][n - 1][0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
    kMod = 1_000_000_007
    m = len(grid)
    n = len(grid[0])
    # dp[i][j][sum] := the number of paths to (i, j), where the sum / k == sum
    dp = [[[0] * k for j in range(n)] for i in range(m)]
    dp[0][0][grid[0][0] % k] = 1

    for i in range(m):
      for j in range(n):
        for summ in range(k):
          newSum = (summ + grid[i][j]) % k
          if i > 0:
            dp[i][j][newSum] += dp[i - 1][j][summ]
          if j > 0:
            dp[i][j][newSum] += dp[i][j - 1][summ]
          dp[i][j][newSum] %= kMod

    return dp[m - 1][n - 1][0]