Maximum Non Negative Product in a Matrix - Video Solutions

Problem 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.