Paths in Matrix Whose Sum Is Divisible by K

Hard
1050.

Paths in Matrix Whose Sum Is Divisible by K

Paths in Matrix Whose Sum Is Divisible by K is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Microsoft interviews.

Starting at the top-left cell and moving only right or down, reach the bottom-right cell. A path's value is the sum of the cells it visits, start and end included.

Return the number of paths whose value is divisible by k, modulo 10⁹ + 7.

Example 1

Input
grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output
2
Explanation
Two of the six paths sum to a multiple of 3.

Example 2

Input
grid = [[0,0]], k = 5
Output
1
Explanation
The single path sums to 0, which is divisible by anything.

Example 3

Input
grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
Output
10
Explanation
Every sum is divisible by 1, so all ten paths count.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 5 * 10^4
  • 1 <= m * n <= 5 * 10^4
  • 0 <= grid[i][j] <= 100
  • 1 <= k <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var numberOfPaths = function(grid, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Paths in Matrix Whose Sum Is Divisible by K — Solution

Paths in Matrix Whose Sum Is Divisible by K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Paths in Matrix Whose Sum Is Divisible by K is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Microsoft interviews.

Problem statement

Starting at the top-left cell and moving only right or down, reach the bottom-right cell. A path's value is the sum of the cells it visits, start and end included.

Return the number of paths whose value is divisible by k, modulo 10⁹ + 7.

Example 1

Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output: 2
Explanation: Two of the six paths sum to a multiple of 3.

Example 2

Input: grid = [[0,0]], k = 5
Output: 1
Explanation: The single path sums to 0, which is divisible by anything.

Example 3

Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
Output: 10
Explanation: Every sum is divisible by 1, so all ten paths count.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 5 * 10^4
  • 1 <= m * n <= 5 * 10^4
  • 0 <= grid[i][j] <= 100
  • 1 <= k <= 50

Hints for Paths in Matrix Whose Sum Is Divisible by K

  1. Hint 1

    You cannot enumerate paths — there are exponentially many. Count them by the remainder they carry.

  2. Hint 2

    dp[i][j][r] = the number of paths reaching (i, j) whose partial sum is r modulo k.

  3. Hint 3

    A path arriving with remainder r at (i, j) came from a neighbour with remainder (r - grid[i][j]) mod k.

How to solve Paths in Matrix Whose Sum Is Divisible by K

Add the remainder to the DP state. dp[i][j][r] counts the paths to (i, j) whose sum leaves remainder r. Each cell pulls from the cell above and the cell to the left, shifting the remainder back by the cell's own value.

Approach

  1. Initialise dp[0][0][grid[0][0] mod k] = 1.
  2. Sweep in row-major order. For each cell and each target remainder r, the contributing remainder upstream is ((r - grid[i][j]) mod k + k) mod k.
  3. Sum the contributions from above and from the left, modulo 10⁹ + 7.
  4. Return dp[m-1][n-1][0].

Why it works

Remainders are the only thing about a partial sum that can still matter, so folding the sum into k buckets is lossless and turns an exponential path count into O(m · n · k) states. The double modulo on r - grid[i][j] is not decoration: in most languages the % of a negative number is negative, which would index out of the array.

Complexity

  • Time — O(m · n · k)
  • Space — O(m · n · k), reducible to O(n · k) with a rolling row

Pitfalls

  • A negative intermediate remainder must be normalised before it indexes the table.
  • The starting cell's own value counts towards the sum.
  • k = 1 makes every path count — a useful sanity check on the indexing.

Reference solution

Python

from typing import List

def numberOfPaths(grid: List[List[int]], k: int) -> int:
    MOD = 10**9 + 7
    m, n = len(grid), len(grid[0])
    dp = [[[0] * k for _ in range(n)] for _ in range(m)]
    dp[0][0][grid[0][0] % k] = 1
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            v = grid[i][j] % k
            for r in range(k):
                prev = (r - v) % k
                total = 0
                if i > 0:
                    total += dp[i - 1][j][prev]
                if j > 0:
                    total += dp[i][j - 1][prev]
                dp[i][j][r] = total % MOD
    return dp[m - 1][n - 1][0]

Java

public static int numberOfPaths(int[][] grid, int k) {
    final int MOD = 1000000007;
    int m = grid.length, n = grid[0].length;
    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++) {
            if (i == 0 && j == 0) continue;
            int v = grid[i][j] % k;
            for (int r = 0; r < k; r++) {
                int prev = ((r - v) % k + k) % k;
                long total = 0;
                if (i > 0) total += dp[i - 1][j][prev];
                if (j > 0) total += dp[i][j - 1][prev];
                dp[i][j][r] = (int) (total % MOD);
            }
        }
    }
    return dp[m - 1][n - 1][0];
}

C++

int numberOfPaths(vector<vector<int>>& grid, int k) {
    const int MOD = 1000000007;
    int m = (int) grid.size(), n = (int) 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;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            int v = grid[i][j] % k;
            for (int r = 0; r < k; r++) {
                int prev = ((r - v) % k + k) % k;
                long long total = 0;
                if (i > 0) total += dp[i - 1][j][prev];
                if (j > 0) total += dp[i][j - 1][prev];
                dp[i][j][r] = (int) (total % MOD);
            }
        }
    }
    return dp[m - 1][n - 1][0];
}

JavaScript

var numberOfPaths = function(grid, k) {
    var MOD = 1000000007;
    var m = grid.length, n = grid[0].length, i, j, r;
    var dp = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) {
            var cell = [];
            for (r = 0; r < k; r++) cell.push(0);
            row.push(cell);
        }
        dp.push(row);
    }
    dp[0][0][grid[0][0] % k] = 1;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (i === 0 && j === 0) continue;
            var v = grid[i][j] % k;
            for (r = 0; r < k; r++) {
                var prev = ((r - v) % k + k) % k;
                var total = 0;
                if (i > 0) total += dp[i - 1][j][prev];
                if (j > 0) total += dp[i][j - 1][prev];
                dp[i][j][r] = total % MOD;
            }
        }
    }
    return dp[m - 1][n - 1][0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming