# Paths in Matrix Whose Sum Is Divisible by K
**Difficulty:** HARD
[External](https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k)
Canonical: https://scaleengineer.com/dsa/problems/paths-in-matrix-whose-sum-is-divisible-by-k
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
---
## Problem
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 divisible by_ `k`. Since the answer may be very large, return it **modulo** `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/paths-in-matrix-whose-sum-is-divisible-by-k/image0.png) 

**Input:** grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
**Output:** 2
**Explanation:** There are two paths where the sum of the elements on the path is divisible by k.
The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3.
The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.

**Example 2:**

![](https://assets.glich.co/dsa/paths-in-matrix-whose-sum-is-divisible-by-k/image1.png) 

**Input:** grid = [[0,0]], k = 5
**Output:** 1
**Explanation:** The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.

**Example 3:**

![](https://assets.glich.co/dsa/paths-in-matrix-whose-sum-is-divisible-by-k/image2.png) 

**Input:** grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
**Output:** 10
**Explanation:** Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 5 * 104`
* `1 <= m * n <= 5 * 104`
* `0 <= grid[i][j] <= 100`
* `1 <= k <= 50`

# Approaches
## Brute-Force Recursion
This approach involves exploring every possible path from the starting cell `(0, 0)` to the destination `(m-1, n-1)` using recursion. For each path, we keep track of the running sum of its elements. When a path reaches the destination, we check if its total sum is divisible by `k`. To avoid dealing with potentially large sums, we only need to track the remainder of the sum with respect to `k`.
**Time:** O(2^(m+n)) - In the worst case, for each cell, the function branches into two calls. This leads to an exponential number of calls, exploring all possible paths. · **Space:** O(m + n) - This is for the recursion stack depth, which is at most the length of the longest path, `m + n - 1`.
**Pros:** Simple to conceptualize and implement.; It's a direct translation of the problem statement into a recursive structure.
**Cons:** Extremely inefficient due to a massive number of redundant calculations for the same subproblems (reaching the same cell with the same remainder).; Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest of grids.
### Explanation
The core idea is to build a recursive function that explores paths by moving down and right. The state of our recursion will be `(row, col, currentRem)`, representing our current position and the remainder of the sum of elements on the path from `(0,0)` to the cell just before `(row, col)`. When we move to `(row, col)`, we update the remainder. When we reach the destination, we check the final remainder.

```java
class Solution {
    private int MOD = 1_000_000_007;

    public int numberOfPaths(int[][] grid, int k) {
        return countPaths(grid, k, 0, 0, 0);
    }

    private int countPaths(int[][] grid, int k, int r, int c, int currentRem) {
        int m = grid.length;
        int n = grid[0].length;

        // If out of bounds, no path is possible.
        if (r >= m || c >= n) {
            return 0;
        }

        // Update the remainder with the current cell's value.
        currentRem = (currentRem + grid[r][c]) % k;

        // If we are at the destination cell.
        if (r == m - 1 && c == n - 1) {
            // Return 1 if the sum is divisible by k, otherwise 0.
            return (currentRem == 0) ? 1 : 0;
        }

        // Recursively call for right and down moves.
        long pathsDown = countPaths(grid, k, r + 1, c, currentRem);
        long pathsRight = countPaths(grid, k, r, c + 1, currentRem);

        // Return the sum of paths modulo 10^9 + 7.
        return (int)((pathsDown + pathsRight) % MOD);
    }
}
```
### Algorithm
1. Define a recursive function `countPaths(row, col, currentRem)` that takes the current cell coordinates and the remainder of the sum of the path so far.
2. The base case for the recursion is when we go out of the grid boundaries. In this case, there is no valid path, so we return 0.
3. Another base case is when we reach the destination cell `(m-1, n-1)`. We add the value of this cell to our running sum and check if the final sum's remainder modulo `k` is 0. If it is, we have found one valid path and return 1, otherwise, we return 0.
4. In the recursive step, from the current cell `(row, col)`, we calculate the new remainder `newRem = (currentRem + grid[row][col]) % k`.
5. We then make two recursive calls: one for moving down to `(row+1, col)` and one for moving right to `(row, col+1)`, both with the `newRem`.
6. The total number of paths from `(row, col)` is the sum of the results from these two recursive calls. Remember to apply the modulo `10^9 + 7` to the sum of paths.
7. The initial call to the function will be `countPaths(0, 0, 0)`.

## Memoization (Top-Down Dynamic Programming)
The brute-force approach is slow because it repeatedly solves the same subproblems. We can significantly improve performance by using memoization, a top-down dynamic programming technique. We store the results of subproblems in a cache (e.g., a 3D array) so that we only compute the solution for each unique state `(row, col, remainder)` once.
**Time:** O(m * n * k) - Each state `(row, col, rem)` is computed at most once. There are `m * n * k` such states, and each computation takes constant time. · **Space:** O(m * n * k) - For the memoization table. The recursion stack depth adds an `O(m+n)` term, which is dominated.
**Pros:** Drastically more efficient than brute-force, solving the problem within typical time limits.; Maintains a relatively intuitive recursive structure.
**Cons:** Requires a large amount of memory, `O(m * n * k)`, which could be substantial depending on the constraints.; Deep recursion could potentially lead to a stack overflow, although the problem constraints make this unlikely.
### Explanation
The state of a subproblem is uniquely identified by the current cell `(row, col)` and the remainder of the path sum `rem`. We can use a 3D array, `memo[m][n][k]`, to store the number of valid paths for each state. The recursive function will first check this table to see if a result is already available. If not, it computes the result, stores it in the table, and then returns it.

This approach transforms the exponential complexity of the brute-force solution into a polynomial one, making it efficient enough to pass within the given time limits.

```java
class Solution {
    private int m, n, k, MOD = 1_000_000_007;
    private int[][] grid;
    private Integer[][][] memo;

    public int numberOfPaths(int[][] grid, int k) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.k = k;
        this.grid = grid;
        this.memo = new Integer[m][n][k];
        // We want paths to (m-1, n-1) with a final sum remainder of 0.
        return solve(m - 1, n - 1, 0);
    }

    private int solve(int r, int c, int rem) {
        // Base case: out of bounds
        if (r < 0 || c < 0) {
            return 0;
        }

        // Base case: starting cell
        if (r == 0 && c == 0) {
            return (grid[r][c] % k == rem) ? 1 : 0;
        }

        // Check memoization table
        if (memo[r][c][rem] != null) {
            return memo[r][c][rem];
        }

        // Calculate the required remainder from the previous cells
        int requiredRem = (rem - (grid[r][c] % k) + k) % k;

        // Recursive calls for paths from up and left
        int paths = (solve(r - 1, c, requiredRem) + solve(r, c - 1, requiredRem)) % MOD;

        // Store result and return
        return memo[r][c][rem] = paths;
    }
}
```
### Algorithm
1. Define a state for our DP as `(row, col, rem)`, which will store the number of paths from `(0,0)` to `(row, col)` with a path sum remainder of `rem`.
2. Create a 3D memoization table `memo[m][n][k]` initialized with a sentinel value (e.g., `null` or `-1`) to store the results of computed states.
3. Implement a recursive function `solve(row, col, rem)`.
4. In the function, first check if the result for the state `(row, col, rem)` is already in the memoization table. If so, return it.
5. Define the base cases:
   - If `row` or `col` is out of bounds, return 0.
   - If `(row, col)` is `(0,0)`, return 1 if `grid[0][0] % k == rem`, otherwise return 0.
6. For the recursive step, to find the number of paths to `(row, col)` with remainder `rem`, we need to find the number of paths to the preceding cells (`(row-1, col)` and `(row, col-1)`) with a remainder `prevRem` such that `(prevRem + grid[row][col]) % k == rem`. This `prevRem` can be calculated as `(rem - grid[row][col] % k + k) % k`.
7. The result for `solve(row, col, rem)` is `(solve(row-1, col, prevRem) + solve(row, col-1, prevRem)) % MOD`.
8. Store the result in `memo[row][col][rem]` before returning.
9. The final answer is the result of `solve(m-1, n-1, 0)`.

## Tabulation (Bottom-Up Dynamic Programming)
This approach is the iterative, or bottom-up, version of the dynamic programming solution. It systematically fills a DP table, starting from the base case `(0,0)` and moving towards the destination `(m-1, n-1)`. This avoids recursion and its associated overhead, which can sometimes lead to slightly better performance and prevents any risk of stack overflow.
**Time:** O(m * n * k) - We iterate through each cell and each possible remainder, performing constant time work inside the loops. · **Space:** O(m * n * k) - For the 3D DP table.
**Pros:** Avoids recursion, eliminating recursion overhead and stack depth limitations.; Can be more cache-friendly, leading to better practical performance than memoization.
**Cons:** Also requires `O(m * n * k)` space, which is identical to the memoization approach and can be large.
### Explanation
We define a 3D DP table, `dp[i][j][rem]`, to store the number of paths from `(0,0)` to cell `(i,j)` that result in a path sum with remainder `rem`. We fill this table iteratively. For any cell `(i,j)`, the number of paths to it with a certain remainder can be calculated from the number of paths to its neighbors above `(i-1,j)` and to the left `(i,j-1)`. Specifically, a path to `(i-1,j)` with remainder `p_rem` will extend to `(i,j)` with a new remainder of `(p_rem + grid[i][j]) % k`. The same logic applies to paths from `(i,j-1)`.

```java
class Solution {
    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int MOD = 1_000_000_007;

        long[][][] dp = new long[m][n][k];

        // Base case: starting cell (0, 0)
        dp[0][0][grid[0][0] % k] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // For each previous remainder, calculate the new remainder
                // and add the paths.
                for (int rem = 0; rem < k; rem++) {
                    if (dp[i][j][rem] == 0) continue;

                    // Move down
                    if (i + 1 < m) {
                        int newRem = (rem + grid[i + 1][j]) % k;
                        dp[i + 1][j][newRem] = (dp[i + 1][j][newRem] + dp[i][j][rem]) % MOD;
                    }
                    // Move right
                    if (j + 1 < n) {
                        int newRem = (rem + grid[i][j + 1]) % k;
                        dp[i][j + 1][newRem] = (dp[i][j + 1][newRem] + dp[i][j][rem]) % MOD;
                    }
                }
            }
        }

        return (int) dp[m - 1][n - 1][0];
    }
}
```
### Algorithm
1. Create a 3D DP table `dp[m][n][k]`, where `dp[i][j][rem]` will store the number of paths from `(0,0)` to `(i,j)` with a path sum remainder of `rem`.
2. Initialize the entire `dp` table with zeros.
3. Set the base case: for the starting cell `(0,0)`, there is one path with a remainder of `grid[0][0] % k`. So, `dp[0][0][grid[0][0] % k] = 1`.
4. Iterate through the grid cells `(i, j)` from `(0,0)` to `(m-1, n-1)`.
5. For each cell `(i,j)`, iterate through all possible remainders `p_rem` from `0` to `k-1`.
6. Calculate the new remainder `new_rem = (p_rem + grid[i][j]) % k`.
7. Apply the transition (update rule):
   - Add paths from the cell above: If `i > 0`, `dp[i][j][new_rem] = (dp[i][j][new_rem] + dp[i-1][j][p_rem]) % MOD`.
   - Add paths from the cell to the left: If `j > 0`, `dp[i][j][new_rem] = (dp[i][j][new_rem] + dp[i][j-1][p_rem]) % MOD`.
8. After filling the table, the answer is the number of paths to the destination `(m-1, n-1)` with a sum remainder of 0, which is `dp[m-1][n-1][0]`.

## Space-Optimized Bottom-Up DP
This is the most efficient approach, building upon the bottom-up DP solution. We can optimize the space complexity by noticing that the calculation for any cell `(i, j)` only depends on values from the same row `i` (at column `j-1`) and the previous row `i-1` (at column `j`). Therefore, we don't need to store the entire `m x n` grid of DP states. We only need to maintain the DP states for the previous row to compute the current row.
**Time:** O(m * n * k) - The time complexity remains the same as the unoptimized DP approach, as the number of calculations is identical. · **Space:** O(n * k) - We only need to store the DP states for one row. If `m > n`, we could transpose the grid to get `O(min(m, n) * k)` space.
**Pros:** Most memory-efficient solution.; Retains the optimal time complexity of `O(m * n * k)`.
**Cons:** The implementation can be slightly more complex due to the need to manage the DP state for the current and previous rows.
### Explanation
We can reduce the space from `O(m * n * k)` to `O(n * k)` by using only two rows' worth of DP data at any time: one for the previous row and one for the current row. A common implementation uses two 2D arrays, say `prev_dp` and `curr_dp`, and alternates between them. A slightly more optimized version reuses a single 2D array `dp[n][k]`. When computing row `i`, `dp` is first used to represent row `i-1`. A temporary array for each cell's new counts is created, using values from `dp[j]` (representing row `i-1`) and `dp[j-1]` (which has already been updated to represent row `i`), and then `dp[j]` is updated.

```java
class Solution {
    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int MOD = 1_000_000_007;

        // dp[j][rem] will store path counts to cell (i, j) for the current row i.
        int[][] dp = new int[n][k];

        // Process row by row
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = grid[i][j];
                if (i == 0 && j == 0) {
                    dp[0][val % k] = 1;
                    continue;
                }

                int[] newCounts = new int[k];
                // Add paths from the cell above (from previous row's dp table)
                if (i > 0) {
                    for (int rem = 0; rem < k; rem++) {
                        int newRem = (rem + val) % k;
                        newCounts[newRem] = (newCounts[newRem] + dp[j][rem]) % MOD;
                    }
                }
                // Add paths from the cell to the left (from current row's dp table)
                if (j > 0) {
                    for (int rem = 0; rem < k; rem++) {
                        int newRem = (rem + val) % k;
                        newCounts[newRem] = (newCounts[newRem] + dp[j - 1][rem]) % MOD;
                    }
                }
                dp[j] = newCounts;
            }
        }

        return dp[n - 1][0];
    }
}
```
### Algorithm
1. Observe that to compute the DP values for the current row `i`, we only need the DP values from the previous row `i-1`.
2. Instead of a 3D table `dp[m][n][k]`, we can use a 2D table `dp[n][k]` to store the DP values for just the current row being processed.
3. Initialize `dp[n][k]` for the first row (`i=0`). `dp[0][grid[0][0]%k] = 1`. Then, for `j` from 1 to `n-1`, compute `dp[j]` based on `dp[j-1]`.
4. Iterate from the second row (`i=1`) to the last row (`m-1`).
5. In each iteration `i`, create a new temporary 2D array `next_dp[n][k]` to store the results for the current row `i`.
6. For each column `j` from `0` to `n-1`, calculate `next_dp[j]` based on the values from the previous row (`dp[j]`) and the values from the previous column in the current row (`next_dp[j-1]`).
7. The transition for `next_dp[j][new_rem]` is the sum of paths from `dp[j][rem]` (from above) and `next_dp[j-1][rem]` (from left).
8. After computing all values for the current row `i` into `next_dp`, update `dp = next_dp`.
9. After the loops complete, the answer is `dp[n-1][0]`.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int k;
private
  static final int MOD = (int)1 e9 + 7;
private
  int[][] grid;
private
  int[][][] f;
public
  int numberOfPaths(int[][] grid, int k) {
    this.grid = grid;
    this.k = k;
    m = grid.length;
    n = grid[0].length;
    f = new int[m][n][k];
    for (var a : f) {
      for (var b : a) {
        Arrays.fill(b, -1);
      }
    }
    return dfs(0, 0, 0);
  }
private
  int dfs(int i, int j, int s) {
    if (i < 0 || i >= m || j < 0 || j >= n) {
      return 0;
    }
    s = (s + grid[i][j]) % k;
    if (f[i][j][s] != -1) {
      return f[i][j][s];
    }
    if (i == m - 1 && j == n - 1) {
      return s == 0 ? 1 : 0;
    }
    int ans = dfs(i + 1, j, s) + dfs(i, j + 1, s);
    ans %= MOD;
    f[i][j][s] = ans;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfPaths(vector<vector<int>> &grid, int k) {
    int m = grid.size(), n = grid[0].size();
    int mod = 1e9 + 7;
    vector<vector<vector<int>>> f(m,
                                  vector<vector<int>>(n, vector<int>(k, -1)));
    function<int(int, int, int)> dfs;
    dfs = [&](int i, int j, int s) {
      if (i < 0 || i >= m || j < 0 || j >= n)
        return 0;
      s = (s + grid[i][j]) % k;
      if (i == m - 1 && j == n - 1)
        return s == 0 ? 1 : 0;
      if (f[i][j][s] != -1)
        return f[i][j][s];
      int ans = dfs(i + 1, j, s) + dfs(i, j + 1, s);
      ans %= mod;
      f[i][j][s] = ans;
      return ans;
    };
    return dfs(0, 0, 0);
  }
};

```

### Python

```python
class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int: @ cache def dfs(i, j, s): if i < 0 or i >= m or j < 0 or j >= n: return 0 s = (s + grid[i][j]) % k if i == m - 1 and j == n - 1: return int(s == 0) ans = dfs(i + 1, j, s) + dfs(i, j + 1, s) return ans % mod m, n = len(grid), len(grid[0]) mod = 10 ** 9 + 7 ans = dfs(0, 0, 0) dfs . cache_clear() return ans

```