Maximum Non Negative Product in a Matrix

Maximum Non Negative Product in a Matrix

What is this problem about?

The Maximum Non Negative Product in a Matrix coding problem gives you an m×n grid of integers. You must travel from the top-left to the bottom-right cell, only moving right or down. Along the path, multiply all values encountered. Find the maximum non-negative product of any such path, modulo 10^9 + 7. If no non-negative product path exists, return -1.

Why is this asked in interviews?

Amazon and Google use this problem because it combines a classic path DP with the tricky aspect of tracking both maximum and minimum products simultaneously. Negative numbers are key: multiplying two negatives gives a positive, so the current minimum might become the future maximum. This dual-tracking pattern is a hallmark of product-based DP problems.

Algorithmic pattern used

Dynamic Programming with dual tracking: At each cell, maintain both the maximum and minimum product of paths reaching that cell. The transition is: when the cell value is positive, max comes from multiplying max with the cell; min comes from multiplying min. When negative: max might come from previous min * negative (two negatives = positive), and vice versa. At the destination, if max_product >= 0, return max_product % MOD; otherwise return -1.

Be careful: take modulo only at the final step, not intermediately, since comparing products mid-computation requires actual (not modded) values.

Example explanation

Grid: [[1, -2, 1], [1, -2, 1], [3, -4, 1]] Paths (right/down only):

• Right, right, down, down: 1*(-2)1(-4)*1 = 8. Positive.
• Down, down, right, right: 113*(-4)*1 = -12. Negative.
• Various other paths...

Track max/min at each cell:

• (0,0): max=1, min=1.
• (0,1): max=1*(-2)=-2, min=-2. (Only from left.)
• (0,2): max=-2*1=-2, min=-2.
• At destination (2,2), trace all paths and find max non-negative product.

Answer = 8.

Common mistakes candidates make

• Taking modulo before comparison: Modular arithmetic destroys sign information. Store raw products for DP comparisons; only apply mod at the very end.
• Not swapping max/min when multiplying by negative: Forgetting to swap leads to incorrect DP values.
• Ignoring all-negative paths: If the only paths have negative products, return -1; don't return the modded value of a negative number.

Interview preparation tip

For the Array Matrix Dynamic Programming interview pattern, the "track max and min simultaneously" trick applies to any DP with multiplication over potentially negative values. Practice it first on 1D arrays (maximum product subarray), then extend to 2D grids. The swap-on-negative step is the critical implementation detail to master.