2435. Paths in Matrix Whose Sum Is Divisible by K


Problem Description

In this LeetCode problem, we have a two-dimensional grid representing a matrix with m rows and n columns, and we are tasked with finding paths from the top left corner (0, 0) to the bottom right corner (m - 1, n - 1). The only permitted movements are either right or down. Each cell in the grid contains an integer, and we want to consider only those paths for which the sum of the integers along the path is divisible by a given integer k.

The problem statement asks us to return the total number of such paths modulo 10^9 + 7. This large number is used to prevent overflow issues due to very large result values, which is a common practice in computational problems.

Intuition

To arrive at the solution, we have to think in terms of dynamic programming, which is a method for solving problems by breaking them down into simpler subproblems. The main idea behind the approach is to create a 3-dimensional array dp where each element dp[i][j][s] represents the number of ways to reach cell (i, j) such that the sum of all elements in the path modulo k is s.

Here's how we can think through it:

  1. Initialize a 3-dimensional array dp of size m x n x k with zeroes, which will store the count of paths that lead to a certain remainder when the sum of path elements is divided by k. The third dimension s represents all possible remainders [0, k-1].

  2. Set dp[0][0][grid[0][0] % k] to 1 as a base case since there's one way to be at the starting cell with the sum equal to the element of that cell modulo k.

  3. Start iterating over the grid, cell by cell. At each cell, we want to update the dp array for all possible sums modulo k. We consider two possibilities to arrive at a cell (i, j): from the cell above (i - 1, j) and from the cell to the left (i, j - 1). For each of these cells, we add to the path count for the current remainder s.

  4. We calculate the new remainder t after including the current cell's value using the formula t = ((s - grid[i][j] % k) + k) % k. This gives us the remainder from the previous cell that would lead to a current remainder s after adding grid[i][j].

  5. If the cell above (i - 1, j) is valid, we add the number of ways to reach it with the remainder t to dp[i][j][s]. If the cell to the left (i, j - 1) is valid, we do the same.

  6. Since we only care about the counts modulo 10^9 + 7, we take the modulo at each update step to keep numbers in the range.

  7. Finally, we're interested in the number of paths that have a sum divisible by k when we've reached the bottom-right cell. This corresponds to dp[m - 1][n - 1][0], the number of paths with a remainder of 0, which we return as the answer.

By following these steps, we can fill up our dp table and compute the required value efficiently, avoiding the need to explicitly enumerate all possible paths, which would be impractical for large grids.

Solution Approach

The implementation utilizes dynamic programming to efficiently compute the number of paths that lead to the bottom-right corner of the grid with sums divisible by k:

  1. Initialization: We initialize a 3D list, dp, of size m * n * k, where m is the number of rows and n is the number of columns in the grid. This array will store the count of paths for each possible sum modulo k (s ranges from 0 to k-1) for each cell. Initially, all elements are set to 0.

  2. Base Case: The path count of the starting position (0, 0) is set such that dp[0][0][grid[0][0] % k] is 1, because there is only one way to be at the starting cell and the sum equals the element in the starting cell modulo k.

    1dp[0][0][grid[0][0] % k] = 1
  3. Main Logic: We iterate through each cell (i, j) in the grid, and for each cell, we iterate through all possible remainders s (from 0 to k-1). We update dp[i][j][s] by adding the number of ways to reach either the cell above (i - 1, j) or the cell to the left (i, j - 1) that would result in a remainder s after adding the value of the current cell.

    The transition formula used is:

    1t = ((s - grid[i][j] % k) + k) % k
    2if i:
    3    dp[i][j][s] += dp[i - 1][j][t]
    4if j:
    5    dp[i][j][s] += dp[i][j - 1][t]

    For each dp update, we take the modulo operation to ensure the result stays within the required range:

    1dp[i][j][s] %= mod
  4. Final Result: The number of paths where the sum of the elements is divisible by k is the last cell's value dp[m - 1][n - 1][0], since we are interested in paths with a sum that has a remainder of 0 after modulo division by k.

    1return dp[-1][-1][0]

By following this approach, we can compute the number of valid paths without visiting all possible paths, which would be computationally expensive especially on larger grids. This solution leverages the property of modulo operation and the principle of dynamic programming, specifically memoization, to store intermediate results and avoid repetitive work. The modular arithmetic ensures that we handle large numbers efficiently and prevent arithmetic overflow, which is a common issue in problems involving counting and combinatorics on a large scale.

Example Walkthrough

Let's illustrate the dynamic programming approach with a small example. Consider a 2x3 grid with the following values:

1[
2  [1, 1, 2],
3  [2, 3, 4]
4]

And let k = 3. We want to find all the paths from the top left corner to the bottom right with sums divisible by k.

  1. Initialization: We first set up a 3D array dp of size 2x3x3 (since m = 2, n = 3, and k = 3). We initialize all elements to 0.

  2. Base case: For the starting cell (0, 0) with the value 1, we set dp[0][0][1 % 3] = dp[0][0][1] = 1. There is one way to be at (0, 0) with a sum that modulo k is 1.

  3. Main logic:

    • Starting with cell (0, 1) with the value 1, the remainder s will be ((1 + 1) % 3) = 2. Since we can only arrive from the left, we will update dp[0][1][2] to 1.

    • Now for cell (0, 2) with the value 2, s will be ((2 + 2) % 3) = 1. Update dp[0][2][1] to 1 as we can only arrive from the left.

    • For cell (1, 0) with the value 2, s will be ((1 + 2) % 3) = 0. Update dp[1][0][0] to 1 since we can only arrive from above.

    • At cell (1, 1) with the value 3, we check from above (0, 1) and left (1, 0). From above, t = ((s - 3 % 3) + 3) % 3 = s, we add dp[0][1][t] = dp[0][1][s] to dp[1][1][s]. We will do the same for the left cell (1, 0). Hence, dp[1][1][0] will be updated to 2 (1 from above, 1 from the left).

    • Lastly, for cell (1, 2) with the value 4, the remainder s will be ((0 + 4) % 3) = 1. Update dp[1][2][1] by adding counts from above (1, 1) with value dp[1][1][t] where t = ((1 - 4 % 3) + 3) % 3 = 0, and from the left (1, 2) with value dp[1][1][1]. Thus, dp[1][2][1] will increase by 2 (all from above, nothing from the left, as dp[1][1][1] is 0).

  4. Final result: We look at dp[1][2][0], but in our case, the number of paths that end with a sum divisible by k is stored in dp[1][2][1]. Since the bottom right cell ((1, 2)) has a sum remainder s = 1, not 0, there are no paths that sum up to a number divisible by k, and the method would return 0.

Using this approach, we managed to calculate the required paths without exhaustively iterating through all paths. We used a combination of iterative updates based on previous states and modular arithmetic to maintain efficiency and correctness.

Python Solution

1class Solution:
2    def numberOfPaths(self, grid, k):
3        # Obtain the dimensions of the grid
4        num_rows, num_cols = len(grid), len(grid[0])
5      
6        # Initialize a dynamic programming table to hold counts of paths 
7        # with different remainders modulo k at each cell
8        # dp[row][col][remainder] will store the number of ways to reach 
9        # cell (row, col) such that the path sum has a remainder of `remainder` when divided by k
10        dp = [[[0] * k for _ in range(num_cols)] for _ in range(num_rows)]
11        # Set the initial case for the starting cell (top-left corner)
12        dp[0][0][grid[0][0] % k] = 1
13
14        # Define the modulo operation base
15        mod_base = 10**9 + 7
16      
17        # Iterate through each cell in the grid
18        for row in range(num_rows):
19            for col in range(num_cols):
20                # For each cell, iterate through all possible remainders
21                for remainder in range(k):
22                    # Compute the adjusted remainder to update the paths count
23                    adjusted_remainder = ((remainder - grid[row][col] % k) + k) % k
24                    # If there is a row above the current cell, add the number of paths from the cell above
25                    if row:
26                        dp[row][col][remainder] += dp[row - 1][col][adjusted_remainder]
27                    # If there is a column to the left of the current cell, add the number of paths from the cell to the left
28                    if col:
29                        dp[row][col][remainder] += dp[row][col - 1][adjusted_remainder]
30                    # Apply modulo operation to avoid large integers
31                    dp[row][col][remainder] %= mod_base
32      
33        # Return the result, which is the number of paths that lead to the bottom-right corner of the grid
34        # with a path sum divisible by k (remainder 0)
35        return dp[-1][-1][0] # dp[num_rows - 1][num_cols - 1][0] in non-Pythonic indexing
36

Java Solution

1class Solution {
2    // Define the modulus constant for preventing integer overflow
3    private static final int MOD = (int) 1e9 + 7;
4
5    public int numberOfPaths(int[][] grid, int k) {
6        // m and n represent the dimensions of the grid
7        int numRows = grid.length;
8        int numCols = grid[0].length;
9      
10        // 3D dp array to store the number of ways to reach a cell (i, j) 
11        // such that the path sum modulo k is s
12        int[][][] dp = new int[numRows][numCols][k];
13      
14        // Base case: start at the top-left corner of the grid
15        dp[0][0][grid[0][0] % k] = 1;
16      
17        // Iterate over all cells of the grid
18        for (int i = 0; i < numRows; ++i) {
19            for (int j = 0; j < numCols; ++j) {
20                // Try all possible sums modulo k
21                for (int sumModK = 0; sumModK < k; ++sumModK) {
22                    // Calculate the modulo to identify how the current value of grid contributes to the new sum
23                    int remainder = ((sumModK - grid[i][j] % k) + k) % k;
24                  
25                    // If not in the first row, add paths from the cell above
26                    if (i > 0) {
27                        dp[i][j][sumModK] += dp[i - 1][j][remainder];
28                    }
29                    // If not in the first column, add paths from the cell on the left
30                    if (j > 0) {
31                        dp[i][j][sumModK] += dp[i][j - 1][remainder];
32                    }
33                  
34                    // Use modulus operation to prevent integer overflow
35                    dp[i][j][sumModK] %= MOD;
36                }
37            }
38        }
39      
40        // The result is the number of ways to reach the bottom-right corner such that path sum modulo k is 0
41        return dp[numRows - 1][numCols - 1][0];
42    }
43}
44

C++ Solution

1#include <vector>
2#include <functional>
3using namespace std;
4
5class Solution {
6public:
7    int numberOfPaths(vector<vector<int>>& grid, int k) {
8        // Dimensions of the grid
9        int m = grid.size(), n = grid[0].size();
10        // Modulo value to prevent overflow
11        const int MOD = 1e9 + 7;
12      
13        // A 3D vector to store the number of paths, with the third dimension representing the sum modulo k
14        vector<vector<vector<int>>> memo(m, vector<vector<int>>(n, vector<int>(k, -1)));
15      
16        // Define the depth-first search function using std::function for recursion
17        function<int(int, int, int)> dfs = [&](int row, int col, int sum) {
18            // Base case: outside of the grid bounds, return 0
19            if (row < 0 || row >= m || col < 0 || col >= n) return 0;
20          
21            // Add the current cell's value to the running sum and apply modulo k
22            sum = (sum + grid[row][col]) % k;
23          
24            // If we reached the bottom-right cell, return 1 if sum modulo k is 0, otherwise return 0
25            if (row == m - 1 && col == n - 1) {
26                return sum == 0 ? 1 : 0;
27            }
28          
29            // Check if this state has already been computed
30            if (memo[row][col][sum] != -1) {
31                return memo[row][col][sum];
32            }
33          
34            // Recurse to the right cell and the bottom cell and sum their path counts
35            int pathCount = dfs(row + 1, col, sum) + dfs(row, col + 1, sum);
36            // Apply modulo operations to prevent overflow
37            pathCount %= MOD;
38          
39            // Cache the result in the memoization table
40            memo[row][col][sum] = pathCount;
41
42            // Return the total number of paths from this cell
43            return pathCount;
44        };
45      
46        // Call the DFS function starting from the top-left cell of the grid with an initial sum of 0
47        return dfs(0, 0, 0);
48    }
49};
50

Typescript Solution

1function numberOfPaths(grid: number[][], k: number): number {
2    // Define the modulo constant for the final answer
3    const MOD = 10 ** 9 + 7;
4
5    // Get the dimensions of the grid
6    const numRows = grid.length;
7    const numCols = grid[0].length;
8
9    // Initialize a 3D array to store the number of ways to reach a cell
10    // such that the sum of values mod k is a certain remainder
11    let paths = Array.from({ length: numRows + 1 }, () =>
12        Array.from({ length: numCols + 1 }, () => new Array(k).fill(0)),
13    );
14
15    // There is one way to reach the starting position (0,0) with a sum of 0 (mod k)
16    paths[0][1][0] = 1;
17
18    // Iterate over all cells in the grid
19    for (let row = 0; row < numRows; row++) {
20        for (let col = 0; col < numCols; col++) {
21            // Iterate over all possible remainders
22            for (let remainder = 0; remainder < k; remainder++) {
23                // Compute the next key as the sum of the current cell's value and the previous remainder, mod k
24                let newRemainder = (grid[row][col] + remainder) % k;
25
26                // Update the number of ways to reach the current cell such that the sum of values mod k
27                // is the new remainder. Take into account paths from the top and from the left.
28                // Ensure the sum is within the MOD range
29                paths[row + 1][col + 1][newRemainder] =
30                    (paths[row][col + 1][remainder] + paths[row + 1][col][remainder] + paths[row + 1][col + 1][newRemainder]) % MOD;
31            }
32        }
33    }
34
35    // The answer is the number of ways to reach the bottom-right corner
36    // such that the total sum mod k is 0
37    return paths[numRows][numCols][0];
38}
39

Time and Space Complexity

The provided Python code defines a method to calculate the number of paths on a 2D grid where the sum of the values along the path is divisible by k. It uses dynamic programming to store the counts for intermediate paths where the sum of the values modulo k is a specific remainder.

Time Complexity:

The time complexity of the given code can be analyzed by considering the three nested loops:

  1. The outermost loop runs for m iterations, where m is the number of rows in the grid.
  2. The middle loop runs for n iterations for each i, where n is the number of columns in the grid.
  3. The innermost loop runs for k iterations for each combination of i and j.

Combining these, we get m * n * k iterations in total. Within the innermost loop, all operations are constant time. Hence, the time complexity is O(m * n * k).

Space Complexity:

The space complexity is determined by the size of the dp array, which stores intermediate counts for each cell and each possible remainder modulo k:

  • The dp array is a 3-dimensional array with dimensions m, n, and k.
  • This results in a space requirement for m * n * k integers.

Hence, the space complexity of the code is also O(m * n * k).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫