Daily LeetCode - by Vítor Belim

Description

You are given a m x n matrix grid. Initially, you are located at the top-left corner (0, 0), and in each step, you can only move right or down in the matrix.

Among all possible paths starting from the top-left corner (0, 0) and ending in the bottom-right corner (m - 1, n - 1), find the path with the maximum non-negative product. The product of a path is the product of all integers in the grid cells visited along the path.

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

Notice that the modulo is performed after getting the maximum product.

Example 1:

Input: grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
Output: -1
Explanation: It is not possible to get non-negative product in the path from (0, 0) to (2, 2), so return -1.

Example 2:

Input: grid = [[1,-2,1],[1,-2,1],[3,-4,1]]
Output: 8
Explanation: Maximum non-negative product is shown (1 * 1 * -2 * -4 * 1 = 8).

Example 3:

Input: grid = [[1,3],[0,-4]]
Output: 0
Explanation: Maximum non-negative product is shown (1 * 0 * -4 = 0).

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 15
-4 <= grid[i][j] <= 4

Solutions

This code finds the maximum product of numbers along a path from the top-left to bottom-right corner of a grid, where you can only move right or down. It uses dynamic programming with two tables (min and max) to track both the smallest and largest products reaching each cell, since multiplying by a negative number can flip which is larger. It initializes both tables with the starting grid value, then fills the first row and column by considering only left or top neighbors, and fills the remaining cells by computing products from all four possible previous paths. Finally, it handles the edge case where all paths yield negative products by returning -1, otherwise it returns the maximum product found at the bottom-right corner, modulo 10^9 + 7 to prevent overflow.

Language: javascript(2026-03-23 09:48)DONE

CPU Performance91.67%

Memory Performance29.17%

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxProductPath = function(grid) {
    const m = grid.length;
    const n = grid[0].length;

    const min = Array.from({ length: m }, () => new Array(n).fill(1));
    min[0][0] = grid[0][0];
    const max = Array.from({ length: m }, () => new Array(n).fill(1));
    max[0][0] = grid[0][0];

    for (let row = 1; row < m; row++) {
        const minTop = grid[row][0] * min[row - 1][0];
        const maxTop = grid[row][0] * max[row - 1][0];

        min[row][0] = Math.min(minTop, maxTop);
        max[row][0] = Math.max(minTop, maxTop);
    }

    for (let col = 1; col < n; col++) {
        const minLeft = grid[0][col] * min[0][col - 1];
        const maxLeft = grid[0][col] * max[0][col - 1];

        min[0][col] = Math.min(minLeft, maxLeft);
        max[0][col] = Math.max(minLeft, maxLeft);
    }

    for (let row = 1; row < m; row++) {
        for (let col = 1; col < n; col++) {
            const minLeft = grid[row][col] * min[row][col - 1];
            const minTop = grid[row][col] * min[row - 1][col];
            const maxLeft = grid[row][col] * max[row][col - 1];
            const maxTop = grid[row][col] * max[row - 1][col];

            min[row][col] = Math.min(minLeft, minTop, maxLeft, maxTop);
            max[row][col] = Math.max(minLeft, minTop, maxLeft, maxTop);
        }
    }

    if (min[m - 1][n - 1] < 0 && max[m - 1][n - 1] < 0) {
        return -1;
    }

    return Math.max(min[m - 1][n - 1], max[m - 1][n - 1]) % (10 ** 9 + 7);
};

Description

Solutions

AI Explanation