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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Non Negative Product in a Matrix

Difficulty: Medium

Problem Description

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 10^9 + 7. If the maximum product is negative, return -1.

Key Insights

  • The product can be affected by both positive and negative integers.
  • To maximize the product, we need to consider both the count of negative numbers and the presence of zeroes.
  • Dynamic programming can be employed to keep track of both the maximum and minimum products at each cell to handle negative products properly.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

To solve the problem, we will use dynamic programming. We will maintain two 2D arrays: one for tracking the maximum product (maxProduct) and another for the minimum product (minProduct) at each cell in the grid.

  1. Initialize maxProduct[0][0] and minProduct[0][0] with the value of grid[0][0].
  2. Iterate through each cell in the grid:
    • For each cell, calculate the maximum and minimum products that can be obtained by moving from the top or left cell.
    • If the current cell is negative, swap the maximum and minimum products because multiplying by a negative number will switch their roles.
    • If the current cell is zero, set both maximum and minimum products to zero.
  3. At the end, check the value in the bottom-right cell. If the maximum product is negative, return -1; otherwise, return the maximum product modulo 10^9 + 7.

Code Solutions

def maxProduct(grid):
    MOD = 10**9 + 7
    m, n = len(grid), len(grid[0])
    
    maxProduct = [[0] * n for _ in range(m)]
    minProduct = [[0] * n for _ in range(m)]
    
    maxProduct[0][0] = minProduct[0][0] = grid[0][0]
    
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                continue
            
            candidates = []
            if i > 0:
                candidates.append(maxProduct[i-1][j])
                candidates.append(minProduct[i-1][j])
            if j > 0:
                candidates.append(maxProduct[i][j-1])
                candidates.append(minProduct[i][j-1])
                
            if grid[i][j] == 0:
                maxProduct[i][j] = 0
                minProduct[i][j] = 0
            else:
                max_val = max(c * grid[i][j] for c in candidates)
                min_val = min(c * grid[i][j] for c in candidates)
                
                if grid[i][j] < 0:
                    maxProduct[i][j] = min_val
                    minProduct[i][j] = max_val
                else:
                    maxProduct[i][j] = max_val
                    minProduct[i][j] = min_val
    
    if maxProduct[m-1][n-1] < 0:
        return -1
    return maxProduct[m-1][n-1] % MOD
← Back to All Questions