2435. Paths in Matrix Whose Sum Is Divisible by K LeetCode Solution
In this guide, you will get 2435. Paths in Matrix Whose Sum Is Divisible by K LeetCode Solution with the best time and space complexity. The solution to Paths in Matrix Whose Sum Is Divisible by K problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Paths in Matrix Whose Sum Is Divisible by K
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.
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.length
n == grid[i].length
1 <= m, n <= 5 * 104
1 <= m * n <= 5 * 104
0 <= grid[i][j] <= 100
1 <= k <= 50
Complexity Analysis
Time Complexity: O(mnk)
Space Complexity: O(mnk)
2435. Paths in Matrix Whose Sum Is Divisible by K LeetCode Solution in C++
class Solution {
public:
int numberOfPaths(vector<vector<int>>& grid, int k) {
vector<vector<vector<int>>> mem(
grid.size(), vector<vector<int>>(grid[0].size(), vector<int>(k, -1)));
return numberOfPaths(grid, 0, 0, 0, k, mem);
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of paths to (i, j), where the sum / k == `sum`.
int numberOfPaths(const vector<vector<int>>& grid, int i, int j, int sum,
int k, vector<vector<vector<int>>>& mem) {
if (i == grid.size() || j == grid[0].size())
return 0;
if (i == grid.size() - 1 && j == grid[0].size() - 1)
return (sum + grid[i][j]) % k == 0;
if (mem[i][j][sum] != -1)
return mem[i][j][sum];
const int newSum = (sum + grid[i][j]) % k;
return mem[i][j][sum] = (numberOfPaths(grid, i + 1, j, newSum, k, mem) +
numberOfPaths(grid, i, j + 1, newSum, k, mem)) %
kMod;
}
}; /* code provided by PROGIEZ */
2435. Paths in Matrix Whose Sum Is Divisible by K LeetCode Solution in Java
class Solution {
public int numberOfPaths(int[][] grid, int k) {
Integer[][][] mem = new Integer[grid.length][grid[0].length][k];
return numberOfPaths(grid, 0, 0, 0, k, mem);
}
private static final int kMod = 1_000_000_007;
// Returns the number of paths to (i, j), where the sum / k == `sum`.
private int numberOfPaths(int[][] grid, int i, int j, int sum, int k, Integer[][][] mem) {
if (i == grid.length || j == grid[0].length)
return 0;
if (i == grid.length - 1 && j == grid[0].length - 1)
return (sum + grid[i][j]) % k == 0 ? 1 : 0;
if (mem[i][j][sum] != null)
return mem[i][j][sum];
final int newSum = (sum + grid[i][j]) % k;
return mem[i][j][sum] = (numberOfPaths(grid, i + 1, j, newSum, k, mem) +
numberOfPaths(grid, i, j + 1, newSum, k, mem)) %
kMod;
}
} // code provided by PROGIEZ
2435. Paths in Matrix Whose Sum Is Divisible by K LeetCode Solution in Python
class Solution:
def numberOfPaths(self, grid: list[list[int]], k: int) -> int:
kMod = 1_000_000_007
m = len(grid)
n = len(grid[0])
@functools.lru_cache(None)
def dp(i: int, j: int, summ: int) -> int:
"""
Returns the number of paths to (i, j), where the sum / k == `summ`.
"""
if i == m or j == n:
return 0
if i == m - 1 and j == n - 1:
return 1 if (summ + grid[i][j]) % k == 0 else 0
newSum = (summ + grid[i][j]) % k
return (dp(i + 1, j, newSum) + dp(i, j + 1, newSum)) % kMod
return dp(0, 0, 0) # code by PROGIEZ
