Leetcode: 2435. Paths in Matrix Whose Sum Is Divisible by K

Problem Statement

Understand the problem

Count the number of paths from \((0,0)\) to \((n-1,m-1)\) (on Directed Acyclic Graph) where the path goes down-right and has sum module \(k\).

Devise a plan

Modeling as a graph problem, a cell connected to the one directly to the left and top. So, this is an Directed Acyclic Graph and we can compute the number of paths using Dynamic Programming. For each cell and each \(0 \leq x < k\), store the number of paths that reached that cell such that sum of the paths is \(x\) module \(k\). Time complexity is \(O(n \times m \times k)\) and space is \(O(n \times m \times k)\).

Carry out the plan

class Solution:
    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
        MOD = 10**9 + 7
        N = len(grid)
        M = len(grid[0])
        dp = [[Counter() for _ in range(M)] for _ in range(N)]
        dp[0][0] = Counter([grid[0][0] % k])
        for i in range(N):
            for j in range(M):
                if i == 0 and j == 0:
                    continue
                t = Counter() if i == 0 else dp[i - 1][j]
                l = Counter() if j == 0 else dp[i][j - 1]
                for x, c in (t + l).items():
                    dp[i][j][(x + grid[i][j]) % k] = (
                        dp[i][j][(x + grid[i][j]) % k] + c
                    ) % MOD
        return dp[N - 1][M - 1][0]