LeetCode Entry

2435. Paths in Matrix Whose Sum Is Divisible by K

26.11.2025 hard 2025 kotlin rust

Paths in 2D matrix %k

2435. Paths in Matrix Whose Sum Is Divisible by K hard blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1185

Problem TLDR

Paths in 2D matrix %k #hard

Intuition

Each cell hash exactly k possible remainders of all paths, so memo by [y][x][k]

Approach

• top down is just a memo+bruteforce DFS

Complexity

• Time complexity: \(O(nk)\)

• Space complexity: \(O(nk)\)

Code

// 479ms
    fun numberOfPaths(g: Array<IntArray>, k: Int): Int {
        val M = 1000000007; val dp = HashMap<Int, Int>()
        fun dfs(y: Int, x: Int, s: Int): Int =
            if (y==g.size-1&&x==g[0].size-1) {if ((g[y][x]+s)%k==0) 1 else 0}
            else if (y==g.size||x==g[0].size) 0 else
            dp.getOrPut(y*1000000+x*100+s) {
                (dfs(y+1, x, (g[y][x] + s)%k) + dfs(y, x+1, (g[y][x]+s)%k))%M
            }
        return dfs(0, 0, 0)
    }

// 29ms
    pub fn number_of_paths(g: Vec<Vec<i32>>, k: i32) -> i32 {
        let k = k as usize; let mut r = vec![vec![0; k+1]; g[0].len()+1];
        let mut n = r.clone(); r[1][0] = 1;
        for row in g {
            for x in 0..r.len()-1 { let v = row[x]as usize; for i in 0..k {
                n[x+1][(i+v)%k] = (n[x][i] + r[x+1][i])%1000000007 }}
            (r,n)=(n,r)
        }; r[r.len()-1][0]
    }