Paths in Matrix Whose Sum Is Divisible by K solution and explanation
Google
9 more videos on this problem
Paths in Matrix Whose Sum Is Divisible by K - Leetcode 2435 - PythonNeetCodeIO · 21:50 · 7K views
Paths in Matrix Whose Sum Is Divisible by K | Simplest Approaches | Leetcode 2435 | codestorywithMIKcodestorywithMIK · 25:19 · 6K views
Leetcode 2435. Paths in Matrix Whose Sum Is Divisible by K |Dynamic Programming| Weekly Contest HardCode with Alisha · 19:24 · 6K views
Weekly Contest 314 | 6203. Paths in Matrix Whose Sum Is Divisible by KcodingMohan · 14:15 · 1K views
2435. Paths in Matrix Whose Sum Is Divisible by K (Leetcode Hard)Programming Live with Larry · 19:52 · 750 views
Daily Leetcode #2066: Nov 26, 2025 - 2435. Paths in Matrix Whose Sum Is Divisible by KProgramming Live with Larry · 6:54 · 514 views
【每日一题】LeetCode 2435. Paths in Matrix Whose Sum Is Divisible by KHuifeng Guan · 15:59 · 472 views
2435 Paths in Matrix Whose Sum Is Divisible by K Leetcode Weekly Contest 314Ashutosh sharma · 8:41 · 453 views
2435. Paths in Matrix Whose Sum Is Divisible by K | Leetcode Daily - PythonLeetcode Daily · 8:58 · 231 views
Paths in Matrix Whose Sum Is Divisible by K | LeetCode 2435 - Pythonimpoldev · 16:21 · 227 views
The problem
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
Approach overview
Problem 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 1: Dynamic Programming with 3D DP Array
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.
def numberOfPaths(grid, k):
m, n = len(grid), len(grid[0])
dp = [[[0] * k for _ in range(n)] for _ in range(m)]
MOD = 10**9 + 7
dp[0][0][grid[0][0] % k] = 1
for i in range(m):
for j in range(n):
for mod in range(k):
if i > 0:
newMod = (mod + grid[i][j]) % k
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i-1][j][mod]) % MOD
if j > 0:
newMod = (mod + grid[i][j]) % k
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i][j-1][mod]) % MOD
return dp[-1][-1][0]import java.util.*;
class Solution {
public int numberOfPaths(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int MOD = 1_000_000_007;
int[][][] dp = new int[m][n][k];
dp[0][0][grid[0][0] % k] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int mod = 0; mod < k; mod++) {
if (i > 0) {
int newMod = (mod + grid[i][j]) % k;
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i - 1][j][mod]) % MOD;
}
if (j > 0) {
int newMod = (mod + grid[i][j]) % k;
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i][j - 1][mod]) % MOD;
}
}
}
}
return dp[m - 1][n - 1][0];
}
}#include <vector>
using namespace std;
class Solution {
public:
int numberOfPaths(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k, 0)));
dp[0][0][grid[0][0] % k] = 1;
int MOD = 1e9 + 7;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int mod = 0; mod < k; ++mod) {
if (i > 0) {
int newMod = (mod + grid[i][j]) % k;
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i-1][j][mod]) % MOD;
}
if (j > 0) {
int newMod = (mod + grid[i][j]) % k;
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i][j-1][mod]) % MOD;
}
}
}
}
return dp[m-1][n-1][0];
}
};var numberOfPaths = function(grid, k) {
const m = grid.length;
const n = grid[0].length;
const MOD = 1e9 + 7;
const dp = Array.from({ length: m }, () => Array.from({ length: n }, () => Array(k).fill(0)));
dp[0][0][grid[0][0] % k] = 1;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
for (let mod = 0; mod < k; mod++) {
if (i > 0) {
const newMod = (mod + grid[i][j]) % k;
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i-1][j][mod]) % MOD;
}
if (j > 0) {
const newMod = (mod + grid[i][j]) % k;
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i][j-1][mod]) % MOD;
}
}
}
}
return dp[m-1][n-1][0];
};#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int pathsWithSumDivisibleByK(int** grid, int gridSize, int* gridColSize, int k) {
int m = gridSize, n = gridColSize[0];
int dp[m][n][k];
memset(dp, 0, sizeof(dp));
dp[0][0][grid[0][0] % k] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int mod = 0; mod < k; ++mod) {
if (i > 0) {
int newMod = (mod + grid[i][j]) % k;
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i-1][j][mod]) % MOD;
}
if (j > 0) {
int newMod = (mod + grid[i][j]) % k;
dp[i][j][newMod] = (dp[i][j][newMod] + dp[i][j-1][mod]) % MOD;
}
}
}
}
return dp[m-1][n-1][0];
}using System;
public class Solution {
public int NumberOfPaths(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int MOD = 1000000007;
int[,,] dp = new int[m, n, k];
dp[0, 0, grid[0][0] % k] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int mod = 0; mod < k; mod++) {
if (i > 0) {
int newMod = (mod + grid[i][j]) % k;
dp[i, j, newMod] = (dp[i, j, newMod] + dp[i - 1, j, mod]) % MOD;
}
if (j > 0) {
int newMod = (mod + grid[i][j]) % k;
dp[i, j, newMod] = (dp[i, j, newMod] + dp[i, j - 1, mod]) % MOD;
}
}
}
}
return dp[m - 1, n - 1, 0];
}
}The Python function initializes a 3D list for tracking path counts across mod states.
Execution iteratively updates these states by considering contributions from upwards and leftwards transitions, ensuring computation for each possible modulo scenario.
Time Complexity: O(m * n * k).
Space Complexity: O(m * n * k).
Approach 2: Dynamic Programming
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.
function numberOfPaths(grid: number[][], K: number): number {
const mod = 1e9 + 7;
const m = grid.length;
const n = grid[0].length;
const f: number[][][] = Array.from({ length: m }, () =>
Array.from({ length: n }, () => Array(K).fill(0)),
);
f[0][0][grid[0][0] % K] = 1;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
for (let k = 0; k < K; ++k) {
const k0 = (k - (grid[i][j] % K) + K) % K;
if (i > 0) {
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k0]) % mod;
}
if (j > 0) {
f[i][j][k] = (f[i][j][k] + f[i][j - 1][k0]) % mod;
}
}
}
}
return f[m - 1][n - 1][0];
}func numberOfPaths(grid [][]int, K int) int {
const mod = 1e9 + 7
m, n := len(grid), len(grid[0])
f := make([][][]int, m)
for i := range f {
f[i] = make([][]int, n)
for j := range f[i] {
f[i][j] = make([]int, K)
}
}
f[0][0][grid[0][0]%K] = 1
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
for k := 0; k < K; k++ {
k0 := ((k - grid[i][j]%K) + K) % K
if i > 0 {
f[i][j][k] = (f[i][j][k] + f[i-1][j][k0]) % mod
}
if j > 0 {
f[i][j][k] = (f[i][j][k] + f[i][j-1][k0]) % mod
}
}
}
}
return f[m-1][n-1][0]
}impl Solution {
pub fn number_of_paths(grid: Vec<Vec<i32>>, K: i32) -> i32 {
const MOD: i32 = 1_000_000_007;
let m = grid.len();
let n = grid[0].len();
let K = K as usize;
let mut f = vec![vec![vec![0; K]; n]; m];
f[0][0][grid[0][0] as usize % K] = 1;
for i in 0..m {
for j in 0..n {
for k in 0..K {
let k0 = ((k + K - grid[i][j] as usize % K) % K) as usize;
if i > 0 {
f[i][j][k] = (f[i][j][k] + f[i - 1][j][k0]) % MOD;
}
if j > 0 {
f[i][j][k] = (f[i][j][k] + f[i][j - 1][k0]) % MOD;
}
}
}
}
f[m - 1][n - 1][0]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with 3D DP Array | Time Complexity: Space Complexity: |
| Dynamic Programming | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Paths in Matrix Whose Sum Is Divisible by K easy or hard?
Paths in Matrix Whose Sum Is Divisible by K is classified as a Hard problem on LeetCode. The difficulty comes from combining grid path DP with modular arithmetic and managing an extra remainder dimension in the DP state.
Paths in Matrix Whose Sum Is Divisible by K Python/Java solution
Python and Java implementations typically build a 3D DP array where dp[i][j][r] represents path counts with remainder r. Each cell updates states from the top and left neighbors while applying modulo k arithmetic. The final answer is the number of paths ending at the bottom-right cell with remainder 0.
How to solve Paths in Matrix Whose Sum Is Divisible by K in O(n)?
The problem cannot be solved in strict O(n) time because every grid cell and remainder state must be processed. The optimal approach processes m*n*k states using dynamic programming. Space can be optimized using rolling arrays to reduce memory usage, but the time complexity remains O(m*n*k).
What is the best approach for Paths in Matrix Whose Sum Is Divisible by K?
The best approach uses dynamic programming with a 3D DP state tracking the remainder of the path sum modulo k. Each state dp[i][j][r] stores the number of ways to reach cell (i,j) with remainder r. Transitions come from the top and left cells while updating the remainder. This solution runs in O(m*n*k) time and O(m*n*k) space.
Is Paths in Matrix Whose Sum Is Divisible by K asked at Google/Amazon/Meta?
Grid dynamic programming problems with modular constraints frequently appear in interviews at large tech companies including Google, Amazon, and Meta. Variations involving path counting, modulo arithmetic, and DP state compression are common interview themes.
What data structure is used in Paths in Matrix Whose Sum Is Divisible by K?
The solution uses a 3D dynamic programming array or equivalent memoization structure. The DP state tracks grid position (row, column) and the current remainder modulo k. This structure efficiently aggregates counts of valid paths.
What is the time complexity of Paths in Matrix Whose Sum Is Divisible by K?
The optimal dynamic programming solution runs in O(m*n*k) time, where m and n are the grid dimensions and k is the divisor. Each cell processes k remainder states and combines transitions from two directions. Space complexity is also O(m*n*k) for the DP table.