Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A negative cell can turn the smallest, most negative incoming product into the largest outgoing product. Keeping only a maximum loses that possibility, so every cell must retain both minimum and maximum reachable products.

Approach

Initialize both tables at the top-left value. Boundary cells have a single path, so extend that product directly. At an interior cell, multiply its value by both extremes from above and both extremes from the left, then retain the smallest and largest of the four candidates. These extremes suffice because multiplication either preserves or reverses order. At the destination, return -1 if its maximum is negative; otherwise return that exact maximum modulo 10^9 + 7. Apply the modulus only at the end, and allow zero as a valid nonnegative result.

class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n = len(grid)
        m = len(grid[0])
        mn = [[0] * m for _ in range(n)]
        mx = [[0] * m for _ in range(n)]
        mn[0][0], mx[0][0] = grid[0][0], grid[0][0]

        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    continue
                if i == 0:
                    mn[i][j] = mn[i][j - 1] * grid[i][j]
                    mx[i][j] = mx[i][j - 1] * grid[i][j]
                elif j == 0:
                    mn[i][j] = mn[i - 1][j] * grid[i][j]
                    mx[i][j] = mx[i - 1][j] * grid[i][j]
                else:
                    a = mn[i - 1][j] * grid[i][j]
                    b = mx[i - 1][j] * grid[i][j]
                    c = mn[i][j - 1] * grid[i][j]
                    d = mx[i][j - 1] * grid[i][j]
                    mn[i][j] = min(a, b, c, d)
                    mx[i][j] = max(a, b, c, d)

        res = mx[-1][-1]
        return res % MOD if res >= 0 else -1

Complexity analysis

For an R × C grid, both displayed implementations compute each min/max product-table cell once. In the standard unit-cost model, time and auxiliary space are O(RC). Exact products contain O(R + C) bits, so a bit-level model gives O(RC(R + C)) time and O(RC(R + C)) stored bits.