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] <= 4This 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.
Java
C++
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.
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.
| 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. |
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,137 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