LeetCode 1594 - Maximum Non Negative Product in a Matrix

LeetCode Problem 1594

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem asks us to navigate a m x n integer matrix grid from the top-left corner (0, 0) to the bottom-right corner (m - 1, n - 1), moving only right or down at each step. Along the path, we multiply all the integers we pass through, and our goal is to maximize the product while ensuring it is non-negative. If no non-negative product exists, we return -1. If a non-negative product exists, we return it modulo 10^9 + 7.

The input is a matrix where each element ranges from -4 to 4, and both dimensions are small (1 <= m, n <= 15), which suggests that solutions with higher computational complexity could be feasible but should ideally be polynomial. The problem is complicated by the presence of negative numbers: the product of a path could switch between negative and positive depending on the number of negative values encountered. This requires careful tracking of both the maximum and minimum products at each cell.

Important edge cases include matrices that contain zeros, matrices where all paths result in a negative product, and matrices with a single row or column. The constraints guarantee that the matrix is non-empty and small enough for a dynamic programming solution.

Approaches

The brute-force approach would explore all possible paths recursively, calculating the product for each path and then selecting the maximum non-negative result. This is correct but computationally infeasible because the number of paths is exponential: for an m x n grid, there are C(m+n-2, m-1) paths, which grows extremely quickly even for modest values of m and n.

The optimal approach is to use dynamic programming. The key observation is that at any cell (i, j), the maximum non-negative product can result either from a positive product from the previous cells or by multiplying two negative products. Therefore, we need to maintain both the maximum and minimum product up to each cell. The transitions are simple: to compute (i, j), we consider the products coming from the top (i-1, j) and left (i, j-1), updating both the maximum and minimum products at that cell. This ensures that we always have the correct product regardless of the signs of the numbers encountered along the path.

Algorithm Walkthrough

1. Initialization: Create two matrices, max_dp and min_dp, of the same size as grid to store the maximum and minimum product achievable at each cell. Initialize max_dp[0][0] = min_dp[0][0] = grid[0][0].
2. First row and column: For the first row (0, j) and first column (i, 0), the only possible path is straight from the start. Update max_dp and min_dp by multiplying the previous cell's value by the current cell.
3. Dynamic programming iteration: For each cell (i, j) starting from (1,1), compute the potential maximum and minimum products by considering the top (i-1, j) and left (i, j-1) cells:

• Calculate all four possible products: grid[i][j] * max_dp[i-1][j], grid[i][j] * min_dp[i-1][j], grid[i][j] * max_dp[i][j-1], grid[i][j] * min_dp[i][j-1].
• Update max_dp[i][j] as the maximum of these four values.
• Update min_dp[i][j] as the minimum of these four values.

4. Result extraction: The final result is max_dp[m-1][n-1]. If it is negative, return -1. Otherwise, return it modulo 10^9 + 7.

Why it works: By maintaining both the maximum and minimum products at each cell, the algorithm correctly handles negative numbers and zeros. This ensures that the optimal path is captured even when two negative numbers multiply to form a positive product. The DP ensures that we only compute each cell once, making it efficient.

Python Solution

from typing import List

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        MOD = 10**9 + 7
        m, n = len(grid), len(grid[0])
        
        max_dp = [[0] * n for _ in range(m)]
        min_dp = [[0] * n for _ in range(m)]
        
        max_dp[0][0] = min_dp[0][0] = grid[0][0]
        
        # Initialize first row
        for j in range(1, n):
            max_dp[0][j] = max_dp[0][j-1] * grid[0][j]
            min_dp[0][j] = max_dp[0][j]
        
        # Initialize first column
        for i in range(1, m):
            max_dp[i][0] = max_dp[i-1][0] * grid[i][0]
            min_dp[i][0] = max_dp[i][0]
        
        # Fill DP table
        for i in range(1, m):
            for j in range(1, n):
                candidates = [
                    grid[i][j] * max_dp[i-1][j],
                    grid[i][j] * min_dp[i-1][j],
                    grid[i][j] * max_dp[i][j-1],
                    grid[i][j] * min_dp[i][j-1]
                ]
                max_dp[i][j] = max(candidates)
                min_dp[i][j] = min(candidates)
        
        return max_dp[m-1][n-1] % MOD if max_dp[m-1][n-1] >= 0 else -1

The implementation first initializes the DP tables for the first row and column since there is only one possible path to each of these cells. It then iterates through the rest of the grid, considering all possible previous paths to each cell. The use of max and min ensures that negative values are correctly handled.

Go Solution

func maxProductPath(grid [][]int) int {
    const MOD = 1_000_000_007
    m, n := len(grid), len(grid[0])
    
    maxDP := make([][]int, m)
    minDP := make([][]int, m)
    for i := 0; i < m; i++ {
        maxDP[i] = make([]int, n)
        minDP[i] = make([]int, n)
    }
    
    maxDP[0][0], minDP[0][0] = grid[0][0], grid[0][0]
    
    for j := 1; j < n; j++ {
        maxDP[0][j] = maxDP[0][j-1] * grid[0][j]
        minDP[0][j] = maxDP[0][j]
    }
    
    for i := 1; i < m; i++ {
        maxDP[i][0] = maxDP[i-1][0] * grid[i][0]
        minDP[i][0] = maxDP[i][0]
    }
    
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            candidates := []int{
                grid[i][j] * maxDP[i-1][j],
                grid[i][j] * minDP[i-1][j],
                grid[i][j] * maxDP[i][j-1],
                grid[i][j] * minDP[i][j-1],
            }
            maxDP[i][j] = max(candidates...)
            minDP[i][j] = min(candidates...)
        }
    }
    
    if maxDP[m-1][n-1] < 0 {
        return -1
    }
    return maxDP[m-1][n-1] % MOD
}

func max(nums ...int) int {
    res := nums[0]
    for _, n := range nums[1:] {
        if n > res {
            res = n
        }
    }
    return res
}

func min(nums ...int) int {
    res := nums[0]
    for _, n := range nums[1:] {
        if n < res {
            res = n
        }
    }
    return res
}

The Go implementation mirrors the Python logic. Since Go does not support max and min for slices by default, helper functions are defined. The DP arrays are slices of slices, initialized explicitly.

Worked Examples

Example 1: grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]

Initial cell: max = -1, min = -1

First row: max = [-1, 2, -6], min = [-1, 2, -6]

First column: max