We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Non Negative Product in a Matrix

Number: 1716

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given an m x n matrix grid, find a path from the top-left corner to the bottom-right corner which yields the maximum non-negative product. In each step, you are allowed to move only right or down. The product of a path is the product of all numbers encountered along that path. Return the product modulo (10^9 + 7) if it is non-negative, or -1 if no path yields a non-negative product.

Key Insights

  • Use dynamic programming to track both the maximum and minimum product obtainable at each cell because negative numbers can flip the sign.
  • At every cell (i, j), the possible paths come from the top (i-1, j) or left (i, j-1). For each incoming value, calculate the new products by multiplying with grid[i][j].
  • Maintain a pair (maxProduct, minProduct) per cell because a very small (negative) product might become the maximum when multiplied by a negative number.
  • Special care is needed for cells that are 0, as they reset the product.
  • Finally, check the result at the bottom-right cell for non-negativity before applying the modulo.

Space and Time Complexity

Time Complexity: O(m * n) – We traverse each cell a constant number of times. Space Complexity: O(m * n) – Using a DP table to store the maximum and minimum products for each cell.

Solution

We use a dynamic programming approach where each cell (i, j) holds two values: the maximum product possible (dpMax) and the minimum product possible (dpMin) along any path reaching that cell. The reason for tracking both is that multiplying with a negative number can flip a minimum product into a maximum product.

For each cell, we derive the potential candidates from its top and left neighbors (if available) and then multiply them by the current cell value. Then, update the current cell’s dpMax with the maximum among these candidates and dpMin with the minimum. Special boundary handling for the first row and column is required since there’s only one direction from which they can be reached.

Finally, if the maximum product at the bottom-right cell is negative, return -1; otherwise, return the product modulo (10^9 + 7).

Code Solutions

MOD = 10**9 + 7

def maxProductPath(grid):
    m, n = len(grid), len(grid[0])
    # Initialize dp arrays for max and min product for each cell.
    dpMax = [[0] * n for _ in range(m)]
    dpMin = [[0] * n for _ in range(m)]
    
    # Base case: starting cell.
    dpMax[0][0] = dpMin[0][0] = grid[0][0]
    
    # First row.
    for j in range(1, n):
        dpMax[0][j] = dpMin[0][j] = dpMax[0][j-1] * grid[0][j]
    
    # First column.
    for i in range(1, m):
        dpMax[i][0] = dpMin[i][0] = dpMax[i-1][0] * grid[i][0]
    
    # Fill in the rest of the dp tables.
    for i in range(1, m):
        for j in range(1, n):
            curVal = grid[i][j]
            # Get candidates from the top cell.
            topMax = dpMax[i-1][j] * curVal
            topMin = dpMin[i-1][j] * curVal
            # Get candidates from the left cell.
            leftMax = dpMax[i][j-1] * curVal
            leftMin = dpMin[i][j-1] * curVal
            
            # Candidates array includes results from both sides.
            candidates = [topMax, topMin, leftMax, leftMin]
            dpMax[i][j] = max(candidates)
            dpMin[i][j] = min(candidates)
    
    # The bottom-right cell holds the result.
    result = dpMax[m-1][n-1]
    # If negative, no valid non-negative product path exists.
    if result < 0:
        return -1
    return result % MOD

# Example usage:
print(maxProductPath([[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]))  # Expected output: -1
print(maxProductPath([[1,-2,1],[1,-2,1],[3,-4,1]]))  # Expected output: 8
← Back to All Questions