LeetCode 1594: Maximum Non Negative Product in a Matrix Solution

Master LeetCode problem 1594 (Maximum Non Negative Product in a Matrix), a medium 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.

1594. Maximum Non Negative Product in a Matrix

Medium

Array Dynamic Programming Matrix

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will maintain two arrays to keep track of the maximum positive product and the minimum negative product that can be obtained at each cell. At each cell, we update these values based on the values obtained from moving either from the cell above or the cell to the left.

Initialize two 2D arrays maxProd and minProd of size m x n to store the maximum positive product and the minimum negative product.
Initialize maxProd[0][0] = minProd[0][0] = grid[0][0].
Iterate through the matrix starting from (0, 1) and (1, 0).
Update maxProd[i][j] and minProd[i][j] based on the values from the cell above and the cell to the left.
Return the maximum non-negative product modulo 10^9 + 7.

Time complexity: O(m * n) Space complexity: O(m * n)

Solution Code

class Solution {
    public int maxProductPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        long[][] maxProd = new long[m][n];
        long[][] minProd = new long[m][n];
        
        maxProd[0][0] = minProd[0][0] = grid[0][0];
        
        // Fill the first row
        for (int j = 1; j < n; j++) {
            maxProd[0][j] = minProd[0][j] = maxProd[0][j - 1] * grid[0][j];
        }
        
        // Fill the first column
        for (int i = 1; i < m; i++) {
            maxProd[i][0] = minProd[i][0] = maxProd[i - 1][0] * grid[i][0];
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (grid[i][j] >= 0) {
                    maxProd[i][j] = Math.max(maxProd[i - 1][j], maxProd[i][j - 1]) * grid[i][j];
                    minProd[i][j] = Math.min(minProd[i - 1][j], minProd[i][j - 1]) * grid[i][j];
                } else {
                    maxProd[i][j] = Math.min(minProd[i - 1][j], minProd[i][j - 1]) * grid[i][j];
                    minProd[i][j] = Math.max(maxProd[i - 1][j], maxProd[i][j - 1]) * grid[i][j];
                }
            }
        }
        
        long result = maxProd[m - 1][n - 1] % 1000000007;
        return result < 0 ? -1 : (int)result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1594 (Maximum Non Negative Product in a Matrix)?

This page provides optimized solutions for LeetCode problem 1594 (Maximum Non Negative Product in a Matrix) 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 1594 (Maximum Non Negative Product in a Matrix)?

The time complexity for LeetCode 1594 (Maximum Non Negative Product in a Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1594 on DevExCode?

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

Back to LeetCode Solutions