Skip to main content

Maximum Non Negative Product in a Matrix

In this page, we will solve the Maximum Non Negative Product in a Matrix problem using different approaches. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description​

You are given an 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)(0, 0) and ending in the bottom-right corner (m−1,n−1)(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+710^9 + 7. If the maximum product is negative, return -1.

Examples​

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.lengthm == grid.length
  • n==grid[i].lengthn == grid[i].length
  • 1<=m,n<=151 <= m, n <= 15
  • −4<=grid[i][j]<=4-4 <= grid[i][j] <= 4

Solution for Maximum Non Negative Product in a Matrix​

Intuition and Approach​

To solve this problem, we can use Dynamic Programming (DP). We'll maintain two DP arrays maxDP and minDP, where:

  • maxDP[i][j] will store the maximum product to reach cell (i, j).
  • minDP[i][j] will store the minimum product to reach cell (i, j).

At each cell (i, j), we will consider the values from the cell above (i-1, j) and from the cell to the left (i, j-1). This helps in managing both positive and negative products.

Approach 1: Dynamic Programming​

Implementation​

Live Editor
function maximumNonNegativeProductInMatrix() {
  const grid = [[1,-2,1],[1,-2,1],[3,-4,1]];

  const maxProductPath = function(grid) {
    const MOD = 1e9 + 7;
    const m = grid.length, n = grid[0].length;
    const maxDP = Array.from({length: m}, () => Array(n).fill(0));
    const minDP = Array.from({length: m}, () => Array(n).fill(0));

    maxDP[0][0] = minDP[0][0] = grid[0][0];

    for (let i = 1; i < m; ++i) {
      maxDP[i][0] = minDP[i][0] = maxDP[i - 1][0] * grid[i][0];
    }

    for (let j = 1; j < n; ++j) {
      maxDP[0][j] = minDP[0][j] = maxDP[0][j - 1] * grid[0][j];
    }

    for (let i = 1; i < m; ++i) {
      for (let j = 1; j < n; ++j) {
        if (grid[i][j] >= 0) {
          maxDP[i][j] = Math.max(maxDP[i - 1][j], maxDP[i][j - 1]) * grid[i][j];
          minDP[i][j] = Math.min(minDP[i - 1][j], minDP[i][j - 1]) * grid[i][j];
        } else {
          maxDP[i][j] = Math.min(minDP[i - 1][j], minDP[i][j - 1]) * grid[i][j];
          minDP[i][j] = Math.max(maxDP[i - 1][j], maxDP[i][j - 1]) * grid[i][j];
        }
      }
    }

    const result = maxDP[m - 1][n - 1];
    return result < 0 ? -1 : result % MOD;
  };

  const result = maxProductPath(grid);
  return (
    <div>
      <p>
        <b>Input:</b> grid = {JSON.stringify(grid)}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}
Result
Loading...

Code in Different Languages​

Written by @manishh12
 function maxProductPath(grid) {
   const MOD = 1e9 + 7;
   const m = grid.length, n = grid[0].length;
   const maxDP = Array.from({length: m}, () => Array(n).fill(0));
   const minDP = Array.from({length: m}, () => Array(n).fill(0));

   maxDP[0][0] = minDP[0][0] = grid[0][0];

   for (let i = 1; i < m; ++i) {
     maxDP[i][0] = minDP[i][0] = maxDP[i - 1][0] * grid[i][0];
   }

   for (let j = 1; j < n; ++j) {
     maxDP[0][j] = minDP[0][j] = maxDP[0][j - 1] * grid[0][j];
   }

   for (let i = 1; i < m; ++i) {
     for (let j = 1; j < n; ++j) {
       if (grid[i][j] >= 0) {
         maxDP[i][j] = Math.max(maxDP[i - 1][j], maxDP[i][j - 1]) * grid[i][j];
         minDP[i][j] = Math.min(minDP[i - 1][j], minDP[i][j - 1]) * grid[i][j];
       } else {
         maxDP[i][j] = Math.min(minDP[i - 1][j], minDP[i][j - 1]) * grid[i][j];
         minDP[i][j] = Math.max(maxDP[i - 1][j], maxDP[i][j - 1]) * grid[i][j];
       }
     }
   }

   const result = maxDP[m - 1][n - 1];
   return result < 0 ? -1 : result % MOD;
 }

Complexity Analysis​

  • Time Complexity: O(m×n)O(m \times n) since we process each cell once.
  • Space Complexity: O(m×n)O(m \times n) for storing the DP arrays.
tip

By using either the Tabulation approach or the Memoization approach, we can efficiently solve the Maximum Non Negative Product in a Matrix. The choice of implementation language depends on the specific requirements and constraints of the problem.

References​