LeetCode 2435: Paths in Matrix Whose Sum Is Divisible by K Solution

Master LeetCode problem 2435 (Paths in Matrix Whose Sum Is Divisible by K), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2435. Paths in Matrix Whose Sum Is Divisible by K

Hard

Array Dynamic Programming Matrix

Problem Explanation

Explanation:

To solve this problem, we can utilize dynamic programming. We will maintain a 2D array dp where dp[i][j] represents the number of paths from (0,0) to (i,j) whose sum of elements is divisible by k.

We can fill up the dp array by iterating row by row and column by column. For each cell (i,j) in the grid, the number of paths to reach that cell is the sum of paths coming from the cell above (i-1, j) and the cell on the left (i, j-1).

To calculate the sum of elements along the path, we need to consider the current element in the grid as well. If the sum of elements along the path to (i,j) is divisible by k, we increment the count in dp[i][j].

Finally, the result will be stored in dp[m-1][n-1].

Time Complexity: The time complexity of this approach is O(m*n) where m and n are the dimensions of the input matrix.

Space Complexity: The space complexity is also O(m*n) for the dp array.

Solution Code

class Solution {
    public int countPaths(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        
        int[][] dp = new int[m][n];
        dp[0][0] = (grid[0][0] % k == 0) ? 1 : 0;
        
        for (int i = 1; i < m; i++) {
            dp[i][0] = (dp[i - 1][0] + grid[i][0]) % k == 0 ? 1 : 0;
        }
        
        for (int j = 1; j < n; j++) {
            dp[0][j] = (dp[0][j - 1] + grid[0][j]) % k == 0 ? 1 : 0;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % k == 0 ? 1 : 0;
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2435 (Paths in Matrix Whose Sum Is Divisible by K)?

This page provides optimized solutions for LeetCode problem 2435 (Paths in Matrix Whose Sum Is Divisible by K) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2435 (Paths in Matrix Whose Sum Is Divisible by K)?

The time complexity for LeetCode 2435 (Paths in Matrix Whose Sum Is Divisible by K) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2435 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2435 in Java, C++, or Python.

Back to LeetCode Solutions