Leetcode 1594. Maximum Non Negative Product in a Matrix
Explanation
In this problem, we are given a 2D grid and we start from the top-left cell. In each move, we can only move to the right or bottom cell. We need to find the maximum non-negative product that can be achieved by moving from the top-left corner to the bottom-right corner of the grid. We take the product of all the numbers in the path.
The key to solving this problem is to use dynamic programming. We start with two 2D dp arrays, dpMin
and dpMax
, to keep track of the minimum and maximum product from (0,0) to (i,j), respectively.
To fill these dp tables, we iterate over every cell in the grid:
- If the current cell contains a negative number, the maximum product is the maximum between
dpMax[i-1][j]
anddpMax[i][j-1]
multiplied by current cell value, and the minimum product is the minimum betweendpMin[i-1][j]
anddpMin[i][j-1]
multiplied by the current cell value. - If the current cell contains a non-negative number, the reverse holds: the maximum product results from the maximum of the same quantities but multiplied by the current cell value, and the minimum product comes from the minimum of the same quantities but multiplied by the current cell value.
Finally, we return the maximum between the last element of dpMin
and dpMax
. If this maximum is negative, we return -1
; else, we return maxi % kMod
where kMod = 1'000'000'007
.
Walk-through Example
Take the grid from the 2nd example [[1,-2,1],[1,-2,1],[3,-4,1]]
. Start from dpMin
and dpMax
:
1 2ASCII 3dpMin = dpMax = [[1, 0, 0], [0, 0, 0], [0, 0, 0]]
- Update the first row and column. This is because we only have one way to reach those cells - by moving right (for the first row) or down (for the first column).
1 2ASCII 3dpMin = dpMax = [[1, -2, -2], [1, 0, 0], [3, 0, 0]]
- Update the rest of the cells. Start from cell (1,1):
- Since
grid[1][1]
is negative,dpMin[1][1] = max(dpMax[0][1], dpMax[1][0]) * grid[1][1] = 2
anddpMax[1][1] = min(dpMin[0][1], dpMin[1][0]) * grid[1][1] = -4
. Now the dp tables look like:
1 2ASCII 3dpMin = [[1, -2, -2], [1, 2, 0], [3, 0, 0]] 4dpMax = [[1, -2, -2], [1, -4, 0], [3, 0, 0]]
Follow the same procedure for the rest of the cells to get:
1 2ASCII 3dpMin = [[1, -2, -2], [1, 2, -2], [3, -8, -8]] 4dpMax = [[1, -2, -2], [1, -4, 4], [3, 12, -8]]
- The maximum non-negative product of the path is 8.
Python Solution
1 2python 3class Solution: 4 def maxProductPath(self, grid: List[List[int]]) -> int: 5 m, n = len(grid), len(grid[0]) 6 dp_min = [[0]*n for _ in range(m)] 7 dp_max = [[0]*n for _ in range(m)] 8 dp_min[0][0] = dp_max[0][0] = grid[0][0] 9 # fill the edges 10 for i in range(1, m): dp_min[i][0] = dp_max[i][0] = dp_min[i-1][0] * grid[i][0] 11 for j in range(1, n): dp_min[0][j] = dp_max[0][j] = dp_min[0][j-1] * grid[0][j] 12 for i in range(1, m): 13 for j in range(1, n): 14 if grid[i][j] < 0: 15 dp_min[i][j] = max(dp_max[i-1][j] * grid[i][j], dp_max[i][j-1] * grid[i][j]) 16 dp_max[i][j] = min(dp_min[i-1][j] * grid[i][j], dp_min[i][j-1] * grid[i][j]) 17 else: 18 dp_min[i][j] = min(dp_min[i-1][j] * grid[i][j], dp_min[i][j-1] * grid[i][j]) 19 dp_max[i][j] = max(dp_max[i-1][j] * grid[i][j], dp_max[i][j-1] * grid[i][j]) 20 return max(-1, dp_max[-1][-1] % (10**9 + 7))
Java Solution
1
2java
3class Solution {
4 public int maxProductPath(int[][] grid) {
5 int mod = (int) (1e9 + 7), rows = grid.length, cols = grid[0].length;
6 long[][] maxDP = new long[rows][cols], minDP = new long[rows][cols];
7 maxDP[0][0] = minDP[0][0] = grid[0][0];
8 for (int i=1; i<rows; i++) maxDP[i][0] = minDP[i][0] = minDP[i-1][0] * grid[i][0];
9 for (int i=1; i<cols; i++) maxDP[0][i] = minDP[0][i] = minDP[0][i-1] * grid[0][i];
10 for (int i=1; i<rows; i++)
11 for (int j=1; j<cols; j++) {
12 if (grid[i][j] < 0) {
13 maxDP[i][j] = Math.min(minDP[i-1][j], minDP[i][j-1]) * grid[i][j];
14 minDP[i][j] = Math.max(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j];
15 }
16 else {
17 maxDP[i][j] = Math.max(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j];
18 minDP[i][j] = Math.min(minDP[i-1][j], minDP[i][j-1]) * grid[i][j];
19 }
20 }
21 return maxDP[rows-1][cols-1] < 0 ? -1 : (int)(maxDP[rows-1][cols-1] % mod);
22 }
23}
JavaScript Solution
1 2javascript 3var maxProductPath = function(grid) { 4 const m = grid.length; 5 const n = grid[0].length; 6 const maxDP = Array(m).fill(0).map(() => Array(n).fill(0)); 7 const minDP = Array(m).fill(0).map(() => Array(n).fill(0)); 8 9 maxDP[0][0] = minDP[0][0] = grid[0][0]; 10 for (let i = 1; i < m; i++) maxDP[i][0] = minDP[i][0] = minDP[i - 1][0] * grid[i][0]; 11 for (let i = 1; i < n; i++) maxDP[0][i] = minDP[0][i] = minDP[0][i - 1] * grid[0][i]; 12 for (let i = 1; i < m; i++) 13 for (let j = 1; j < n; j++) 14 if (grid[i][j] < 0) { 15 maxDP[i][j] = Math.min(minDP[i - 1][j], minDP[i][j - 1]) * grid[i][j]; 16 minDP[i][j] = Math.max(maxDP[i - 1][j], maxDP[i][j - 1]) * grid[i][j]; 17 } else { 18 maxDP[i][j] = Math.max(maxDP[i - 1][j], maxDP[i][j - 1]) * grid[i][j]; 19 minDP[i][j] = Math.min(minDP[i - 1][j], minDP[i][j - 1]) * grid[i][j]; 20 } 21 return maxDP[m - 1][n - 1] < 0 ? -1 : maxDP[m - 1][n - 1] % (1e9 + 7); 22};
C++ Solution
1
2cpp
3class Solution {
4public:
5 int maxProductPath(vector<vector<int>>& grid) {
6 int mod = 1e9 + 7, rows = grid.size(), cols = grid[0].size();
7 vector<vector<long long>> maxDP(rows, vector<long long>(cols)),
8 minDP(rows, vector<long long>(cols));
9 maxDP[0][0] = minDP[0][0] = grid[0][0];
10 for (int i=1; i<rows; ++i)
11 maxDP[i][0] = minDP[i][0] = minDP[i-1][0] * grid[i][0];
12 for (int i=1; i<cols; ++i)
13 maxDP[0][i] = minDP[0][i] = minDP[0][i-1] * grid[0][i];
14
15 for (int i=1; i<rows; ++i)
16 for (int j=1; j<cols; ++j)
17 if (grid[i][j] < 0) {
18 maxDP[i][j] = max(minDP[i-1][j], minDP[i][j-1]) * grid[i][j];
19 minDP[i][j] = min(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j];
20 } else {
21 maxDP[i][j] = max(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j];
22 minDP[i][j] = min(minDP[i-1][j], minDP[i][j-1]) * grid[i][j];
23 }
24
25 return maxDP[rows-1][cols-1] < 0 ? -1 : maxDP[rows-1][cols-1] % mod;
26 }
27};
C# Solution
1
2csharp
3public class Solution {
4 public int MaxProductPath(int[][] grid) {
5 int mod = (int)(1e9 + 7), rows = grid.Length, cols = grid[0].Length;
6 long[][] maxDP = new long[rows][], minDP = new long[rows][];
7 for (int i=0; i<rows; i++) {
8 maxDP[i] = new long[cols];
9 minDP[i] = new long[cols];
10 }
11
12 maxDP[0][0] = minDP[0][0] = grid[0][0];
13 for (int i=1; i<rows; i++) maxDP[i][0] = minDP[i][0] = minDP[i-1][0] * grid[i][0];
14 for (int i=1; i<cols; i++) maxDP[0][i] = minDP[0][i] = minDP[0][i-1] * grid[0][i];
15
16 for (int i=1; i<rows; i++)
17 for (int j=1; j<cols; j++)
18 if (grid[i][j] < 0) {
19 maxDP[i][j] = Math.Max(minDP[i-1][j], minDP[i][j-1]) * grid[i][j];
20 minDP[i][j] = Math.Min(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j];
21 } else {
22 maxDP[i][j] = Math.Max(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j];
23 minDP[i][j] = Math.Min(minDP[i-1][j], minDP[i][j-1]) * grid[i][j];
24 }
25
26 return (int)(maxDP[rows-1][cols-1] < 0 ? -1 : maxDP[rows-1][cols-1] % mod);
27 }
28}
Go Solution
1 2go 3func maxProductPath(grid [][]int) int { 4 mod := int(1e9 + 7) 5 rows, cols := len(grid), len(grid[0]) 6 maxDP := make([][]int, rows) 7 minDP := make([][]int, rows) 8 for i := range maxDP { 9 maxDP[i] = make([]int, cols) 10 minDP[i] = make([]int, cols) 11 } 12 13 maxDP[0][0] = grid[0][0] 14 minDP[0][0] = grid[0][0] 15 16 17 for i := 1; i < rows; i++ { 18 maxDP[i][0] = maxDP[i - 1][0] * grid[i][0] 19 minDP[i][0] = minDP[i - 1][0] * grid[i][0] 20 } 21 22 for i := 1; i < cols; i++ { 23 maxDP[0][i] = maxDP[0][i - 1] * grid[0][i] 24 minDP[0][i] = minDP[0][i - 1] * grid[0][i] 25 } 26 27 for i := 1; i < rows; i++ { 28 for j := 1; j < cols; j++ { 29 if grid[i][j] < 0 { 30 maxDP[i][j] = max(minDP[i-1][j], minDP[i][j-1]) * grid[i][j] 31 minDP[i][j] = min(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j] 32 } else { 33 maxDP[i][j] = max(maxDP[i-1][j], maxDP[i][j-1]) * grid[i][j] 34 minDP[i][j] = min(minDP[i-1][j], minDP[i][j-1]) * grid[i][j] 35 } 36 } 37 } 38 return maxDP[rows-1][cols-1] < 0 ? -1 : maxDP[rows-1][cols-1] % mod; 39} 40 41func min(a, b int) int { 42 if a < b { 43 return a 44 } 45 return b 46} 47 48func max(a, b int) int { 49 if a > b { 50 return a 51 } 52 return b 53}
In the above Go solution, maxDP
and minDP
arrays are created with size equals to the grid. These arrays store the maximum and minimum product possible to reach the cell (i, j)
from the top left corner (0, 0)
.
We fill the first row and column with product of elements till a certain cell, as we can move only left or down to reach there. And for the rest of the cells, we use the values from maxDP
and minDP
arrays of its neighbouring cells, as these represent the maximum and minimum product possible to reach the cell (i-1, j)
or (i, j-1)
from (0, 0)
. At the end, we return the maximum product possible to reach the bottom right cell (rows-1, cols-1)
from (0, 0)
, or -1
if it is negative.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.