Given a 2D matrix grid of size m x n containing integers (which may be negative, zero, or positive), you are to find the maximum non-negative product that can be obtained by moving from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1). At each step, you can only move either right or down.
The product is calculated by multiplying all the numbers along the chosen path. If the maximum product is negative, return -1. Otherwise, return the maximum product modulo 10^9 + 7.
grid can be used at most once (since you cannot revisit cells).1 <= m, n <= 15, -4 <= grid[i][j] <= 4.At first glance, this problem seems like a standard path problem where you want to maximize a sum or product. However, the twist is that the matrix can contain negative numbers and zeros, which makes the product's sign and magnitude tricky to manage.
A brute-force approach would be to try all possible paths from the start to the end, calculate the product for each, and keep track of the maximum non-negative product. However, with up to 2^{m+n} possible paths, this approach is not feasible for larger matrices.
The key realization is that negative numbers can flip the sign of the product, and zeros can reset it. This means that at each cell, you need to keep track of both the maximum and minimum products that can be achieved at that point, since a minimum (negative) product could become the maximum if multiplied by a negative number later.
Thus, the problem is well-suited for a dynamic programming approach where at each cell, you maintain both the largest and smallest products possible up to that point.
To solve this problem efficiently, we use dynamic programming (DP) with the following strategy:
(i, j), maintain two values:
max_prod[i][j]: The maximum product achievable at (i, j) from the start.min_prod[i][j]: The minimum product achievable at (i, j) from the start.max_prod[0][0] = min_prod[0][0] = grid[0][0].
grid[i][j] is positive, multiplying by the previous max gives a new max, multiplying by the previous min gives a new min.grid[i][j] is negative, multiplying by the previous max gives a new min, multiplying by the previous min gives a new max.grid[i][j] == 0, both max and min become 0.max_prod[m-1][n-1] if it is non-negative, otherwise -1. Remember to return the answer modulo 10^9 + 7 if it is non-negative.
This approach ensures each cell is processed only once, and both the maximum and minimum products are tracked, preventing sign errors due to negative numbers.
Consider the following grid:
grid = [
[1, -2, 1],
[1, -2, 1],
[3, -4, 1]
]
(0,0) with value 1.(0,1), you can only come from the left: 1 * -2 = -2 (both max and min are -2).(1,0), only from above: 1 * 1 = 1 (both max and min are 1).(0,2), from (0,1): -2 * 1 = -2.(1,1), from top (max= -2, min= -2) or left (max= 1, min= 1), multiply by -2:
-2 * -2 = 4, -2 * -2 = 4.1 * -2 = -2, 1 * -2 = -2.max=4, min=-2.(2,2), the maximum non-negative product is 8.
Thus, the answer is 8.
O(2^{m+n}) (all possible paths).O(m+n) (for recursion stack).O(mn) (each cell is processed once, and each transition is constant time).O(mn) (for the DP tables).The DP approach is efficient and scalable for the given constraints.
This problem requires careful handling of negative numbers and zeros when calculating products along paths in a matrix. By using dynamic programming and maintaining both the maximum and minimum products at each cell, we ensure that we don't miss any optimal solution due to sign changes. The approach is efficient and elegant, turning a potentially exponential brute-force problem into a tractable one.
class Solution:
def maxProductPath(self, grid):
MOD = 10 ** 9 + 7
m, n = len(grid), len(grid[0])
max_prod = [[0] * n for _ in range(m)]
min_prod = [[0] * n for _ in range(m)]
max_prod[0][0] = min_prod[0][0] = grid[0][0]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
vals = []
if i > 0:
vals.append((max_prod[i-1][j], min_prod[i-1][j]))
if j > 0:
vals.append((max_prod[i][j-1], min_prod[i][j-1]))
max_val = max(x for pair in vals for x in pair)
min_val = min(x for pair in vals for x in pair)
if grid[i][j] >= 0:
max_prod[i][j] = max_val * grid[i][j]
min_prod[i][j] = min_val * grid[i][j]
else:
max_prod[i][j] = min_val * grid[i][j]
min_prod[i][j] = max_val * grid[i][j]
result = max_prod[-1][-1]
return result % MOD if result >= 0 else -1
class Solution {
public:
int maxProductPath(vector<vector<int>>& grid) {
const int MOD = 1e9 + 7;
int m = grid.size(), n = grid[0].size();
vector<vector<long long>> max_prod(m, vector<long long>(n, 0));
vector<vector<long long>> min_prod(m, vector<long long>(n, 0));
max_prod[0][0] = min_prod[0][0] = grid[0][0];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 && j == 0) continue;
long long max_val = LLONG_MIN, min_val = LLONG_MAX;
if (i > 0) {
max_val = max(max_val, max_prod[i-1][j]);
min_val = min(min_val, min_prod[i-1][j]);
}
if (j > 0) {
max_val = max(max_val, max_prod[i][j-1]);
min_val = min(min_val, min_prod[i][j-1]);
}
if (grid[i][j] >= 0) {
max_prod[i][j] = max_val * grid[i][j];
min_prod[i][j] = min_val * grid[i][j];
} else {
max_prod[i][j] = min_val * grid[i][j];
min_prod[i][j] = max_val * grid[i][j];
}
}
}
long long result = max_prod[m-1][n-1];
return result >= 0 ? result % MOD : -1;
}
};
class Solution {
public int maxProductPath(int[][] grid) {
int MOD = 1000000007;
int m = grid.length, n = grid[0].length;
long[][] maxProd = new long[m][n];
long[][] minProd = new long[m][n];
maxProd[0][0] = minProd[0][0] = grid[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
long maxVal = Long.MIN_VALUE, minVal = Long.MAX_VALUE;
if (i > 0) {
maxVal = Math.max(maxVal, maxProd[i-1][j]);
minVal = Math.min(minVal, minProd[i-1][j]);
}
if (j > 0) {
maxVal = Math.max(maxVal, maxProd[i][j-1]);
minVal = Math.min(minVal, minProd[i][j-1]);
}
if (grid[i][j] >= 0) {
maxProd[i][j] = maxVal * grid[i][j];
minProd[i][j] = minVal * grid[i][j];
} else {
maxProd[i][j] = minVal * grid[i][j];
minProd[i][j] = maxVal * grid[i][j];
}
}
}
long result = maxProd[m-1][n-1];
return result >= 0 ? (int)(result % MOD) : -1;
}
}
var maxProductPath = function(grid) {
const MOD = 1e9 + 7;
const m = grid.length, n = grid[0].length;
let maxProd = Array.from({length: m}, () => Array(n).fill(0));
let minProd = Array.from({length: m}, () => Array(n).fill(0));
maxProd[0][0] = minProd[0][0] = grid[0][0];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0 && j === 0) continue;
let candidates = [];
if (i > 0) candidates.push([maxProd[i-1][j], minProd[i-1][j]]);
if (j > 0) candidates.push([maxProd[i][j-1], minProd[i][j-1]]);
let maxVal = Math.max(...candidates.flat());
let minVal = Math.min(...candidates.flat());
if (grid[i][j] >= 0) {
maxProd[i][j] = maxVal * grid[i][j];
minProd[i][j] = minVal * grid[i][j];
} else {
maxProd[i][j] = minVal * grid[i][j];
minProd[i][j] = maxVal * grid[i][j];
}
}
}
let result = maxProd[m-1][n-1];
return result >= 0 ? result % MOD : -1;
};