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] <= 4Problem Overview: You are given an m x n grid containing positive, negative, and zero values. Starting from the top-left cell, you can only move right or down. The goal is to reach the bottom-right cell while maximizing the product of all visited values. If the maximum product is negative, return -1. Otherwise return the product modulo 1e9 + 7. The challenge is handling negative numbers, because multiplying by a negative flips the sign of the product.
Approach 1: Recursive DFS with Memoization (O(m*n) time, O(m*n) space)
This approach explores all valid paths using depth-first search while caching results to avoid recomputation. At each cell, recursively compute the best possible product from the right and down neighbors. Because values can be negative, you must track both the minimum and maximum product reaching a cell. A negative number can turn the smallest product into the largest after multiplication. Memoization stores results for each cell so the recursion does not recompute overlapping subproblems. This technique works well for explaining the state transition and mirrors the recurrence directly, but recursion depth and function call overhead make it less practical than an iterative DP solution.
Approach 2: Dynamic Programming with Min/Max Path Products (O(m*n) time, O(m*n) space)
The optimal approach uses dynamic programming on the grid. Instead of storing a single value per cell, maintain two DP tables: maxProd[i][j] and minProd[i][j]. These represent the maximum and minimum product achievable when reaching cell (i, j). The reason for two states is that multiplying by a negative value flips signs, so a previously small negative product may become the largest positive product.
For each cell, compute candidate values from the top and left neighbors. Multiply the current cell value with both the neighbor's min and max products. Take the maximum of these results for maxProd and the minimum for minProd. This transition ensures all sign combinations are handled correctly. The grid is processed row by row, similar to standard matrix DP problems. The final answer is maxProd[m-1][n-1]. If it is negative, return -1; otherwise apply the required modulo.
This solution runs in linear time relative to the number of cells and only performs constant work per transition. The idea of tracking both minimum and maximum states appears frequently in array and DP problems involving products or negative numbers.
Recommended for interviews: The dynamic programming approach with min/max tracking is what interviewers expect. It shows you understand how negative values affect multiplicative paths and how to model that with DP states. The recursive memoized version demonstrates the recurrence clearly, but the iterative DP solution is cleaner, faster, and easier to reason about in production code.
This approach involves tracking the maximum and minimum products achievable at each cell. We initialize two matrices, 'max_product' and 'min_product', both the same size as the grid. These matrices store the maximum and minimum product paths to each cell. We fill these matrices by considering the best possible moves from the left and above to reach each cell. Finally, we compare the maximum product at the bottom-right corner to determine the result.
This code starts by initializing two matrices to track the minimum and maximum products possible at each cell. It iterates through the grid, updating these matrices based on the best possible ways to enter each cell from the left or above it. The result is the maximum product at the bottom-right corner modulo 10^9 + 7 if it is non-negative; otherwise, it returns -1.
Time complexity: O(m * n) where m and n are the dimensions of the grid.
Space complexity: O(m * n) for the additional storage of the minimum and maximum product matrices.
This approach uses a recursive depth-first search combined with memoization to explore all possible paths from the top-left to the bottom-right. The recursion tracks the product along each possible path, storing previously calculated products for revisitation efficiency through a memoization table.
This JavaScript solution leverages DFS for exploring grid paths recursively. By storing maximum and minimum path products in a memoization structure at each step, repetitive calculations are reduced, which enhances performance.
JavaScript
C#
Time complexity: Expected to be close to O(m * n) due to memoization, which prevents re-evaluating already computed results.
Space complexity: O(m * n) for memoization storage.
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 10^9 + 7. If f[m - 1][n - 1][1] is less than 0, return -1.
The time complexity is O(m times n) and the space complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Min/Max Path Products | Time complexity: O(m * n) where m and n are the dimensions of the grid. |
| Recursive DFS with Memoization | Time complexity: Expected to be close to O(m * n) due to memoization, which prevents re-evaluating already computed results. |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS with Memoization | O(m*n) | O(m*n) | Useful for understanding the recurrence and exploring paths recursively |
| Dynamic Programming with Min/Max Path Products | O(m*n) | O(m*n) | Best general solution for grids with positive and negative numbers |
Maximum Non Negative Product in a Matrix | Recursion | Memo | Bottom Up | Leetcode 1594 |DP On Grids • codestorywithMIK • 15,381 views views
Watch 9 more video solutions →Practice Maximum Non Negative Product in a Matrix with our built-in code editor and test cases.
Practice on FleetCode