Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1594.html
1594. Maximum Non Negative Product in a Matrix (Medium)
You are given a rows x cols 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 (rows - 1, cols - 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's 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 in bold (1 * 1 * -2 * -4 * 1 = 8).
Example 3:
Input: grid = [[1, 3], [0,-4]] Output: 0 Explanation: Maximum non-negative product is in bold (1 * 0 * -4 = 0).
Example 4:
Input: grid = [[ 1, 4,4,0], [-2, 0,0,1], [ 1,-1,1,1]] Output: 2 Explanation: Maximum non-negative product is in bold (1 * -2 * 1 * -1 * 1 * 1 = 2).
Constraints:
1 <= rows, cols <= 15-4 <= grid[i][j] <= 4
Related Topics:
Dynamic Programming, Greedy
Solution 1. DP
// OJ: https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
int maxProductPath(vector<vector<int>>& G) {
long ans = 0, mod = 1e9+7, M = G.size(), N = G[0].size();
vector<vector<pair<long, long>>> dp(M + 1, vector<pair<long, long>>(N + 1, { INT_MAX, INT_MIN })); // min, max
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (i == 0 && j == 0) dp[i][j] = {G[i][j], G[i][j]};
if (i != 0) {
dp[i][j].first = min(dp[i - 1][j].first * G[i][j], dp[i - 1][j].second * G[i][j]);
dp[i][j].second = max(dp[i - 1][j].first * G[i][j], dp[i - 1][j].second * G[i][j]);
}
if (j != 0) {
dp[i][j].first = min({ dp[i][j].first, dp[i][j - 1].first * G[i][j], dp[i][j - 1].second * G[i][j] });
dp[i][j].second = max({ dp[i][j].second, dp[i][j - 1].first * G[i][j], dp[i][j - 1].second * G[i][j] });
}
}
}
return dp[M - 1][N - 1].second < 0 ? -1 : (dp[M - 1][N - 1].second % mod);
}
};
Solution 2. DP with Space Optimization
// OJ: https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/
// Time: O(MN)
// Space: O(N)
class Solution {
public:
int maxProductPath(vector<vector<int>>& G) {
long ans = 0, mod = 1e9+7, M = G.size(), N = G[0].size();
vector<pair<long, long>> dp(N + 1); // min, max
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
long mn = INT_MAX, mx = INT_MIN;
if (i == 0 && j == 0) mn = mx = G[i][j];
if (i != 0) {
mn = min(dp[j].first * G[i][j], dp[j].second * G[i][j]);
mx = max(dp[j].first * G[i][j], dp[j].second * G[i][j]);
}
if (j != 0) {
mn = min({ mn, dp[j - 1].first * G[i][j], dp[j - 1].second * G[i][j] });
mx = max({ mx, dp[j - 1].first * G[i][j], dp[j - 1].second * G[i][j] });
}
dp[j] = { mn, mx };
}
}
return dp[N - 1].second < 0 ? -1 : (dp[N - 1].second % mod);
}
};
Java
-
class Solution { public int maxProductPath(int[][] grid) { final int MODULO = 1000000007; long maxProduct = -1; int rows = grid.length, columns = grid[0].length; long[][][] products = new long[rows][columns][2]; products[0][0][0] = products[0][0][1] = grid[0][0]; for (int i = 1; i < rows; i++) { long product = products[i - 1][0][0] * grid[i][0]; if (product == 0 && maxProduct < 0) maxProduct = 0; products[i][0][0] = products[i][0][1] = product; } for (int j = 1; j < columns; j++) { long product = products[0][j - 1][0] * grid[0][j]; if (product == 0 && maxProduct < 0) maxProduct = 0; products[0][j][0] = products[0][j][1] = product; } for (int i = 1; i < rows; i++) { for (int j = 1; j < columns; j++) { int num = grid[i][j]; if (num == 0 && maxProduct < 0) maxProduct = 0; long product1 = products[i - 1][j][0] * num; long product2 = products[i - 1][j][1] * num; long product3 = products[i][j - 1][0] * num; long product4 = products[i][j - 1][1] * num; long[] array = {product1, product2, product3, product4}; Arrays.sort(array); long min = array[0], max = array[3]; if (max > 0) products[i][j][0] = max; else products[i][j][0] = min; if (min < 0) products[i][j][1] = min; else products[i][j][1] = max; } } maxProduct = Math.max(maxProduct, Math.max(products[rows - 1][columns - 1][0], products[rows - 1][columns - 1][1])); return (int) (maxProduct % MODULO); } } -
// OJ: https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/ // Time: O(MN) // Space: O(MN) class Solution { public: int maxProductPath(vector<vector<int>>& G) { long ans = 0, mod = 1e9+7, M = G.size(), N = G[0].size(); vector<vector<pair<long, long>>> dp(M + 1, vector<pair<long, long>>(N + 1, { INT_MAX, INT_MIN })); // min, max for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (i == 0 && j == 0) dp[i][j] = {G[i][j], G[i][j]}; if (i != 0) { dp[i][j].first = min(dp[i - 1][j].first * G[i][j], dp[i - 1][j].second * G[i][j]); dp[i][j].second = max(dp[i - 1][j].first * G[i][j], dp[i - 1][j].second * G[i][j]); } if (j != 0) { dp[i][j].first = min({ dp[i][j].first, dp[i][j - 1].first * G[i][j], dp[i][j - 1].second * G[i][j] }); dp[i][j].second = max({ dp[i][j].second, dp[i][j - 1].first * G[i][j], dp[i][j - 1].second * G[i][j] }); } } } return dp[M - 1][N - 1].second < 0 ? -1 : (dp[M - 1][N - 1].second % mod); } }; -
class Solution: def maxProductPath(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) mod = 10**9 + 7 dp = [[[grid[0][0]] * 2 for _ in range(n)] for _ in range(m)] for i in range(1, m): dp[i][0] = [dp[i - 1][0][0] * grid[i][0]] * 2 for j in range(1, n): dp[0][j] = [dp[0][j - 1][0] * grid[0][j]] * 2 for i in range(1, m): for j in range(1, n): v = grid[i][j] if v >= 0: dp[i][j][0] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * v dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * v else: dp[i][j][0] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * v dp[i][j][1] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * v ans = dp[-1][-1][1] return -1 if ans < 0 else ans % mod ############ # 1594. Maximum Non Negative Product in a Matrix # https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/ class Solution: def maxProductPath(self, A: List[List[int]]) -> int: m, n = len(A), len(A[0]) Max = [[0] * n for _ in range(m)] Min = [[0] * n for _ in range(m)] Max[0][0] = A[0][0] Min[0][0] = A[0][0] for j in range(1, n): Max[0][j] = Max[0][j - 1] * A[0][j] Min[0][j] = Min[0][j - 1] * A[0][j] for i in range(1, m): Max[i][0] = Max[i - 1][0] * A[i][0] Min[i][0] = Min[i - 1][0] * A[i][0] for i in range(1,m): for j in range(1,n): Max[i][j] = max(Max[i-1][j] * A[i][j], Min[i-1][j] * A[i][j], Max[i][j-1] * A[i][j], Min[i][j-1] * A[i][j]) Min[i][j] = min(Max[i-1][j] * A[i][j], Min[i-1][j] * A[i][j], Max[i][j-1] * A[i][j], Min[i][j-1] * A[i][j]) return Max[-1][-1] % int(1e9 + 7) if Max[-1][-1] >= 0 else -1 # revisited solutin class Solution: def maxProductPath(self, A: List[List[int]]) -> int: M = 1000000007 row, col = len(A), len(A[0]) mp = [[0] * col for _ in range(row)] mn = [[0] * col for _ in range(row)] mp[0][0] = mn[0][0] = A[0][0] for i in range(1,col): mp[0][i] = A[0][i] * mp[0][i-1] mn[0][i] = A[0][i] * mp[0][i-1] for i in range(1,row): mp[i][0] = A[i][0] * mp[i-1][0] mn[i][0] = A[i][0] * mp[i-1][0] for i in range(1,row): for j in range(1,col): if A[i][j] > 0: mp[i][j] = max(mp[i-1][j], mp[i][j-1]) * A[i][j] mn[i][j] = min(mn[i-1][j], mn[i][j-1]) * A[i][j] else: mp[i][j] = min(mn[i-1][j], mn[i][j-1]) * A[i][j] mn[i][j] = max(mp[i-1][j], mp[i][j-1]) * A[i][j] res = mp[row-1][col-1] return res%M if res > -1 else -1