1594. Maximum Non Negative Product in a Matrix LeetCode Solution

In this guide, you will get 1594. Maximum Non Negative Product in a Matrix LeetCode Solution with the best time and space complexity. The solution to Maximum Non Negative Product in a Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Non Negative Product in a Matrix solution in C++
Maximum Non Negative Product in a Matrix solution in Java
Maximum Non Negative Product in a Matrix solution in Python
Additional Resources

1594. Maximum Non Negative Product in a Matrix LeetCode Solution image

Problem Statement of Maximum Non Negative Product in a Matrix

You are given a m x n matrix grid. Initially, you are located at the top-left corner (0, 0), and in each step, you can only move right or down in the matrix.
Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right corner (m – 1, n – 1), find the path with the maximum non-negative product. The product of a path is the product of all integers in the grid cells visited along the path.
Return the maximum non-negative product modulo 109 + 7. If the maximum product is negative, return -1.
Notice that the modulo is performed after getting the maximum product.

Example 1:

Input: grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
Output: -1
Explanation: It is not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.

Example 2:

Input: grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
Output: 8
Explanation: Maximum non-negative product is shown (1 * 1 * -2 * -4 * 1 = 8).

Example 3:

Input: grid = [[1,3],[0,-4]]
Output: 0
Explanation: Maximum non-negative product is shown (1 * 0 * -4 = 0).

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 15
-4 <= grid[i][j] <= 4

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

1594. Maximum Non Negative Product in a Matrix LeetCode Solution in C++

class Solution {
 public:
  int maxProductPath(vector<vector<int>>& grid) {
    constexpr int kMod = 1'000'000'007;
    const int m = grid.size();
    const int n = grid[0].size();
    // dpMin[i][j] := the minimum product from (0, 0) to (i, j)
    // dpMax[i][j] := the maximum product from (0, 0) to (i, j)
    vector<vector<long>> dpMin(m, vector<long>(n));
    vector<vector<long>> dpMax(m, vector<long>(n));

    dpMin[0][0] = dpMax[0][0] = grid[0][0];

    for (int i = 1; i < m; ++i)
      dpMin[i][0] = dpMax[i][0] = dpMin[i - 1][0] * grid[i][0];

    for (int j = 1; j < n; ++j)
      dpMin[0][j] = dpMax[0][j] = dpMin[0][j - 1] * grid[0][j];

    for (int i = 1; i < m; ++i)
      for (int j = 1; j < n; ++j)
        if (grid[i][j] < 0) {
          dpMin[i][j] = max(dpMax[i - 1][j], dpMax[i][j - 1]) * grid[i][j];
          dpMax[i][j] = min(dpMin[i - 1][j], dpMin[i][j - 1]) * grid[i][j];
        } else {
          dpMin[i][j] = min(dpMin[i - 1][j], dpMin[i][j - 1]) * grid[i][j];
          dpMax[i][j] = max(dpMax[i - 1][j], dpMax[i][j - 1]) * grid[i][j];
        }

    const long mx = max(dpMin.back().back(), dpMax.back().back());
    return mx < 0 ? -1 : mx % kMod;
  }
};
/* code provided by PROGIEZ */

1594. Maximum Non Negative Product in a Matrix LeetCode Solution in Java

class Solution {
  public int maxProductPath(int[][] grid) {
    final int kMod = 1_000_000_007;
    final int m = grid.length;
    final int n = grid[0].length;
    // dpMin[i][j] := the minimum product from (0, 0) to (i, j)
    // dpMax[i][j] := the maximum product from (0, 0) to (i, j)
    long[][] dpMin = new long[m][n];
    long[][] dpMax = new long[m][n];

    dpMin[0][0] = dpMax[0][0] = grid[0][0];

    for (int i = 1; i < m; ++i)
      dpMin[i][0] = dpMax[i][0] = dpMin[i - 1][0] * grid[i][0];

    for (int j = 1; j < n; ++j)
      dpMin[0][j] = dpMax[0][j] = dpMin[0][j - 1] * grid[0][j];

    for (int i = 1; i < m; ++i)
      for (int j = 1; j < n; ++j)
        if (grid[i][j] < 0) {
          dpMin[i][j] = Math.max(dpMax[i - 1][j], dpMax[i][j - 1]) * grid[i][j];
          dpMax[i][j] = Math.min(dpMin[i - 1][j], dpMin[i][j - 1]) * grid[i][j];
        } else {
          dpMin[i][j] = Math.min(dpMin[i - 1][j], dpMin[i][j - 1]) * grid[i][j];
          dpMax[i][j] = Math.max(dpMax[i - 1][j], dpMax[i][j - 1]) * grid[i][j];
        }

    final long mx = Math.max(dpMin[m - 1][n - 1], dpMax[m - 1][n - 1]);
    return mx < 0 ? -1 : (int) (mx % kMod);
  }
}
// code provided by PROGIEZ