Maximum Non Negative Product in a Matrix
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores every possible path from the top-left to the bottom-right corner using recursion. For each path, it calculates the product of its elements and keeps track of the maximum non-negative product found so far.
Algorithm
- Initialize a global variable
maxProductto -1. - Create a recursive function
solve(row, col, currentProduct). - The function takes the current row, column, and the product of the path so far.
- Base Case: If
row == m-1andcol == n-1, we have reached the destination.- Calculate the final product:
finalProduct = currentProduct * grid[row][col]. - If
finalProduct >= 0, updatemaxProduct = max(maxProduct, finalProduct). - Return.
- Calculate the final product:
- Recursive Step:
- Calculate the new product for the current cell:
newProduct = currentProduct * grid[row][col]. - If
row + 1 < m, callsolve(row + 1, col, newProduct). - If
col + 1 < n, callsolve(row, col, newProduct).
- Calculate the new product for the current cell:
- Start the process by calling
solve(0, 0, 1). - After the recursion completes, if
maxProductis still -1, it means no non-negative path exists. Otherwise, returnmaxProduct % (10^9 + 7).
Walkthrough
The brute-force method involves a straightforward depth-first search (DFS) from the starting cell (0, 0). We define a recursive helper function, say solve(row, col, currentProduct), that explores paths. This function is called for every possible next step (down or right).
The currentProduct parameter accumulates the product of values along the path. When the recursion reaches the destination cell (m-1, n-1), we have a complete path. We then check if the final product is non-negative. If it is, we compare it with a global maximum product and update it if the current path's product is larger.
Since we explore all paths, we are guaranteed to find the maximum product. However, the number of paths grows exponentially with the size of the grid, making this solution impractical for all but the smallest grids.
class Solution { long maxProduct = -1; int MOD = 1_000_000_007; public int maxProductPath(int[][] grid) { int m = grid.length; int n = grid[0].length; solve(grid, 0, 0, 1L); if (maxProduct == -1) { return -1; } return (int) (maxProduct % MOD); } private void solve(int[][] grid, int r, int c, long currentProduct) { int m = grid.length; int n = grid[0].length; if (r >= m || c >= n) { return; } currentProduct *= grid[r][c]; if (r == m - 1 && c == n - 1) { if (currentProduct >= 0) { maxProduct = Math.max(maxProduct, currentProduct); } return; } solve(grid, r + 1, c, currentProduct); solve(grid, r, c + 1, currentProduct); }}Complexity
Time
O(C(m+n-2, m-1)) - The number of paths from `(0,0)` to `(m-1, n-1)` is given by the binomial coefficient `C((m-1)+(n-1), m-1)`. This grows exponentially, making it very slow.
Space
O(m + n) - The space complexity is determined by the maximum depth of the recursion stack, which corresponds to the length of a path from `(0,0)` to `(m-1, n-1)`.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
This approach uses dynamic programming to solve the problem efficiently. The key insight is that due to negative numbers, a path with a minimum (large negative) product could become a maximum positive product in a subsequent step. Therefore, we maintain two DP tables: one for the maximum product (maxDp) and one for the minimum product (minDp) to reach each cell.
Algorithm
- Get grid dimensions
mandn. - Create two
m x nDP tables,maxDpandminDp, of typelong. - Base Case: Initialize
maxDp[0][0] = grid[0][0]andminDp[0][0] = grid[0][0]. - Fill first row: For
jfrom 1 ton-1, calculatemaxDp[0][j]andminDp[0][j]based on the values at(0, j-1)andgrid[0][j], considering the sign ofgrid[0][j]. - Fill first column: For
ifrom 1 tom-1, calculatemaxDp[i][0]andminDp[i][0]based on the values at(i-1, 0)andgrid[i][0]. - Fill the rest of the tables: For
ifrom 1 tom-1andjfrom 1 ton-1:- Let
val = grid[i][j]. - If
val >= 0:maxDp[i][j] = val * max(maxDp[i-1][j], maxDp[i][j-1])minDp[i][j] = val * min(minDp[i-1][j], minDp[i][j-1])
- If
val < 0:maxDp[i][j] = val * min(minDp[i-1][j], minDp[i][j-1])minDp[i][j] = val * max(maxDp[i-1][j], maxDp[i][j-1])
- Let
- The result is
maxDp[m-1][n-1]. If it's negative, return -1. Otherwise, returnresult % (10^9 + 7).
Walkthrough
We create two 2D arrays, maxDp[m][n] and minDp[m][n], to store the maximum and minimum path products ending at cell (i, j), respectively. We iterate through the grid, filling these tables.
- Initialization: The values for
(0,0)aremaxDp[0][0] = minDp[0][0] = grid[0][0]. - Transitions: For any other cell
(i, j), the path to it must come from either(i-1, j)(top) or(i, j-1)(left). The product at(i, j)isgrid[i][j]multiplied by the product from one of these previous cells.- If
grid[i][j]is non-negative, the new maximum product isgrid[i][j]times the maximum of the previous maximum products (max(maxDp[i-1][j], maxDp[i][j-1])). Similarly for the minimum product. - If
grid[i][j]is negative, the roles are swapped: the new maximum product isgrid[i][j]times the minimum of the previous minimum products (min(minDp[i-1][j], minDp[i][j-1])), as multiplying by a negative flips the sign and magnitude order.
- If
- Final Result: After filling the tables,
maxDp[m-1][n-1]holds the maximum product for any path from(0,0)to(m-1,n-1). If this value is negative, no non-negative path exists. Otherwise, we return the result modulo10^9 + 7.
class Solution { public int maxProductPath(int[][] grid) { int m = grid.length; int n = grid[0].length; long[][] maxDp = new long[m][n]; long[][] minDp = new long[m][n]; int MOD = 1_000_000_007; maxDp[0][0] = minDp[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { long val = grid[i][0]; maxDp[i][0] = maxDp[i - 1][0] * val; minDp[i][0] = minDp[i - 1][0] * val; } for (int j = 1; j < n; j++) { long val = grid[0][j]; maxDp[0][j] = maxDp[0][j - 1] * val; minDp[0][j] = minDp[0][j - 1] * val; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { long val = grid[i][j]; if (val >= 0) { maxDp[i][j] = Math.max(maxDp[i - 1][j], maxDp[i][j - 1]) * val; minDp[i][j] = Math.min(minDp[i - 1][j], minDp[i][j - 1]) * val; } else { maxDp[i][j] = Math.min(minDp[i - 1][j], minDp[i][j - 1]) * val; minDp[i][j] = Math.max(maxDp[i - 1][j], maxDp[i][j - 1]) * val; } } } long result = maxDp[m - 1][n - 1]; if (result < 0) { return -1; } return (int) (result % MOD); }}Complexity
Time
O(m * n) - We iterate through each cell of the grid exactly once to compute the DP values.
Space
O(m * n) - We use two 2D arrays of the same size as the input grid to store the intermediate maximum and minimum products.
Trade-offs
Pros
Guaranteed to find the optimal solution.
Much more efficient than brute force, with a polynomial time complexity.
Handles all cases including positive, negative, and zero values correctly.
Cons
Uses
O(m*n)space, which can be substantial for very large grids, although it's acceptable for the given constraints.
This approach builds upon the standard dynamic programming solution but optimizes the space complexity. We observe that to compute the values for the current row, we only need the values from the previous row. Therefore, instead of storing the entire 2D DP tables, we can use 1D arrays to store the information for just one row at a time, reducing space from O(m*n) to O(n).
Algorithm
- Create two 1D arrays,
maxDpandminDp, of sizen. - Initialize for the first row:
- Set
maxDp[0] = minDp[0] = grid[0][0]. - For
jfrom 1 ton-1, calculatemaxDp[j]andminDp[j]based onmaxDp[j-1],minDp[j-1], andgrid[0][j].
- Set
- Iterate through subsequent rows (
ifrom 1 tom-1):- First, update
maxDp[0]andminDp[0]for the current rowibased on their previous values andgrid[i][0]. - Then, for
jfrom 1 ton-1, calculate the newmaxDp[j]andminDp[j]. - The new values for
(i, j)depend on the values from(i-1, j)(the oldmaxDp[j],minDp[j]) and(i, j-1)(the newmaxDp[j-1],minDp[j-1]).
- First, update
- After iterating through all rows,
maxDp[n-1]holds the final maximum product. - Return the result, handling the negative case and modulo operation as before.
Walkthrough
Instead of using 2D DP tables, we can use two 1D arrays, maxDp and minDp, each of size n (the number of columns). maxDp[j] will store the maximum product to reach the cell in the current row at column j.
We first initialize the arrays based on the first row of the grid. Then, we iterate from the second row to the last. For each row i, we update the maxDp and minDp arrays. When calculating the values for cell (i, j), we need the values from the cell above, (i-1, j), which are stored in maxDp[j] and minDp[j] from the previous iteration, and the values from the cell to the left, (i, j-1), which are the just-computed maxDp[j-1] and minDp[j-1] for the current row. This in-place update scheme allows us to use only O(n) extra space.
class Solution { public int maxProductPath(int[][] grid) { int m = grid.length; int n = grid[0].length; long[] maxDp = new long[n]; long[] minDp = new long[n]; int MOD = 1_000_000_007; // Initialize first cell maxDp[0] = minDp[0] = grid[0][0]; // Initialize first row for (int j = 1; j < n; j++) { long val = grid[0][j]; if (val >= 0) { maxDp[j] = maxDp[j - 1] * val; minDp[j] = minDp[j - 1] * val; } else { maxDp[j] = minDp[j - 1] * val; minDp[j] = maxDp[j - 1] * val; } } // Iterate through the rest of the rows for (int i = 1; i < m; i++) { // Update first column of the current row long val_col0 = grid[i][0]; long tempMax = maxDp[0]; maxDp[0] = (val_col0 >= 0) ? maxDp[0] * val_col0 : minDp[0] * val_col0; minDp[0] = (val_col0 >= 0) ? minDp[0] * val_col0 : tempMax * val_col0; // Update the rest of the row for (int j = 1; j < n; j++) { long val = grid[i][j]; long max_from_top = maxDp[j]; long min_from_top = minDp[j]; long max_from_left = maxDp[j - 1]; long min_from_left = minDp[j - 1]; if (val >= 0) { maxDp[j] = Math.max(max_from_top, max_from_left) * val; minDp[j] = Math.min(min_from_top, min_from_left) * val; } else { maxDp[j] = Math.min(min_from_top, min_from_left) * val; minDp[j] = Math.max(max_from_top, max_from_left) * val; } } } long result = maxDp[n - 1]; if (result < 0) { return -1; } return (int) (result % MOD); }}Complexity
Time
O(m * n) - The time complexity remains the same as the standard DP approach, as we still need to visit each cell once.
Space
O(n) - We use two 1D arrays of size `n` (the number of columns) to store the DP states for the current row.
Trade-offs
Pros
Optimal time complexity of
O(m*n).Highly efficient space complexity of
O(n)(orO(min(m,n))if we choose the smaller dimension).The most efficient solution for this problem.
Cons
The logic for in-place updates can be slightly more complex to implement correctly compared to the 2D DP approach.
Solutions
Solution
class Solution {private static final int MOD = (int)1 e9 + 7;public int maxProductPath(int[][] grid) { int m = grid.length; int n = grid[0].length; long[][][] dp = new long[m][n][2]; dp[0][0][0] = grid[0][0]; dp[0][0][1] = grid[0][0]; for (int i = 1; i < m; ++i) { dp[i][0][0] = dp[i - 1][0][0] * grid[i][0]; dp[i][0][1] = dp[i - 1][0][1] * grid[i][0]; } for (int j = 1; j < n; ++j) { dp[0][j][0] = dp[0][j - 1][0] * grid[0][j]; dp[0][j][1] = dp[0][j - 1][1] * grid[0][j]; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { int v = grid[i][j]; if (v >= 0) { dp[i][j][0] = Math.min(dp[i - 1][j][0], dp[i][j - 1][0]) * v; dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) * v; } else { dp[i][j][0] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) * v; dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i][j - 1][0]) * v; } } } long ans = dp[m - 1][n - 1][1]; return ans < 0 ? -1 : (int)(ans % MOD); }}using ll = long long ; const int mod = 1e9 + 7 ; class Solution { public: int maxProductPath ( vector < vector < int >>& grid ) { int m = grid . size (); int n = grid [ 0 ]. size (); vector < vector < vector < ll >>> dp ( m , vector < vector < ll >> ( n , vector < ll > ( 2 , grid [ 0 ][ 0 ]))); for ( int i = 1 ; i < m ; ++ i ) { dp [ i ][ 0 ][ 0 ] = dp [ i - 1 ][ 0 ][ 0 ] * grid [ i ][ 0 ]; dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 1 ] * grid [ i ][ 0 ]; } for ( int j = 1 ; j < n ; ++ j ) { dp [ 0 ][ j ][ 0 ] = dp [ 0 ][ j - 1 ][ 0 ] * grid [ 0 ][ j ]; dp [ 0 ][ j ][ 1 ] = dp [ 0 ][ j - 1 ][ 1 ] * grid [ 0 ][ j ]; } for ( int i = 1 ; i < m ; ++ i ) { for ( int j = 1 ; j < n ; ++ j ) { int 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 ; } } } ll ans = dp [ m - 1 ][ n - 1 ][ 1 ]; return ans < 0 ? - 1 : ( int ) ( ans % 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 % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.