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] and dpMax[i][j-1] multiplied by current cell value, and the minimum product is the minimum between dpMin[i-1][j] and dpMin[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]]

1. 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]]

2. 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 and dpMax[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]]

3. 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.