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 , or
-1if no non-negative product exists. - Constraints & Edge Cases:
- Grid dimensions are small (), 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 , 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 . For , this is roughly , which exceeds feasible limits for standard time constraints.
The key insight lies in how multiplication affects values:
- Positive numbers: Preserve the order of magnitude (larger previous product yields larger current).
- 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.
- Initialization: Create a DP table of size . Initialize with zeros or handle base case
(0, 0). - Base Case: Set
dp[0][0]directly fromgrid[0][0]. Both min and max are the same value initially. - Iteration: Loop through rows from 1 to R-1 (handling row 0 separately) and columns . For each cell, look at valid neighbors: Top
(i-1, j)and Left(i, j-1). - Transition Logic:
- Collect all potential products by multiplying
grid[i][j]with the neighbor’s min/max values. - Update current cell’s
min_prodto be the minimum of these candidates. - Update current cell’s
max_prodto be the maximum of these candidates.
- Collect all potential products by multiplying
- Result: After filling the table, check
dp[R-1][C-1]. If its max value is negative, return-1. Otherwise, return that value modulo .
Complexity Analysis
- Time Complexity: . 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: 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 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
minandmax. Even if all paths are negative, the code correctly identifies that no non-negative product exists by checkingfinal_max < 0at the end. - Zeros in Grid: If a path contains a zero, products become zero. Since , 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.