Watch 10 video solutions for Paths in Matrix Whose Sum Is Divisible by K, a hard level problem involving Array, Dynamic Programming, Matrix. This walkthrough by NeetCodeIO has 6,773 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |