Problem Statement in English

You’re given a m x n integer matrix grid and an integer k. You can only move either down or right at any point in time.

Your task is to find the number of paths from the top-left corner to the bottom-right corner of the matrix such that the sum of the values along the path is divisible by k.

Approach

We can use dynamic programming with memoization to solve this problem. The idea is to define a recursive function dp(r, c, rem) that returns the number of paths from the cell (r, c) to the bottom-right corner such that the sum of the values along the path modulo k is equal to rem.

So along with the current position (r, c), we also keep track of the current sum modulo k (denoted as rem). At each cell, we have two choices: move down or move right. We will recursively call the dp function for both choices and accumulate the results.

Using a hashmap for the cache results in a Time Limit Exceeded (TLE) error, so we will use a 3D list for caching the results instead.

Bottom-Up Explanation

From the NeetCode video I was also able to understand the intuition behind the bottom-up approach. We basically build the solution from the bottom up rather than recursively reaching the bottom most solution and then propagating the results back up.

So essentially we iterate from the bottom-right corner, since we already know the answer to that cell. The answer to that cell is the remainder that you would need to have when you reach that cell in order to have a total sum divisible by k. So that’s this formula: (k - (grid[N - 1][M - 1] % k)) % k. The reason for the outer modulo is to handle the case when (k - (grid[N - 1][M - 1] % k)) is k, so we wrap such elements back to 0.

For each cell cell we also have k possible remainders (0 to k-1). So we iterate through those as well.


class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        N = len(grid)
        M = len(grid[0])
        MOD = 10**9 + 7

        cache = [[[0] * k for _ in range(M + 1)] for _ in range(N + 1)]
        target_remainder =  (k - (grid[N - 1][M - 1] % k)) % k
        cache[N - 1][M - 1][target_remainder] = 1

        for i in reversed(range(N)):
            for j in reversed(range(M)):
                if i == N - 1 and j == M - 1:
                    continue

                for rem in range(k):
                    
                    new_rem = (rem + grid[i][j]) % k

                    cache[i][j][rem] = (
                        (cache[i + 1][j][new_rem]) % MOD +
                        (cache[i][j + 1][new_rem]) % MOD
                    ) % MOD

        return cache[0][0][0]

This can be optimized further, since at any point we only need the current row and the next row. However, for clarity, we will stick with the 3D list approach here.

Solution in Python


class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        N = len(grid)
        M = len(grid[0])
        MOD = 10**9 + 7

        cache = [[[None] * k for _ in range(M)] for _ in range(N)]

        def dp(r, c, rem):
            if r >= N or c >= M:
                return 0

            if r == N - 1 and c == M - 1:
                return 0 if (rem + grid[r][c]) % k else 1

            if cache[r][c][rem] is not None:
                return cache[r][c][rem]

            cache[r][c][rem] = (
                dp(r + 1, c, (rem + grid[r][c]) % k) % MOD
                + dp(r, c + 1, (rem + grid[r][c]) % k) % MOD
            ) % MOD

            return cache[r][c][rem]

        return dp(0, 0, 0)

Complexity

  • Time: $O(N \times M \times k)$
    Since we are calculating the result for each cell in the grid for each possible remainder when divided by k.

  • Space: $O(N \times M \times k)$
    Since we are calculating the result for each cell in the grid for each possible remainder when divided by k.

Mistakes I Made

I had to watch NeetCode’s video solution for this.

And we are done.