Maximum Non Negative Product in a Matrix LeetCode solution in Python

1
# Runtime: 63 ms (Top 56.0%) | Memory: 16.84 MB (Top 17.4%)
2

3

4
class Solution:
5
    def maxProductPath(self, grid: List[List[int]]) -> int:
6
        m, n = len(grid), len(grid[0])
7

8
        @lru_cache(None)
9
        def fn(i, j):
10
            """Return maximum & minimum products ending at (i, j)."""
11
            if i == 0 and j == 0:
12
                return grid[0][0], grid[0][0]
13
            if i < 0 or j < 0:
14
                return -inf, inf
15
            if grid[i][j] == 0:
16
                return 0, 0
17
            mx1, mn1 = fn(i - 1, j)  # from top
18
            mx2, mn2 = fn(i, j - 1)  # from left
19
            mx, mn = max(mx1, mx2) * grid[i][j], min(mn1, mn2) * grid[i][j]
20
            return (mx, mn) if grid[i][j] > 0 else (mn, mx)
21

22
        mx, _ = fn(m - 1, n - 1)
23
        return -1 if mx < 0 else mx % 1_000_000_007