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.
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; }}Video 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.