Maximum Non Negative Product in a Matrix: Dual-Tracking Grid DP

You are given a rows x cols matrix grid. You start at the upper-left corner and can only move right or down. Along the way, you multiply together every cell value you visit. Return the maximum non-negative product among all paths from the top-left to the bottom-right, modulo 10^9 + 7. If the maximum product is negative, return -1.

This is LeetCode 1594: Maximum Non Negative Product in a Matrix. The twist that makes it interesting: the grid contains negative numbers. A single negative value can flip a huge positive product into a huge negative one, and two negatives can flip it right back. That means you cannot just track the maximum product at each cell. You need to track the minimum too.

Why this problem matters

Most grid DP problems ask you to minimize a cost or count paths. This one asks you to maximize a product, and the presence of negative numbers completely changes the game. In a sum-based problem like Minimum Path Sum, you only care about one value per cell: the best sum so far. But with products, a very negative number today could become a very positive number tomorrow if you multiply by another negative.

This "dual-tracking" idea, keeping both the best and worst value at each cell, shows up in several important problems. Maximum Product Subarray (LeetCode 152) uses the same technique in 1D. Once you understand why you need both max and min here, you will recognize the pattern instantly in those related problems.

The key insight

At every cell, you need two values: the maximum product of any path ending here, and the minimum product of any path ending here. Why the minimum? Because when you multiply by a negative number, the smallest (most negative) product flips to the largest, and the largest flips to the smallest.

The recurrence for cell (r, c) with value v:

1. Gather the max and min products from the cell above (r-1, c) and the cell to the left (r, c-1).
2. Multiply each of those four values by v.
3. The new max at (r, c) is the largest of all those products.
4. The new min at (r, c) is the smallest of all those products.

At the end, the answer is dp_max[rows-1][cols-1] if it is non-negative. Otherwise, return -1.

The solution

def maxProductPath(grid: list[list[int]]) -> int:
    MOD = 10**9 + 7
    rows, cols = len(grid), len(grid[0])

    dp_max = [[0] * cols for _ in range(rows)]
    dp_min = [[0] * cols for _ in range(rows)]

    dp_max[0][0] = dp_min[0][0] = grid[0][0]

    for c in range(1, cols):
        dp_max[0][c] = dp_max[0][c - 1] * grid[0][c]
        dp_min[0][c] = dp_min[0][c - 1] * grid[0][c]

    for r in range(1, rows):
        dp_max[r][0] = dp_max[r - 1][0] * grid[r][0]
        dp_min[r][0] = dp_min[r - 1][0] * grid[r][0]

    for r in range(1, rows):
        for c in range(1, cols):
            v = grid[r][c]
            candidates = [
                dp_max[r - 1][c] * v,
                dp_min[r - 1][c] * v,
                dp_max[r][c - 1] * v,
                dp_min[r][c - 1] * v,
            ]
            dp_max[r][c] = max(candidates)
            dp_min[r][c] = min(candidates)

    result = dp_max[rows - 1][cols - 1]
    if result < 0:
        return -1
    return result % MOD

Let's walk through what each piece does.

The two tables dp_max and dp_min store the maximum and minimum product of any path from (0,0) to each cell (r, c). Both tables are needed because a negative minimum can become a positive maximum after multiplication by a negative grid value.

The first row and first column are base cases. There is only one path to any cell in the first row (go right every step), so the max and min products are the same: the running product of all values along that row. The same logic applies to the first column.

For every other cell, we compute four candidate products: the max and min from above multiplied by the current cell value, and the max and min from the left multiplied by the current cell value. The new max is the largest of all four, and the new min is the smallest.

At the end, if the maximum product reaching the bottom-right corner is negative, no non-negative product path exists, and we return -1. Otherwise we return the result modulo 10^9 + 7.

Visual walkthrough

Let's trace through the grid step by step, watching how the max and min product tables get filled. The grid is:

 1  -2   1
 1  -2   1
 3  -4   1

Notice how at cell (1,1), the minimum product from above (-2) multiplied by the negative grid value (-2) produces the maximum product of 4. This is the dual-tracking pattern at work. Without the min table, you would have missed that flip and computed the wrong answer.

Complexity analysis

Time is O(m * n) where m is the number of rows and n is the number of columns. Each cell is visited exactly once, and the work per cell is constant (four multiplications, one max, one min).

Space is O(m * n) for the two DP tables. You could optimize to O(n) by keeping only the previous row, since each cell depends only on the cell above and the cell to the left. The logic is identical to the space optimization in Unique Paths.

The building blocks

1. Dual-tracking DP (max and min)

When a DP transition involves multiplication (or any operation where the sign can flip), a single "best so far" table is not enough. You need to track both the maximum and minimum values at each state. The candidates for the new max include the old min multiplied by a negative factor, and vice versa.

This pattern appears in Maximum Product Subarray (LeetCode 152), where you track the running max and min product of contiguous subarrays. It also shows up in any DP problem where values can be negative and the operation is multiplicative. The core idea is always the same: negatives flip ordering, so you need both extremes.

2. Grid DP with two predecessors

The structure of filling a 2D table where each cell depends on the cell above and the cell to the left is the standard grid DP pattern. You saw it in Unique Paths for counting and in Minimum Path Sum for addition. Here the operation is multiplication instead of addition, but the traversal order and dependency structure are identical: fill row by row, left to right, and each cell looks up and left.

Edge cases

• 1x1 grid: the product is just grid[0][0]. If it is negative, return -1.
• Grid contains a zero: any path through that zero has a product of zero, which is non-negative. So even if all other paths yield negative products, the answer is at least 0 (not -1).
• All positive values: the max product path goes through the largest values. The min table is irrelevant since no flips occur, but the algorithm still works correctly.
• Single row or single column: there is only one path. Compute the product directly. If negative, return -1.
• Very large products: intermediate products can overflow in languages with fixed-width integers. In Python this is not a concern because integers have arbitrary precision. Apply the modulo only at the very end, not during computation, because taking modulo mid-path would break the max/min comparisons.

From understanding to recall

You have seen why tracking both the maximum and minimum product at each cell is essential. A negative grid value flips the ordering, turning the worst path into the best. The dual-tracking pattern handles this cleanly: four candidates per cell, take the max for one table and the min for the other.

The tricky part under interview pressure is remembering why you need two tables. If you only track the max, you will miss the case where a negative minimum flips into a positive maximum. That is a subtle bug that does not show up in test cases with all-positive grids. It only appears when negatives are involved, which is exactly the constraint that makes this problem interesting.

Spaced repetition drills that recall. You write the dual-tracking recurrence from memory, initially after one day, then three days, then a week. Each time, you reconstruct the four-candidate logic and the sign-flip reasoning. After a few rounds, you see "product with negatives" in a problem statement and the dual-tracking pattern flows out automatically.

Related posts

• Unique Paths - The foundational grid DP problem that teaches the 2D table setup, row-by-row fill order, and space optimization
• Climbing Stairs - Your first DP problem, teaching the recursion-to-table pipeline that this problem builds on
• Dungeon Game - Another grid DP problem where you need to track non-obvious state (minimum health) through the grid, similar to tracking min products here

CodeBricks breaks problems like Maximum Non Negative Product in a Matrix into the dual-tracking DP and grid DP building blocks behind them, then drills each block independently with spaced repetition. You type the recurrence from scratch until it is automatic. When a product-based DP problem appears in your interview, you do not hesitate. You just write it.