Leetcode Problem 1594. Maximum Non Negative Product in a Matrix

1594. Maximum Non Negative Product in a Matrix

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize two matrices maxProduct and minProduct of the same size as the input grid, to store the maximum and minimum product paths respectively.
  2. Set the value of the first cell in both maxProduct and minProduct to the value of the first cell in the grid.
  3. Fill the first row and first column of both matrices with the cumulative product of the grid values along the row or column.
  4. Iterate over the grid starting from cell (1,1) to the bottom-right corner.
  5. At each cell (i,j), calculate the maximum and minimum products by multiplying the grid value with the maximum and minimum products from the top (i-1,j) and left (i,j-1) cells.
  6. Update the maxProduct and minProduct matrices with the maximum and minimum of these values, respectively.
  7. After filling both matrices, check the value at the bottom-right corner of maxProduct.
  8. If the value is negative, return -1. Otherwise, return the value modulo 10^9 + 7.
UML Thumbnail

DFS with Memoization Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...