1594. Maximum Non Negative Product in a Matrix


Problem Description

In this problem, you are given a two-dimensional matrix where each cell contains an integer. Starting from the top-left corner of the matrix (0, 0), you need to find a path that leads you to the bottom-right corner (m - 1, n - 1). The only allowed moves are to the right or down from your current position.

Your goal is to find the path that results in the maximum non-negative product of all the numbers on that path. The product of a path is calculated by multiplying all the values of the cells visited on that path. Finally, you'll need to return this maximum product modulo 10^9 + 7. If no such non-negative product exists, you should return -1.

Intuition

The problem can be tackled using dynamic programming. The key observation is that the maximum product at any given cell will either be the result of multiplying the maximum or the minimum product up to that point by the value of the current cell. This is because multiplying a negative value by another negative value could give a positive product, which might be the maximum.

We use a 3-dimensional dynamic programming (dp) array where each cell at (i, j) holds two values:

  1. dp[i][j][0]: The minimum product to reach cell (i, j). This is important to keep track of because a negative minimum product can become a positive product if we multiply it by a negative number in the grid.
  2. dp[i][j][1]: The maximum product to reach cell (i, j).

For the first row and first column, the maximum and minimum products can only come from one direction, so we just multiply the current cell value by the value in the dp array of the previous cell in the same row or column.

As we iterate through the inner cells of the grid, we calculate the possible minimum and maximum products using the previously filled cells above and to the left. We calculate the new values to store by considering the current cell's value:

  • If the current cell's value is non-negative, we achieve the minimum product by multiplying the cell's value by the minimum of the two possible pre-calculated minimum products. We obtain the maximum product by multiplying the cell's value by the maximum of the two possible pre-calculated maximum products.
  • If the cell value is negative, the minimum product could result in the largest product (if later multiplied by another negative value), hence we take the maximum of the pre-calculated maximum products and multiply it by the cell's value. Conversely, the maximum value is achieved by taking the minimum of the pre-calculated minimum products and multiplying by the cell's value.

After calculating dp values for the entire grid, we look at the maximum product of the last cell. If the maximum is negative, return -1. Otherwise, return the maximum product modulo 10^9 + 7.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution to this problem involves understanding the intricacies of dynamic programming and how to effectively handle both positive and negative numbers while searching for the maximum product path.

The algorithm uses a 3-dimensional dynamic programming array called dp. Here's the step-by-step breakdown:

  1. Initialization:

    • The dp array is initialized with a size of m x n x 2, where m and n are the dimensions of the input grid. Each cell in dp will hold two numbers: the minimum and maximum product up to that point in the grid.
    • The first cell, dp[0][0], is initialized with the value of the first cell of the grid, grid[0][0], as both the minimum and maximum, since there's only one number in the path at this point.
  2. Filling the first row and column:

    • Each cell in the first row and column can only be reached from one direction. Thus, for the first row, we iterate over j from 1 to n, and set dp[0][j] equal to the product of dp[0][j - 1][0] (the previous cell) and grid[0][j]. We do the same for the first column, iterating over i from 1 to m, setting each dp[i][0] according to the product of the previous cell and the current grid value.
  3. Filling the rest of the dp array:

    • We iterate over the cells of the grid starting from (1, 1) and for each cell at (i, j), we calculate the minimum and maximum product paths to that point. This involves comparisons and multiplications using the values from the top (i - 1, j) and left (i, j - 1) cells.
    • The crux of the approach: If grid[i][j] is non-negative, we:
      • Find dp[i][j][0] (min product) by multiplying grid[i][j] with the smaller of either dp[i - 1][j][0] (above) or dp[i][j - 1][0] (left).
      • Calculate dp[i][j][1] (max product) by multiplying grid[i][j] with the larger of either dp[i - 1][j][1] (above) or dp[i][j - 1][1] (left). If grid[i][j] is negative, we switch the above, since minimum times a negative can lead to a maximum product, and vice versa:
      • Calculate dp[i][j][0] (min product) by multiplying grid[i][j] with the larger of either dp[i - 1][j][1] (above) or dp[i][j - 1][1] (left).
      • Find dp[i][j][1] (max product) by multiplying grid[i][j] with the smaller of either dp[i - 1][j][0] (above) or dp[i][j - 1][0] (left).
  4. Getting the result:

    • After filling in the entire dp array, we look at the bottom-right corner (last cell) of the grid dp[m - 1][n - 1]. Specifically, we're interested in the maximum product path, which is stored in dp[m - 1][n - 1][1].
    • If the maximum product path is negative, this indicates there are no non-negative product paths to the bottom-right corner, and thus we return -1.
    • If the maximum product is non-negative, we return the maximum product modulo 10^9 + 7 as per the problem's requirement.

The solution demonstrates the utilization of dynamic programming to maintain and compare potential product paths through a grid with both positive and negative integers, ensuring the computations adhere to the maximum non-negative product principle.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example Walkthrough

Let's consider a small 3x3 matrix as an example to illustrate the solution approach:

1Grid:
2[1,  -2, 1]
3[1,   3, -2]
4[-1, -2, 4]

Here's a step-by-step application of the solution approach:

  1. Initialization:

    • Initialize dp as a 3-dimensional array with the dimensions of the grid and an extra dimension to hold both minimum and maximum products. For our 3x3 grid, dp will have dimensions 3 x 3 x 2.
    • Set dp[0][0] to [1, 1] since the first cell of the grid is 1, and there's only one path with one cell at the starting point.
  2. Filling the first row and column:

    • First row: Iterate over j from 1 to 2.
      • For j = 1, dp[0][1] is initialized as [1 * (-2), 1 * (-2)] => [-2, -2].
      • For j = 2, dp[0][2] becomes [-2 * 1, -2 * 1] => [-2, -2].
    • First column: Iterate over i from 1 to 2.
      • For i = 1, dp[1][0] is [1 * 1, 1 * 1] => [1, 1].
      • For i = 2, dp[2][0] becomes [1 * (-1), 1 * (-1)] => [-1, -1].
  3. Filling the rest of the dp array:

    • Now, we iterate over the inner cells starting from (1, 1).
    • For i = 1 and j = 1 (grid[1][1] is 3, a positive value):
      • Calculate minimum as min(dp[0][1][0], dp[1][0][0]) * 3 => min(-2, 1) * 3 => 1 * 3 => 3.
      • Calculate maximum as max(dp[0][1][1], dp[1][0][1]) * 3 => max(-2, 1) * 3 => 1 * 3 => 3.
      • Set dp[1][1] to [3, 3].
    • For i = 1 and j = 2 (grid[1][2] is -2, a negative value):
      • Calculate the minimum as max(dp[0][2][1], dp[1][1][1]) * -2 => max(-2, 3) * -2 => 3 * -2 => -6.
      • Calculate the maximum as min(dp[0][2][0], dp[1][1][0]) * -2 => min(-2, 3) * -2 => -2 * -2 => 4.
      • Set dp[1][2] to [-6, 4].
    • For i = 2 and j = 1 (grid[2][1] is -2, a negative value):
      • Minimum: max(dp[1][1][1], dp[2][0][1]) * -2 => max(3, -1) * -2 => 3 * -2 => -6.
      • Maximum: min(dp[1][1][0], dp[2][0][0]) * -2 => min(3, -1) * -2 => -1 * -2 => 2.
      • Set dp[2][1] to [-6, 2].
    • For i = 2 and j = 2 (grid[2][2] is 4, a positive value):
      • Minimum: min(dp[1][2][0], dp[2][1][0]) * 4 => min(-6, -6) * 4 => -6 * 4 => -24.
      • Maximum: max(dp[1][2][1], dp[2][1][1]) * 4 => max(4, 2) * 4 => 4 * 4 => 16.
      • Set dp[2][2] to [-24, 16].
  4. Getting the result:

    • Looking at the last cell dp[2][2], we have the maximum product as 16. Since it is non-negative, we return 16 % (10^9 + 7), which is 16.

This walk-through demonstrates how the dynamic programming array is filled out in order to maximize the product path from the top-left to the bottom-right of the grid.

Solution Implementation

1class Solution:
2    def maxProductPath(self, grid: List[List[int]]) -> int:
3        # Get the dimensions of the grid.
4        rows, cols = len(grid), len(grid[0])
5        # Define the modulo value for the final result.
6        mod = 10**9 + 7
7        # Initialize a 3D dp array where dp[i][j] will store the min and max product up to (i, j).
8        dp = [[[0] * 2 for _ in range(cols)] for _ in range(rows)]
9        dp[0][0] = [grid[0][0], grid[0][0]] # Base case: min and max products for the starting cell.
10
11        # Initialize the first column of the grid.
12        for i in range(1, rows):
13            dp[i][0] = [dp[i - 1][0][0] * grid[i][0]] * 2 # Copy min and max since they are the same here.
14
15        # Initialize the first row of the grid.
16        for j in range(1, cols):
17            dp[0][j] = [dp[0][j - 1][0] * grid[0][j]] * 2 # Copy min and max since they are the same here.
18
19        # Compute the min and max products for the whole grid.
20        for i in range(1, rows):
21            for j in range(1, cols):
22                value = grid[i][j]
23                if value >= 0:
24                    # The current value is non-negative, so the min product is the min of min products from above and left cells.
25                    dp[i][j][0] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * value
26                    # The max product is the max of max products from above and left cells.
27                    dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * value
28                else:
29                    # The current value is negative, so the min product becomes the max product from above/left, and vice versa.
30                    dp[i][j][0] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * value
31                    dp[i][j][1] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * value
32
33        # The answer is the max product for the bottom-right cell.
34        ans = dp[-1][-1][1]
35      
36        # If the answer is negative, there is no non-negative product path.
37        return -1 if ans < 0 else ans % mod # Return the result modulo 10^9+7.
38
1class Solution {
2    // Define modulus for the result to keep the result within integer range.
3    private static final int MOD = (int) 1e9 + 7;
4
5    // Function to calculate the maximum product of paths.
6    public int maxProductPath(int[][] grid) {
7        // Get the dimensions of the grid.
8        int rows = grid.length;
9        int cols = grid[0].length;
10      
11        // 3D DP array to store the min and max product up to each cell.
12        // dp[i][j][0] will store the minimum product up to grid[i][j],
13        // dp[i][j][1] will store the maximum product.
14        long[][][] dp = new long[rows][cols][2];
15      
16        // Initialize the first cell of the grid.
17        dp[0][0][0] = grid[0][0];
18        dp[0][0][1] = grid[0][0];
19      
20        // Initialize the first column of the grid.
21        for (int i = 1; i < rows; ++i) {
22            dp[i][0][0] = dp[i - 1][0][0] * grid[i][0];
23            dp[i][0][1] = dp[i - 1][0][1] * grid[i][0];
24        }
25      
26        // Initialize the first row of the grid.
27        for (int j = 1; j < cols; ++j) {
28            dp[0][j][0] = dp[0][j - 1][0] * grid[0][j];
29            dp[0][j][1] = dp[0][j - 1][1] * grid[0][j];
30        }
31      
32        // Fill the DP table.
33        for (int i = 1; i < rows; ++i) {
34            for (int j = 1; j < cols; ++j) {
35                int value = grid[i][j];
36              
37                // When the current value is non-negative.
38                if (value >= 0) {
39                    dp[i][j][0] = Math.min(dp[i - 1][j][0], dp[i][j - 1][0]) * value;
40                    dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) * value;
41                } else {
42                    // When the current value is negative, flip the min and max.
43                    dp[i][j][0] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) * value;
44                    dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i][j - 1][0]) * value;
45                }
46            }
47        }
48      
49        // Get the max product from the bottom-right cell of the grid.
50        long maxProduct = dp[rows - 1][cols - 1][1];
51      
52        // If the max product is negative, return -1, otherwise return the max product modulo MOD.
53        return maxProduct < 0 ? -1 : (int) (maxProduct % MOD);
54    }
55}
56
1using ll = long long;
2const int MOD = 1e9 + 7;
3
4class Solution {
5public:
6    // Function to find the maximum product path in a given grid
7    int maxProductPath(vector<vector<int>>& grid) {
8        int rows = grid.size();          // Number of rows in the grid
9        int cols = grid[0].size();       // Number of columns in the grid
10        // Creating a 3D vector to store the minimum and maximum products
11        // dp[row][col][0] for minimum product up to (row, col)
12        // dp[row][col][1] for maximum product up to (row, col)
13        vector<vector<vector<ll>>> dp(rows, vector<vector<ll>>(cols, vector<ll>(2, 0)));
14      
15        // Initialize the first cell with the value in the grid
16        dp[0][0][0] = dp[0][0][1] = grid[0][0];
17
18        // Fill the first column (all rows, column 0)
19        for (int i = 1; i < rows; ++i) {
20            dp[i][0][0] = dp[i - 1][0][0] * grid[i][0]; // Product could be positive or negative
21            dp[i][0][1] = dp[i][0][0]; // Both min and max are the same for the first column
22        }
23
24        // Fill the first row (row 0, all columns)
25        for (int j = 1; j < cols; ++j) {
26            dp[0][j][0] = dp[0][j - 1][0] * grid[0][j]; // Product could be positive or negative
27            dp[0][j][1] = dp[0][j][0]; // Both min and max are the same for the first row
28        }
29
30        // Calculate dp values for the rest of the grid
31        for (int i = 1; i < rows; ++i) {
32            for (int j = 1; j < cols; ++j) {
33                int value = grid[i][j];
34                if (value >= 0) {
35                    // If current cell value is non-negative
36                    dp[i][j][0] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * value;
37                    dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * value;
38                } else {
39                    // If current cell value is negative, min and max swap
40                    dp[i][j][0] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * value;
41                    dp[i][j][1] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * value;
42                }
43            }
44        }
45
46        // The final result is the maximum product path to the bottom-right cell
47        ll result = dp[rows - 1][cols - 1][1];
48        // If the result is negative, return -1, else return the result modulo MOD
49        return result < 0 ? -1 : static_cast<int>(result % MOD);
50    }
51};
52
1type ll = bigint; // Using TypeScript alias for bigint
2const MOD: ll = BigInt(1e9 + 7); // MOD value as a bigint
3
4// Function to find the maximum product path in a given grid
5function maxProductPath(grid: number[][]): number {
6    const rows = grid.length; // Number of rows in the grid
7    const cols = grid[0].length; // Number of columns in the grid
8    // Create a 3D array to store the minimum and maximum products
9    const dp: ll[][][] = Array.from({ length: rows }, () =>
10        Array.from({ length: cols }, () => Array(2).fill(BigInt(0)))
11    );
12
13    // Initialize the first cell with the value in the grid
14    dp[0][0][0] = dp[0][0][1] = BigInt(grid[0][0]);
15
16    // Fill in the first column (all rows, column 0)
17    for (let i = 1; i < rows; ++i) {
18        dp[i][0][0] = dp[i - 1][0][0] * BigInt(grid[i][0]);
19        dp[i][0][1] = dp[i][0][0]; // Both min and max are the same for the first column
20    }
21
22    // Fill in the first row (row 0, all columns)
23    for (let j = 1; j < cols; ++j) {
24        dp[0][j][0] = dp[0][j - 1][0] * BigInt(grid[0][j]);
25        dp[0][j][1] = dp[0][j][0]; // Both min and max are the same for the first row
26    }
27
28    // Calculate dp values for the rest of the grid
29    for (let i = 1; i < rows; ++i) {
30        for (let j = 1; j < cols; ++j) {
31            const value: ll = BigInt(grid[i][j]);
32            if (value >= BigInt(0)) {
33                // If current cell value is non-negative
34                dp[i][j][0] = llMin(dp[i - 1][j][0], dp[i][j - 1][0]) * value;
35                dp[i][j][1] = llMax(dp[i - 1][j][1], dp[i][j - 1][1]) * value;
36            } else {
37                // If current cell value is negative, min and max swap
38                dp[i][j][0] = llMax(dp[i - 1][j][1], dp[i][j - 1][1]) * value;
39                dp[i][j][1] = llMin(dp[i - 1][j][0], dp[i][j - 1][0]) * value;
40            }
41        }
42    }
43
44    // The final result is the maximum product path to the bottom-right cell
45    const result: ll = dp[rows - 1][cols - 1][1];
46    // If the result is negative, return -1, else return the result modulo MOD
47    return result < BigInt(0) ? -1 : Number(result % MOD);
48}
49
50// Helper function to find the minimum of two bigints
51function llMin(a: ll, b: ll): ll {
52    return a < b ? a : b;
53}
54
55// Helper function to find the maximum of two bigints
56function llMax(a: ll, b: ll): ll {
57    return a > b ? a : b;
58}
59

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the nested loops that iterate over each cell of the matrix grid. Since there are two loops, one going through all rows (m) and the other through all columns (n), and the operations inside the inner loop take O(1) time, the time complexity is O(m * n).

Space Complexity

For space complexity, the code is using a 3-dimensional list dp with dimensions m x n x 2 to store the minimum and maximum product paths up to each cell. The size of this list dictates the space complexity, which is O(m * n) as it's directly proportional to the size of the input grid.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄