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:
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:
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:
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.lengthn == grid[i].length1 <= m, n <= 5 * 1041 <= m * n <= 5 * 1040 <= grid[i][j] <= 1001 <= k <= 50Problem Overview: Given an array-based grid, move from the top-left cell to the bottom-right cell using only right or down moves. Count how many paths produce a total sum divisible by k. The challenge is tracking path sums efficiently without enumerating every possible path.
Approach 1: Brute Force Path Enumeration (Exponential Time)
Explore every path from (0,0) to (m-1,n-1) using DFS. Maintain a running sum and check if the final sum is divisible by k. Since each step branches into two directions (right or down), the number of paths grows combinatorially. This results in O(2^(m+n)) time and O(m+n) recursion space. Useful only for understanding the problem structure or validating small inputs.
Approach 2: Top-Down Dynamic Programming with Memoization (O(m*n*k))
Instead of storing full sums, store only the remainder sum % k. Define a memo state dp[r][c][mod] representing the number of ways to reach cell (r,c) with remainder mod. Recursively move right and down, updating the remainder as (mod + grid[r][c]) % k. Memoization avoids recomputation of identical states. This reduces complexity to O(m*n*k) time and O(m*n*k) space. The key insight: only the remainder matters for divisibility.
Approach 3: Bottom-Up 3D Dynamic Programming (Optimal) (O(m*n*k))
This approach builds the DP table iteratively. Maintain a 3D table dp[i][j][r] where r represents the remainder of the path sum modulo k. For each cell, propagate counts from the top and left neighbors. When transitioning, compute the new remainder as (prev_r + grid[i][j]) % k. The final answer is dp[m-1][n-1][0], representing paths whose total sum is divisible by k. Time complexity is O(m*n*k) and space complexity is O(m*n*k). This method works well for dynamic programming problems on a matrix with modular state tracking.
Recommended for interviews: Interviewers expect the DP solution with modulo state compression. Brute force shows you understand the path structure, but the 3D DP demonstrates the key optimization: storing only remainders instead of full sums. Recognizing that divisibility depends solely on sum % k is the main insight.
We can use dynamic programming to solve this problem by maintaining a 3D array dp where dp[i][j][mod] keeps track of the number of paths to reach the position (i, j) with a sum that when divided by k leaves a remainder mod.
Our transition will involve checking paths from the top and left cells, updating the path count for each new modulo state by adding the current cell's value.
Start by initializing dp[0][0][grid[0][0] % k] = 1 since starting at the grid's top-left corner with the initial sum modulo.
This C implementation initializes a 3D DP array to store the path counts with specific modulo sums.
Iterate over the grid, updating the DP state based on transitions from the top and left cells. The end result is found in dp[m-1][n-1][0].
Time Complexity: O(m * n * k) since we traverse the whole matrix for each modulo state.
Space Complexity: O(m * n * k) for the 3D DP array.
We denote the k in the problem as K, and let m and n be the number of rows and columns of the matrix grid, respectively.
Define f[i][j][k] as the number of paths starting from (0, 0), reaching position (i, j), where the sum of elements along the path modulo K equals k. Initially, f[0][0][grid[0][0] bmod K] = 1. The final answer is f[m - 1][n - 1][0].
We can derive the state transition equation:
$
f[i][j][k] = f[i - 1][j][(k - grid[i][j])bmod K] + f[i][j - 1][(k - grid[i][j])bmod K]
To avoid issues with negative modulo operations, we can replace (k - grid[i][j])bmod K in the above equation with ((k - grid[i][j] bmod K) + K) bmod K.
The answer is f[m - 1][n - 1][0].
The time complexity is O(m times n times K) and the space complexity is O(m times n times K), where m and n are the number of rows and columns of the matrix grid, respectively, and K is the integer k$ from the problem.
| Approach | Complexity |
|---|---|
| Dynamic Programming with 3D DP Array | Time Complexity: Space Complexity: |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS Paths | O(2^(m+n)) | O(m+n) | Conceptual understanding or very small grids |
| Top-Down DP with Memoization | O(m*n*k) | O(m*n*k) | When recursion with caching is easier to implement |
| Bottom-Up 3D Dynamic Programming | O(m*n*k) | O(m*n*k) | Standard interview solution and most predictable performance |
Paths in Matrix Whose Sum Is Divisible by K - Leetcode 2435 - Python • NeetCodeIO • 6,773 views views
Watch 9 more video solutions →Practice Paths in Matrix Whose Sum Is Divisible by K with our built-in code editor and test cases.
Practice on FleetCode