Domain 2MediumMEDIUM

Maximum Non Negative Product in a Matrix

LeetCode problem 1594: Maximum Non Negative Product in a Matrix (medium).

Domain: medium•Updated: 2026-09-19
#Dynamic Programming#Greedy

Problem Breakdown

We are navigating a grid from the top-left (0, 0) to bottom-right (R-1, C-1), moving only Right or Down. The goal is to maximize the product of all numbers along this path such that the final result is non-negative (>= 0).

  • Inputs: A 2D integer matrix grid.
  • Outputs: An integer representing the maximum valid product modulo 109+710^9 + 7, or -1 if no non-negative product exists.
  • Constraints & Edge Cases:
    • Grid dimensions are small (R,C≤15R, C \le 15), but values can be negative (-4 to 4).
    • The modulo operation applies only at the very end; intermediate products must retain their true sign and magnitude because multiplying a large positive by a negative number requires knowing it was originally “large” (not just its remainder) or, more importantly, tracking whether we have accumulated enough negatives to flip back to positive.
    • Zeros: If any cell on the path is 0, the product becomes 0. Since 0≥00 \ge 0, this is a valid candidate for “maximum non-negative”.
    • Negative Start/End: A negative starting value doesn’t automatically disqualify us; we just need to multiply by another odd number of negatives later to make it positive (or even).

Intuition

A brute-force DFS approach exploring every path would have a complexity proportional to the binomial coefficient (R+CC)\binom{R+C}{C}. For 15×1515 \times 15, this is roughly (2814)\binom{28}{14}, which exceeds feasible limits for standard time constraints.

The key insight lies in how multiplication affects values:

  1. Positive numbers: Preserve the order of magnitude (larger previous product yields larger current).
  2. Negative numbers: Flip the sign and reverse the order (the smallest/most negative number becomes the largest positive after multiplying by a large negative, and vice versa).

Therefore, at any cell (i, j), we cannot just track one “maximum” value from previous cells. We must also track the “minimum” product reaching that cell. Why? Because if grid[i][j] is negative, our current minimum (most negative path so far) multiplied by this new negative number will become a large positive candidate for the maximum at (i+1, j) or (i, j+1).

Approach

We use Dynamic Programming where each cell stores two values: min_prod and max_prod, representing the smallest and largest possible products to reach that specific coordinate.

  1. Initialization: Create a DP table of size R×CR \times C. Initialize with zeros or handle base case (0, 0).
  2. Base Case: Set dp[0][0] directly from grid[0][0]. Both min and max are the same value initially.
  3. Iteration: Loop through rows ii from 1 to R-1 (handling row 0 separately) and columns jj. For each cell, look at valid neighbors: Top (i-1, j) and Left (i, j-1).
  4. Transition Logic:
    • Collect all potential products by multiplying grid[i][j] with the neighbor’s min/max values.
    • Update current cell’s min_prod to be the minimum of these candidates.
    • Update current cell’s max_prod to be the maximum of these candidates.
  5. Result: After filling the table, check dp[R-1][C-1]. If its max value is negative, return -1. Otherwise, return that value modulo 109+710^9 + 7.

Complexity Analysis

  • Time Complexity: O(R×C)O(R \times C). We visit each cell exactly once. Inside the loop, we perform constant number of arithmetic operations and comparisons (handling up to 2 neighbors).
  • Space Complexity: O(R×C)O(R \times C) for storing the DP table with min/max pairs per cell. This is optimal given the need to store state; it can be reduced to O(C)O(C) but isn’t necessary here due to small constraints.

Solution

from typing import List

class Solution:
    def maxProduct(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        
        # dp[i][j] stores a tuple (min_prod, max_prod) for cell (i, j)
        # We initialize with None to indicate unvisited or handle via logic below.
        # However, since we iterate sequentially, we can just build it row by col.
        
        min_max = [[None] * cols for _ in range(rows)]
        
        MOD = 10**9 + 7
        
        # Base case: Top-left corner
        start_val = grid[0][0]
        min_max[0][0] = (start_val, start_val)
        
        # Fill first row (can only come from left)
        for j in range(1, cols):
            prev_min, prev_max = min_max[0][j-1]
            curr_val = grid[0][j]
            
            candidates = [prev_min * curr_val, prev_max * curr_val]
            # Handle case where previous was None (shouldn't happen with loop logic)
            if not candidates: continue
            
            min_max[0][j] = (min(candidates), max(candidates))

        # Fill first col (can only come from top)
        for i in range(1, rows):
            prev_min, prev_max = min_max[i-1][0]
            curr_val = grid[i][0]
            
            candidates = [prev_min * curr_val, prev_max * curr_val]
            if not candidates: continue
            
            min_max[i][0] = (min(candidates), max(candidates))

        # Fill the rest of the matrix
        for i in range(1, rows):
            for j in range(1, cols):
                val = grid[i][j]
                
                top_min, top_max = min_max[i-1][j]
                left_min, left_max = min_max[i][j-1]
                
                # Collect all possible products from valid neighbors (top and left)
                candidates = [
                    top_min * val, 
                    top_max * val, 
                    left_min * val, 
                    left_max * val
                ]
                
                current_min = min(candidates)
                current_max = max(candidates)
                
                min_max[i][j] = (current_min, current_max)

        final_min, final_max = min_max[rows-1][cols-1]
        
        # If the maximum possible product is negative, no non-negative path exists.
        if final_max < 0:
            return -1
        
        return final_max % MOD

Edge Cases Handled

  • All Negative Paths: The logic tracks min and max. Even if all paths are negative, the code correctly identifies that no non-negative product exists by checking final_max < 0 at the end.
  • Zeros in Grid: If a path contains a zero, products become zero. Since 0≥00 \ge 0, this is valid. The logic naturally handles zeros as they propagate through multiplication (e.g., -2 * 0 = 0).
  • Start/End Negative Values: Handled by initializing dp[0][0] with the actual grid value, not forcing it to be positive or zero initially.
  • Modulo Timing: The modulo is strictly applied only at return time (final_max % MOD) rather than during intermediate steps, preserving sign information required for negative-to-positive flips later in the path.