Maximum Non Negative Product in a Matrix solution and explanation
Google
9 more videos on this problem
Maximum Non Negative Product in a Matrix | Recursion | Memo | Bottom Up | Leetcode 1594 |DP On GridscodestorywithMIK · 1:07:42 · 18K views
LeetCode 1594. Maximum Non Negative Product in a MatrixHappy Coding · 17:27 · 1K views
LeetCode 1594. Maximum Non Negative Product in a Matrix | Dynamic Programming | PythonAH Tech · 7:46 · 1K views
1594. Maximum Non Negative Product in a Matrix | Leetcode Daily - PythonLeetcode Daily · 9:10 · 1K views
Maximum Non Negative Product in a Matrix | Leetcode 1594 | Java | HindiKernel Queen 👑 · 8:45 · 1K views
Leetcode Solutions 1594. Maximum Non Negative Product in a MatrixAbrar Sher · 8:54 · 827 views
Daily Leetcode #2183: Mar 23, 2026 - 1594. Maximum Non Negative Product in a MatrixProgramming Live with Larry · 20:36 · 535 views
Maximum Non Negative Product in a Matrix | LeetCode 1594 | Java Code | Developer CoderDeveloper Coder · 22:06 · 510 views
1594. Maximum Non Negative Product in a Matrix (Leetcode Medium)Programming Live with Larry · 26:46 · 442 views
Maximum Non Negative Product in a Matrix | LeetCode 1594 - Pythonimpoldev · 14:14 · 410 views
The problem
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 109 + 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.lengthn == grid[i].length1 <= m, n <= 15-4 <= grid[i][j] <= 4
Approach overview
Problem Overview: You are given an m x n grid containing positive, negative, and zero values. Starting from the top-left cell, you can only move right or down. The goal is to reach the bottom-right cell while maximizing the product of all visited values. If the maximum product is negative, return -1. Otherwise return the product modulo 1e9 + 7. The challenge is handling negative numbers, because multiplying by a negative flips the sign of the product.
Approach 1: Recursive DFS with Memoization (O(m*n) time, O(m*n) space)
This approach explores all valid paths using depth-first search while caching results to avoid recomputation. At each cell, recursively compute the best possible product from the right and down neighbors. Because values can be negative, you must track both the minimum and maximum product reaching a cell. A negative number can turn the smallest product into the largest after multiplication. Memoization stores results for each cell so the recursion does not recompute overlapping subproblems. This technique works well for explaining the state transition and mirrors the recurrence directly, but recursion depth and function call overhead make it less practical than an iterative DP solution.
Approach 2: Dynamic Programming with Min/Max Path Products (O(m*n) time, O(m*n) space)
The optimal approach uses dynamic programming on the grid. Instead of storing a single value per cell, maintain two DP tables: maxProd[i][j] and minProd[i][j]. These represent the maximum and minimum product achievable when reaching cell (i, j). The reason for two states is that multiplying by a negative value flips signs, so a previously small negative product may become the largest positive product.
For each cell, compute candidate values from the top and left neighbors. Multiply the current cell value with both the neighbor's min and max products. Take the maximum of these results for maxProd and the minimum for minProd. This transition ensures all sign combinations are handled correctly. The grid is processed row by row, similar to standard matrix DP problems. The final answer is maxProd[m-1][n-1]. If it is negative, return -1; otherwise apply the required modulo.
This solution runs in linear time relative to the number of cells and only performs constant work per transition. The idea of tracking both minimum and maximum states appears frequently in array and DP problems involving products or negative numbers.
Recommended for interviews: The dynamic programming approach with min/max tracking is what interviewers expect. It shows you understand how negative values affect multiplicative paths and how to model that with DP states. The recursive memoized version demonstrates the recurrence clearly, but the iterative DP solution is cleaner, faster, and easier to reason about in production code.
Approach 1: Dynamic Programming with Min/Max Path Products
This approach involves tracking the maximum and minimum products achievable at each cell. We initialize two matrices, 'max_product' and 'min_product', both the same size as the grid. These matrices store the maximum and minimum product paths to each cell. We fill these matrices by considering the best possible moves from the left and above to reach each cell. Finally, we compare the maximum product at the bottom-right corner to determine the result.
def maxProductPath(grid):
MOD = 10**9 + 7
m, n = len(grid), len(grid[0])
max_product = [[0] * n for _ in range(m)]
min_product = [[0] * n for _ in range(m)]
max_product[0][0] = min_product[0][0] = grid[0][0]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
cur_val = grid[i][j]
if i > 0:
top_max = max_product[i-1][j]
top_min = min_product[i-1][j]
else:
top_max = top_min = float('-inf') if cur_val < 0 else float('inf')
if j > 0:
left_max = max_product[i][j-1]
left_min = min_product[i][j-1]
else:
left_max = left_min = float('-inf') if cur_val < 0 else float('inf')
max_product[i][j] = max(cur_val * top_max, cur_val * top_min, cur_val * left_max, cur_val * left_min)
min_product[i][j] = min(cur_val * top_max, cur_val * top_min, cur_val * left_max, cur_val * left_min)
result = max_product[m-1][n-1]
return result % MOD if result >= 0 else -1class Solution {
public int maxProductPath(int[][] grid) {
int MOD = 1_000_000_007;
int m = grid.length, n = grid[0].length;
long[][] maxProduct = new long[m][n];
long[][] minProduct = new long[m][n];
maxProduct[0][0] = minProduct[0][0] = grid[0][0];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
long cur = grid[i][j];
long topMax = i > 0 ? maxProduct[i-1][j] : (cur < 0 ? Long.MAX_VALUE : Long.MIN_VALUE);
long topMin = i > 0 ? minProduct[i-1][j] : (cur < 0 ? Long.MAX_VALUE : Long.MIN_VALUE);
long leftMax = j > 0 ? maxProduct[i][j-1] : (cur < 0 ? Long.MAX_VALUE : Long.MIN_VALUE);
long leftMin = j > 0 ? minProduct[i][j-1] : (cur < 0 ? Long.MAX_VALUE : Long.MIN_VALUE);
maxProduct[i][j] = Math.max(cur * topMax, Math.max(cur * topMin, Math.max(cur * leftMax, cur * leftMin)));
minProduct[i][j] = Math.min(cur * topMax, Math.min(cur * topMin, Math.min(cur * leftMax, cur * leftMin)));
}
}
int result = (int)(maxProduct[m-1][n-1] % MOD);
return result >= 0 ? result : -1;
}
}#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProductPath(vector<vector<int>>& grid) {
const int MOD = 1e9 + 7;
int m = grid.size(), n = grid[0].size();
vector<vector<long long>> maxProduct(m, vector<long long>(n));
vector<vector<long long>> minProduct(m, vector<long long>(n));
maxProduct[0][0] = minProduct[0][0] = grid[0][0];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 && j == 0) continue;
long long cur = grid[i][j];
long long topMax = (i > 0) ? maxProduct[i-1][j] : ((cur < 0) ? LLONG_MAX : LLONG_MIN);
long long topMin = (i > 0) ? minProduct[i-1][j] : ((cur < 0) ? LLONG_MAX : LLONG_MIN);
long long leftMax = (j > 0) ? maxProduct[i][j-1] : ((cur < 0) ? LLONG_MAX : LLONG_MIN);
long long leftMin = (j > 0) ? minProduct[i][j-1] : ((cur < 0) ? LLONG_MAX : LLONG_MIN);
maxProduct[i][j] = max({cur * topMax, cur * topMin, cur * leftMax, cur * leftMin});
minProduct[i][j] = min({cur * topMax, cur * topMin, cur * leftMax, cur * leftMin});
}
}
long long result = maxProduct[m-1][n-1];
return result >= 0 ? result % MOD : -1;
}
};This code starts by initializing two matrices to track the minimum and maximum products possible at each cell. It iterates through the grid, updating these matrices based on the best possible ways to enter each cell from the left or above it. The result is the maximum product at the bottom-right corner modulo 10^9 + 7 if it is non-negative; otherwise, it returns -1.
Time complexity: O(m * n) where m and n are the dimensions of the grid.
Space complexity: O(m * n) for the additional storage of the minimum and maximum product matrices.
Approach 2: Recursive DFS with Memoization
This approach uses a recursive depth-first search combined with memoization to explore all possible paths from the top-left to the bottom-right. The recursion tracks the product along each possible path, storing previously calculated products for revisitation efficiency through a memoization table.
function maxProductPath(grid) {
let MOD = 1e9 + 7;
let m = grid.length, n = grid[0].length;
let memo = Array.from({ length: m }, () => Array.from({ length: n }, () => Array(2).fill(null)));
function dfs(x, y) {
if (x === m - 1 && y === n - 1) return [grid[x][y], grid[x][y]];
if (memo[x][y][0] !== null) return [memo[x][y][0], memo[x][y][1]];
let paths = [];
if (x + 1 < m) paths.push(dfs(x + 1, y));
if (y + 1 < n) paths.push(dfs(x, y + 1));
let curVal = grid[x][y];
let maxProduct = -Infinity, minProduct = Infinity;
for (let [maxPath, minPath] of paths) {
maxProduct = Math.max(maxProduct, curVal * maxPath, curVal * minPath);
minProduct = Math.min(minProduct, curVal * maxPath, curVal * minPath);
}
memo[x][y] = [maxProduct, minProduct];
return memo[x][y];
}
let [maxProd, minProd] = dfs(0, 0);
return maxProd < 0 ? -1 : maxProd % MOD;
}public class Solution {
private const int MOD = 1000000007;
private int[][][] memo;
private int[][] grid;
public int MaxProductPath(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
this.grid = grid;
memo = new int[m][][];
for (int i = 0; i < m; i++)
memo[i] = new int[n][] { new int[] { int.MinValue, int.MaxValue } };
var result = Dfs(0, 0);
return result[0] < 0 ? -1 : result[0] % MOD;
}
private int[] Dfs(int i, int j) {
if (i == grid.Length - 1 && j == grid[0].Length - 1)
return new int[] { grid[i][j], grid[i][j] };
if (memo[i][j][0] != int.MinValue)
return memo[i][j];
var maxProduct = int.MinValue;
var minProduct = int.MaxValue;
if (i < grid.Length - 1) {
var down = Dfs(i + 1, j);
maxProduct = Math.Max(maxProduct, grid[i][j] * Math.Max(down[0], down[1]));
minProduct = Math.Min(minProduct, grid[i][j] * Math.Min(down[0], down[1]));
}
if (j < grid[0].Length - 1) {
var right = Dfs(i, j + 1);
maxProduct = Math.Max(maxProduct, grid[i][j] * Math.Max(right[0], right[1]));
minProduct = Math.Min(minProduct, grid[i][j] * Math.Min(right[0], right[1]));
}
memo[i][j] = new int[] { maxProduct, minProduct };
return memo[i][j];
}
}This JavaScript solution leverages DFS for exploring grid paths recursively. By storing maximum and minimum path products in a memoization structure at each step, repetitive calculations are reduced, which enhances performance.
Time complexity: Expected to be close to O(m * n) due to memoization, which prevents re-evaluating already computed results.
Space complexity: O(m * n) for memoization storage.
Approach 3: Dynamic Programming
We define a 3D array f, where f[i][j][0] and f[i][j][1] represent the minimum and maximum product of all paths from the top-left corner (0, 0) to position (i, j), respectively. For each position (i, j), we can transition from above (i - 1, j) or from the left (i, j - 1), so we need to consider the results of multiplying the minimum and maximum products of these two paths by the value of the current cell.
Finally, we need to return f[m - 1][n - 1][1] modulo 10^9 + 7. If f[m - 1][n - 1][1] is less than 0, return -1.
The time complexity is O(m times n) and the space complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively.
function maxProductPath(grid: number[][]): number {
const m = grid.length,
n = grid[0].length;
const f = Array.from({ length: m }, () => Array.from({ length: n }, () => [0, 0]));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
const x = grid[i][j];
if (i === 0 && j === 0) {
f[i][j] = [x, x];
continue;
}
let mn = Infinity,
mx = -Infinity;
if (i > 0) {
const [a, b] = f[i - 1][j];
mn = Math.min(mn, a * x, b * x);
mx = Math.max(mx, a * x, b * x);
}
if (j > 0) {
const [a, b] = f[i][j - 1];
mn = Math.min(mn, a * x, b * x);
mx = Math.max(mx, a * x, b * x);
}
f[i][j] = [mn, mx];
}
}
const ans = f[m - 1][n - 1][1];
const mod = 1e9 + 7;
return ans < 0 ? -1 : ans % mod;
}func maxProductPath(grid [][]int) int {
m, n := len(grid), len(grid[0])
f := make([][][2]int64, m)
for i := range f {
f[i] = make([][2]int64, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
x := int64(grid[i][j])
if i == 0 && j == 0 {
f[i][j] = [2]int64{x, x}
continue
}
mn, mx := int64(1<<63-1), int64(-1<<63)
if i > 0 {
a, b := f[i-1][j][0], f[i-1][j][1]
mn = min(mn, min(a*x, b*x))
mx = max(mx, max(a*x, b*x))
}
if j > 0 {
a, b := f[i][j-1][0], f[i][j-1][1]
mn = min(mn, min(a*x, b*x))
mx = max(mx, max(a*x, b*x))
}
f[i][j] = [2]int64{mn, mx}
}
}
ans := f[m-1][n-1][1]
mod := int64(1e9 + 7)
if ans < 0 {
return -1
}
return int(ans % mod)
}impl Solution {
pub fn max_product_path(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut f = vec![vec![[0i64; 2]; n]; m];
for i in 0..m {
for j in 0..n {
let x = grid[i][j] as i64;
if i == 0 && j == 0 {
f[i][j] = [x, x];
continue;
}
let mut mn = i64::MAX;
let mut mx = i64::MIN;
if i > 0 {
let [a, b] = f[i - 1][j];
mn = mn.min(a * x).min(b * x);
mx = mx.max(a * x).max(b * x);
}
if j > 0 {
let [a, b] = f[i][j - 1];
mn = mn.min(a * x).min(b * x);
mx = mx.max(a * x).max(b * x);
}
f[i][j] = [mn, mx];
}
}
let ans = f[m - 1][n - 1][1];
let mod_val = 1_000_000_007i64;
if ans < 0 {
-1
} else {
(ans % mod_val) as i32
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Min/Max Path Products | Time complexity: O(m * n) where m and n are the dimensions of the grid. |
| Recursive DFS with Memoization | Time complexity: Expected to be close to O(m * n) due to memoization, which prevents re-evaluating already computed results. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS with Memoization | O(m*n) | O(m*n) | Useful for understanding the recurrence and exploring paths recursively |
| Dynamic Programming with Min/Max Path Products | O(m*n) | O(m*n) | Best general solution for grids with positive and negative numbers |
Frequently asked questions
Is Maximum Non Negative Product in a Matrix easy or hard?
The problem is generally classified as Medium on LeetCode. The difficulty comes from handling negative numbers correctly by tracking both minimum and maximum products instead of a single DP state.
Maximum Non Negative Product in a Matrix Python/Java solution
Most implementations use a 2D DP array storing both min and max products per cell. The algorithm iterates through the grid and updates states using values from the left and top cells. The same logic works across Python, Java, and C++ with O(m*n) complexity.
How to solve Maximum Non Negative Product in a Matrix in O(m*n)?
Use two DP states per cell: the maximum product and minimum product reaching that position. For each cell, multiply the current value with both min and max values from the top and left cells, then update the new min and max. This single pass over the grid yields the optimal product in O(m*n) time.
What is the best approach for Maximum Non Negative Product in a Matrix?
Dynamic programming with min and max path tracking is the most reliable approach. Each cell keeps the largest and smallest product achievable from the start because multiplying by a negative value flips signs. This ensures all sign combinations are handled while scanning the grid once.
Is Maximum Non Negative Product in a Matrix asked at Google/Amazon/Meta?
Matrix dynamic programming problems with sign handling frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving path products, maximum path sums, or grid DP transitions are common interview patterns.
What data structure is used in Maximum Non Negative Product in a Matrix?
The solution primarily uses dynamic programming arrays (or matrices) to store the minimum and maximum product values for each grid cell. The grid itself is processed like a typical matrix traversal using row and column indices.
What is the time complexity of Maximum Non Negative Product in a Matrix?
The optimal dynamic programming solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is processed once and only constant work is done per transition using values from the top and left neighbors.