Skip to main content
Talentd

Paths in Matrix Whose Sum Is Divisible by K - Solution & Explanation

HardArrayDynamic ProgrammingMatrix19 min readAsked at: Amazon, Microsoft, Apple +1
Practice this problem

Problem Statement

You are given a 0-indexed m x n integer matrix grid and an integer k. You are currently at position (0, 0) and you want to reach position (m - 1, n - 1) moving only down or right.

Return the number of paths where the sum of the elements on the path is divisible by k. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output: 2
Explanation: 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
Explanation: 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
Explanation: 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

Approach Overview

Problem Overview: Given an array-based grid, move from the top-left cell to the bottom-right cell using only right or down moves. Count how many paths produce a total sum divisible by k. The challenge is tracking path sums efficiently without enumerating every possible path.

Approach 1: Brute Force Path Enumeration (Exponential Time)

Explore every path from (0,0) to (m-1,n-1) using DFS. Maintain a running sum and check if the final sum is divisible by k. Since each step branches into two directions (right or down), the number of paths grows combinatorially. This results in O(2^(m+n)) time and O(m+n) recursion space. Useful only for understanding the problem structure or validating small inputs.

Approach 2: Top-Down Dynamic Programming with Memoization (O(m*n*k))

Instead of storing full sums, store only the remainder sum % k. Define a memo state dp[r][c][mod] representing the number of ways to reach cell (r,c) with remainder mod. Recursively move right and down, updating the remainder as (mod + grid[r][c]) % k. Memoization avoids recomputation of identical states. This reduces complexity to O(m*n*k) time and O(m*n*k) space. The key insight: only the remainder matters for divisibility.

Approach 3: Bottom-Up 3D Dynamic Programming (Optimal) (O(m*n*k))

This approach builds the DP table iteratively. Maintain a 3D table dp[i][j][r] where r represents the remainder of the path sum modulo k. For each cell, propagate counts from the top and left neighbors. When transitioning, compute the new remainder as (prev_r + grid[i][j]) % k. The final answer is dp[m-1][n-1][0], representing paths whose total sum is divisible by k. Time complexity is O(m*n*k) and space complexity is O(m*n*k). This method works well for dynamic programming problems on a matrix with modular state tracking.

Recommended for interviews: Interviewers expect the DP solution with modulo state compression. Brute force shows you understand the path structure, but the 3D DP demonstrates the key optimization: storing only remainders instead of full sums. Recognizing that divisibility depends solely on sum % k is the main insight.

Approach 1: Dynamic Programming with 3D DP Array

We can use dynamic programming to solve this problem by maintaining a 3D array dp where dp[i][j][mod] keeps track of the number of paths to reach the position (i, j) with a sum that when divided by k leaves a remainder mod.

Our transition will involve checking paths from the top and left cells, updating the path count for each new modulo state by adding the current cell's value.

Start by initializing dp[0][0][grid[0][0] % k] = 1 since starting at the grid's top-left corner with the initial sum modulo.

This C implementation initializes a 3D DP array to store the path counts with specific modulo sums.

Iterate over the grid, updating the DP state based on transitions from the top and left cells. The end result is found in dp[m-1][n-1][0].

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n * k) since we traverse the whole matrix for each modulo state.

Space Complexity: O(m * n * k) for the 3D DP array.

Try this approach in the editor →

Approach 2: 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 grid, respectively.

Define f[i][j][k] as the number of paths starting from (0, 0), reaching position (i, j), where the sum of elements along the path modulo K equals k. Initially, f[0][0][grid[0][0] bmod K] = 1. The final answer is f[m - 1][n - 1][0].

We can derive the state transition equation:

$ f[i][j][k] = f[i - 1][j][(k - grid[i][j])bmod K] + f[i][j - 1][(k - grid[i][j])bmod K]

To avoid issues with negative modulo operations, we can replace (k - grid[i][j])bmod K in the above equation with ((k - grid[i][j] bmod K) + K) bmod K.

The answer is f[m - 1][n - 1][0].

The time complexity is O(m times n times K) and the space complexity is O(m times n times K), where m and n are the number of rows and columns of the matrix grid, respectively, and K is the integer k$ from the problem.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with 3D DP Array

Time Complexity: O(m * n * k) since we traverse the whole matrix for each modulo state.

Space Complexity: O(m * n * k) for the 3D DP array.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force DFS PathsO(2^(m+n))O(m+n)Conceptual understanding or very small grids
Top-Down DP with MemoizationO(m*n*k)O(m*n*k)When recursion with caching is easier to implement
Bottom-Up 3D Dynamic ProgrammingO(m*n*k)O(m*n*k)Standard interview solution and most predictable performance

Video Solution

Paths in Matrix Whose Sum Is Divisible by K - Leetcode 2435 - Python • NeetCodeIO • 7,049 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Paths in Matrix Whose Sum Is Divisible by K easy or hard?
Paths in Matrix Whose Sum Is Divisible by K is classified as a Hard problem on LeetCode. The difficulty comes from combining grid path DP with modular arithmetic and managing an extra remainder dimension in the DP state.
Paths in Matrix Whose Sum Is Divisible by K Python/Java solution
Python and Java implementations typically build a 3D DP array where dp[i][j][r] represents path counts with remainder r. Each cell updates states from the top and left neighbors while applying modulo k arithmetic. The final answer is the number of paths ending at the bottom-right cell with remainder 0.
How to solve Paths in Matrix Whose Sum Is Divisible by K in O(n)?
The problem cannot be solved in strict O(n) time because every grid cell and remainder state must be processed. The optimal approach processes m*n*k states using dynamic programming. Space can be optimized using rolling arrays to reduce memory usage, but the time complexity remains O(m*n*k).
What is the best approach for Paths in Matrix Whose Sum Is Divisible by K?
The best approach uses dynamic programming with a 3D DP state tracking the remainder of the path sum modulo k. Each state dp[i][j][r] stores the number of ways to reach cell (i,j) with remainder r. Transitions come from the top and left cells while updating the remainder. This solution runs in O(m*n*k) time and O(m*n*k) space.
Is Paths in Matrix Whose Sum Is Divisible by K asked at Google/Amazon/Meta?
Grid dynamic programming problems with modular constraints frequently appear in interviews at large tech companies including Google, Amazon, and Meta. Variations involving path counting, modulo arithmetic, and DP state compression are common interview themes.
What data structure is used in Paths in Matrix Whose Sum Is Divisible by K?
The solution uses a 3D dynamic programming array or equivalent memoization structure. The DP state tracks grid position (row, column) and the current remainder modulo k. This structure efficiently aggregates counts of valid paths.
What is the time complexity of Paths in Matrix Whose Sum Is Divisible by K?
The optimal dynamic programming solution runs in O(m*n*k) time, where m and n are the grid dimensions and k is the divisor. Each cell processes k remainder states and combines transitions from two directions. Space complexity is also O(m*n*k) for the DP table.

Ready to solve this problem?

Practice Paths in Matrix Whose Sum Is Divisible by K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check if There is a Path With Equal Number of 0's And 1's

Next

Cherry Pickup