Problem Statement in English

You’re given a matrix of integers. You have to find the maximum non-negative product of a path from the top-left corner to the bottom-right corner. You can only move down or right.

Return the maximum non-negative product modulo $10^9 + 7$. If the maximum product is negative, return -1.

Approach

So the first idea that you need to have in this problem is that you need to keep track of both the maximum and minimum product at each cell. This is because a negative number can turn a minimum product into a maximum product and vice versa.

Once we’re past that, it’s a DP.

Just one nice implementation detail is that to avoid having to deal with paths that are out of bounds or don’t result in the bottom-right corner, is that we can have a candidates list that we can extend with the products from the down and right paths. Then we can just take the max and min of that list to get the maximum and minimum product at the current cell.

And if we reach the bottom-right corner, we can just return the value of that cell as both the maximum and minimum product.

And we’re done!

Solution in Python


class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int:
        M = len(grid)
        N = len(grid[0])

        @cache
        def dfs(i, j):
            if i == M - 1 and j == N - 1:
                return (grid[i][j], grid[i][j])

            this = grid[i][j]
            candidates = []

            if i + 1 < M:
                downPos, downNeg = dfs(i + 1, j)
                candidates.extend([this * downPos,this * downNeg,])

            if j + 1 < N:
                rightPos, rightNeg = dfs(i, j + 1)
                candidates.extend([this * rightPos,this * rightNeg,])

            return (max(candidates), min(candidates))

        resPos, _ = dfs(0, 0)

        if resPos < 0:
            return -1
        return resPos % (10 ** 9 + 7)

Complexity

  • Time: $O(M \times N)$
    Since we visit each cell at most once.

  • Space: $O(M \times N)$
    Since we store the results of each cell in the cache.

Mistakes I Made

I messed up the cnadidates list and forgot to include the products of the down and right paths. This resulted in incorrect results for some test cases.

And we are done.