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:
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.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:
-
Initialization:
- The
dp
array is initialized with a size ofm x n x 2
, wherem
andn
are the dimensions of the input grid. Each cell indp
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.
- The
-
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 ton
, and setdp[0][j]
equal to the product ofdp[0][j - 1][0]
(the previous cell) andgrid[0][j]
. We do the same for the first column, iterating overi
from 1 tom
, setting eachdp[i][0]
according to the product of the previous cell and the current grid value.
- Each cell in the first row and column can only be reached from one direction. Thus, for the first row, we iterate over
-
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 multiplyinggrid[i][j]
with the smaller of eitherdp[i - 1][j][0]
(above) ordp[i][j - 1][0]
(left). - Calculate
dp[i][j][1]
(max product) by multiplyinggrid[i][j]
with the larger of eitherdp[i - 1][j][1]
(above) ordp[i][j - 1][1]
(left). Ifgrid[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 multiplyinggrid[i][j]
with the larger of eitherdp[i - 1][j][1]
(above) ordp[i][j - 1][1]
(left). - Find
dp[i][j][1]
(max product) by multiplyinggrid[i][j]
with the smaller of eitherdp[i - 1][j][0]
(above) ordp[i][j - 1][0]
(left).
- Find
- We iterate over the cells of the grid starting from
-
Getting the result:
- After filling in the entire
dp
array, we look at the bottom-right corner (last cell) of the griddp[m - 1][n - 1]
. Specifically, we're interested in the maximum product path, which is stored indp[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.
- After filling in the entire
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
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 dimensions3 x 3 x 2
. - Set
dp[0][0]
to[1, 1]
since the first cell of the grid is1
, and there's only one path with one cell at the starting point.
- Initialize
-
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]
.
- For
- 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]
.
- For
- First row: Iterate over
-
Filling the rest of the dp array:
- Now, we iterate over the inner cells starting from
(1, 1)
. - For
i = 1
andj = 1
(grid[1][1]
is3
, 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]
.
- Calculate minimum as
- For
i = 1
andj = 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]
.
- Calculate the minimum as
- For
i = 2
andj = 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]
.
- Minimum:
- For
i = 2
andj = 2
(grid[2][2]
is4
, 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]
.
- Minimum:
- Now, we iterate over the inner cells starting from
-
Getting the result:
- Looking at the last cell
dp[2][2]
, we have the maximum product as16
. Since it is non-negative, we return16 % (10^9 + 7)
, which is16
.
- Looking at the last cell
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.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.