Paths in Matrix Whose Sum Is Divisible by K
HardPrompt
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 <= 50
Approaches
4 approaches with complexity analysis and trade-offs.
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.
Algorithm
- 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. - 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.
- 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 modulokis 0. If it is, we have found one valid path and return 1, otherwise, we return 0. - In the recursive step, from the current cell
(row, col), we calculate the new remaindernewRem = (currentRem + grid[row][col]) % k. - 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 thenewRem. - The total number of paths from
(row, col)is the sum of the results from these two recursive calls. Remember to apply the modulo10^9 + 7to the sum of paths. - The initial call to the function will be
countPaths(0, 0, 0).
Walkthrough
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.
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); }}Complexity
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`.
Trade-offs
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.
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.
Algorithm
- 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 ofrem. - Create a 3D memoization table
memo[m][n][k]initialized with a sentinel value (e.g.,nullor-1) to store the results of computed states. - Implement a recursive function
solve(row, col, rem). - In the function, first check if the result for the state
(row, col, rem)is already in the memoization table. If so, return it. - Define the base cases:
- If
roworcolis out of bounds, return 0. - If
(row, col)is(0,0), return 1 ifgrid[0][0] % k == rem, otherwise return 0.
- If
- For the recursive step, to find the number of paths to
(row, col)with remainderrem, we need to find the number of paths to the preceding cells ((row-1, col)and(row, col-1)) with a remainderprevRemsuch that(prevRem + grid[row][col]) % k == rem. ThisprevRemcan be calculated as(rem - grid[row][col] % k + k) % k. - The result for
solve(row, col, rem)is(solve(row-1, col, prevRem) + solve(row, col-1, prevRem)) % MOD. - Store the result in
memo[row][col][rem]before returning. - The final answer is the result of
solve(m-1, n-1, 0).
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create a 3D DP table
dp[m][n][k], wheredp[i][j][rem]will store the number of paths from(0,0)to(i,j)with a path sum remainder ofrem. - Initialize the entire
dptable with zeros. - Set the base case: for the starting cell
(0,0), there is one path with a remainder ofgrid[0][0] % k. So,dp[0][0][grid[0][0] % k] = 1. - Iterate through the grid cells
(i, j)from(0,0)to(m-1, n-1). - For each cell
(i,j), iterate through all possible remaindersp_remfrom0tok-1. - Calculate the new remainder
new_rem = (p_rem + grid[i][j]) % k. - 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.
- Add paths from the cell above: If
- 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 isdp[m-1][n-1][0].
Walkthrough
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).
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]; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Observe that to compute the DP values for the current row
i, we only need the DP values from the previous rowi-1. - Instead of a 3D table
dp[m][n][k], we can use a 2D tabledp[n][k]to store the DP values for just the current row being processed. - Initialize
dp[n][k]for the first row (i=0).dp[0][grid[0][0]%k] = 1. Then, forjfrom 1 ton-1, computedp[j]based ondp[j-1]. - Iterate from the second row (
i=1) to the last row (m-1). - In each iteration
i, create a new temporary 2D arraynext_dp[n][k]to store the results for the current rowi. - For each column
jfrom0ton-1, calculatenext_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]). - The transition for
next_dp[j][new_rem]is the sum of paths fromdp[j][rem](from above) andnext_dp[j-1][rem](from left). - After computing all values for the current row
iintonext_dp, updatedp = next_dp. - After the loops complete, the answer is
dp[n-1][0].
Walkthrough
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.
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]; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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); }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.