#2435

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Paths in Matrix Whose Sum Is Divisible by K

Compute all paths in a matrix where the sum of elements is divisible by k using state transition dynamic programming efficiently.

array dynamic programming matrix

Problem Statement

You are given an m x n integer matrix grid and an integer k. Starting from the top-left cell (0,0), move only down or right to reach the bottom-right cell (m-1,n-1). Each path accumulates the sum of its elements.

Return the total number of paths where the sum of elements along the path is divisible by k. Since the result can be large, return it modulo 10^9 + 7. For example, given grid = [[5,2,4],[3,0,5],[0,7,2]] and k = 3, there are two valid paths with sums divisible by 3.

Examples

Example 1

Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3

Output: 2

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

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

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

Solution Approach

Define DP State

Create a 3D DP array dp[i][j][r] representing the number of paths to cell (i,j) with sum modulo k equal to r. Initialize dp[0][0][grid[0][0] % k] = 1.

State Transition

For each cell, combine paths from the top and left neighbors. Update dp[i][j][(r + grid[i][j]) % k] by adding counts from dp[i-1][j][r] and dp[i][j-1][r]. This tracks all remainder combinations efficiently.

Return Result

After filling the DP table, return dp[m-1][n-1][0] modulo 10^9 + 7. This represents all paths where the total sum is divisible by k.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m * n * k) since each of the m*n cells updates k remainders. Space complexity is O(m * n * k), which can be optimized to O(n * k) by reusing rows.

What Interviewers Usually Probe

Are you tracking the remainder sums rather than absolute sums to avoid overflow?
Can you optimize space by reducing one dimension in the DP array?
How do you handle combining paths from both top and left neighbors for all remainders?

Common Pitfalls or Variants

Common pitfalls

Forgetting to take modulo k at each step leads to incorrect remainder tracking.
Ignoring the modulo 10^9 + 7 for the final result can cause integer overflow.
Not correctly initializing the starting cell's remainder can miss valid paths.

Follow-up variants

Counting paths where the product of elements modulo k equals zero instead of sum.
Allowing diagonal moves and updating the DP state accordingly.
Finding maximum or minimum sum paths divisible by k rather than counting them.

FAQ

What is the main DP pattern used in Paths in Matrix Whose Sum Is Divisible by K?

The problem uses state transition dynamic programming where the DP state tracks remainders modulo k at each cell.

Can I reduce space complexity in this problem?

Yes, you can optimize from O(m n k) to O(n*k) by keeping only the current and previous row of the DP table.

Why do we track remainders instead of the sum?

Tracking remainders avoids large numbers and ensures correctness for checking divisibility by k at each step.

How do we handle the modulo 10^9 + 7 requirement?

Apply modulo 10^9 + 7 after each addition to prevent integer overflow in the DP counts.

Does the actual value of grid elements matter for the DP pattern?

No, only the remainder of each element modulo k matters for state transitions and counting valid paths.

terminal

Solution

Solution 1: 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 $\textit{grid}$, respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def numberOfPaths(self, grid: List[List[int]], K: int) -> int:
        mod = 10**9 + 7
        m, n = len(grid), len(grid[0])
        f = [[[0] * K for _ in range(n)] for _ in range(m)]
        f[0][0][grid[0][0] % K] = 1
        for i in range(m):
            for j in range(n):
                for k in range(K):
                    k0 = ((k - grid[i][j] % K) + K) % K
                    if i:
                        f[i][j][k] += f[i - 1][j][k0]
                    if j:
                        f[i][j][k] += f[i][j - 1][k0]
                    f[i][j][k] %= mod
        return f[m - 1][n - 1][0]

Continue Practicing

#2328 number of increasing paths in a grid #2556 disconnect path in a binary matrix by at most one flip #2304 minimum path cost in a grid