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 + 7If 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);
        }
    };
    
  • # 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
    

All Problems

All Solutions