Description
You are given a 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) and ending in the bottom-right corner (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 + 7. If the maximum product is negative, return -1.
Notice that the modulo is performed after getting the maximum product.
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.lengthn == grid[i].length1 <= m, n <= 15-4 <= grid[i][j] <= 4
Solutions
Solution 1: Dynamic Programming
We define a 3D array f, where f[i][j][0] and f[i][j][1] represent the minimum and maximum product of all paths from the top-left corner (0, 0) to position (i, j), respectively. For each position (i, j), we can transition from above (i - 1, j) or from the left (i, j - 1), so we need to consider the results of multiplying the minimum and maximum products of these two paths by the value of the current cell.
Finally, we need to return f[m - 1][n - 1][1] modulo 109 + 7. If f[m - 1][n - 1][1] is less than 0, return -1.
The time complexity is O(m × n) and the space complexity is O(m × n), where m and n are the number of rows and columns of the matrix, respectively.
PythonJavaC++GoTypeScriptRust
class Solution:
def maxProductPath(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
f = [[[0, 0] for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
x = grid[i][j]
if i == 0 and j == 0:
f[i][j][0] = x
f[i][j][1] = x
continue
mn, mx = inf, -inf
if i > 0:
a, b = f[i - 1][j]
mn = min(mn, a * x, b * x)
mx = max(mx, a * x, b * x)
if j > 0:
a, b = f[i][j - 1]
mn = min(mn, a * x, b * x)
mx = max(mx, a * x, b * x)
f[i][j][0], f[i][j][1] = mn, mx
ans = f[m - 1][n - 1][1]
mod = 10**9 + 7
return -1 if ans < 0 else ans % mod(code-box)
class Solution {
public int maxProductPath(int[][] grid) {
int m = grid.length, n = grid[0].length;
long[][][] f = new long[m][n][2];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
long x = grid[i][j];
if (i == 0 && j == 0) {
f[i][j][0] = x;
f[i][j][1] = x;
continue;
}
long mn = Long.MAX_VALUE, mx = Long.MIN_VALUE;
if (i > 0) {
long a = f[i - 1][j][0], b = f[i - 1][j][1];
mn = Math.min(mn, Math.min(a * x, b * x));
mx = Math.max(mx, Math.max(a * x, b * x));
}
if (j > 0) {
long a = f[i][j - 1][0], b = f[i][j - 1][1];
mn = Math.min(mn, Math.min(a * x, b * x));
mx = Math.max(mx, Math.max(a * x, b * x));
}
f[i][j][0] = mn;
f[i][j][1] = mx;
}
}
long ans = f[m - 1][n - 1][1];
int mod = (int) 1e9 + 7;
return ans < 0 ? -1 : (int) (ans % mod);
}
}(code-box)
class Solution {
public:
int maxProductPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<array<long long, 2>>> f(m, vector<array<long long, 2>>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
long long x = grid[i][j];
if (i == 0 && j == 0) {
f[i][j] = {x, x};
continue;
}
long long mn = LLONG_MAX, mx = LLONG_MIN;
if (i > 0) {
auto [a, b] = f[i - 1][j];
mn = min(mn, min(a * x, b * x));
mx = max(mx, max(a * x, b * x));
}
if (j > 0) {
auto [a, b] = f[i][j - 1];
mn = min(mn, min(a * x, b * x));
mx = max(mx, max(a * x, b * x));
}
f[i][j] = {mn, mx};
}
}
long long ans = f[m - 1][n - 1][1];
const int mod = 1e9 + 7;
return ans < 0 ? -1 : ans % mod;
}
};(code-box)
func maxProductPath(grid [][]int) int {
m, n := len(grid), len(grid[0])
f := make([][][2]int64, m)
for i := range f {
f[i] = make([][2]int64, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
x := int64(grid[i][j])
if i == 0 && j == 0 {
f[i][j] = [2]int64{x, x}
continue
}
mn, mx := int64(1<<63-1), int64(-1<<63)
if i > 0 {
a, b := f[i-1][j][0], f[i-1][j][1]
mn = min(mn, min(a*x, b*x))
mx = max(mx, max(a*x, b*x))
}
if j > 0 {
a, b := f[i][j-1][0], f[i][j-1][1]
mn = min(mn, min(a*x, b*x))
mx = max(mx, max(a*x, b*x))
}
f[i][j] = [2]int64{mn, mx}
}
}
ans := f[m-1][n-1][1]
mod := int64(1e9 + 7)
if ans < 0 {
return -1
}
return int(ans % mod)
}(code-box)
function maxProductPath(grid: number[][]): number {
const m = grid.length,
n = grid[0].length;
const f = Array.from({ length: m }, () => Array.from({ length: n }, () => [0, 0]));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const x = grid[i][j];
if (i === 0 && j === 0) {
f[i][j] = [x, x];
continue;
}
let mn = Infinity,
mx = -Infinity;
if (i > 0) {
const [a, b] = f[i - 1][j];
mn = Math.min(mn, a * x, b * x);
mx = Math.max(mx, a * x, b * x);
}
if (j > 0) {
const [a, b] = f[i][j - 1];
mn = Math.min(mn, a * x, b * x);
mx = Math.max(mx, a * x, b * x);
}
f[i][j] = [mn, mx];
}
}
const ans = f[m - 1][n - 1][1];
const mod = 1e9 + 7;
return ans < 0 ? -1 : ans % mod;
}(code-box)
impl Solution {
pub fn max_product_path(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut f = vec![vec![[0i64; 2]; n]; m];
for i in 0..m {
for j in 0..n {
let x = grid[i][j] as i64;
if i == 0 && j == 0 {
f[i][j] = [x, x];
continue;
}
let mut mn = i64::MAX;
let mut mx = i64::MIN;
if i > 0 {
let [a, b] = f[i - 1][j];
mn = mn.min(a * x).min(b * x);
mx = mx.max(a * x).max(b * x);
}
if j > 0 {
let [a, b] = f[i][j - 1];
mn = mn.min(a * x).min(b * x);
mx = mx.max(a * x).max(b * x);
}
f[i][j] = [mn, mx];
}
}
let ans = f[m - 1][n - 1][1];
let mod_val = 1_000_000_007i64;
if ans < 0 {
-1
} else {
(ans % mod_val) as i32
}
}
}(code-box)
