Maximum Non Negative Product in a Matrix — Solution
Maximum Non Negative Product in a Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Non Negative Product in a Matrix is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You start at the top-left cell (0, 0) of an m x n integer matrix grid and may only move right or down until you reach the bottom-right cell (m - 1, n - 1). The product of a path is the product of every cell it visits, both ends included.
Find the path with the maximum product. If that maximum is negative, return -1. Otherwise return the maximum product modulo 10^9 + 7.
The maximum is decided on the exact products — the modulo is applied only to the final answer. (The grid here is at most 13 × 13, so every exact product is at most 4^25 in absolute value and fits in 64 bits — and even in a double.)
Example 1
Input: grid = [[2,-1],[3,-2]]
Output: 4
Explanation: Right then down gives 2 × (-1) × (-2) = 4; down then right gives 2 × 3 × (-2) = -12.
Example 2
Input: grid = [[-1,2],[3,4]]
Output: -1
Explanation: Both paths have a negative product (-8 and -12).
Example 3
Input: grid = [[1,-3,0],[2,-4,1]]
Output: 12
Explanation: 1 × (-3) × (-4) × 1 = 12 beats the paths through 0 (product 0) and through 2 (product -8).
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 13-4 <= grid[i][j] <= 4
Hints for Maximum Non Negative Product in a Matrix
Hint 1
Keeping only the largest product so far is not enough — a very negative product can become the largest after one more negative cell.
Hint 2
For every cell, track both the maximum and the minimum product of a path that ends there.
Hint 3
The new maximum and minimum at a cell come from multiplying its value with the max and min of the cell above and the cell to the left.
How to solve Maximum Non Negative Product in a Matrix
Multiplying by a negative number swaps the order of products, so a DP that remembers both the largest and the smallest product reaching each cell is enough to recover the true maximum.
Approach
- Set
hi[0][0] = lo[0][0] = grid[0][0]. - For every other cell with value
v, collecthi * vandlo * vfor the cell above and the cell to the left (whichever exist). hi[i][j]is the largest of those candidates andlo[i][j]the smallest.- If
hi[m-1][n-1] < 0return-1; otherwise return it modulo10^9 + 7.
Why it works
For a fixed last step, x · v over all products x reaching the previous cell is maximised at an extreme of x: the largest x when v >= 0, the smallest when v < 0. So keeping only the two extremes per cell loses no optimal path, and the same argument applies to the minimum.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Taking the modulo inside the DP destroys the comparisons — keep exact 64-bit products and reduce only at the end.
- Zero is a valid non-negative answer; return
-1only when the best product is strictly negative. - In JavaScript,
0 * -3is-0; normalise before printing.
Reference solution
Python
from typing import List
def maxProductPath(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
hi = [[0] * n for _ in range(m)]
lo = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
v = grid[i][j]
if i == 0 and j == 0:
hi[i][j] = lo[i][j] = v
continue
cands = []
if i > 0:
cands += [hi[i - 1][j] * v, lo[i - 1][j] * v]
if j > 0:
cands += [hi[i][j - 1] * v, lo[i][j - 1] * v]
hi[i][j] = max(cands)
lo[i][j] = min(cands)
best = hi[m - 1][n - 1]
return -1 if best < 0 else best % 1000000007Java
public static int maxProductPath(int[][] grid) {
int m = grid.length, n = grid[0].length;
long[][] hi = new long[m][n], lo = new long[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
long v = grid[i][j];
if (i == 0 && j == 0) { hi[i][j] = v; lo[i][j] = v; continue; }
long best = Long.MIN_VALUE, worst = Long.MAX_VALUE;
if (i > 0) {
best = Math.max(best, Math.max(hi[i - 1][j] * v, lo[i - 1][j] * v));
worst = Math.min(worst, Math.min(hi[i - 1][j] * v, lo[i - 1][j] * v));
}
if (j > 0) {
best = Math.max(best, Math.max(hi[i][j - 1] * v, lo[i][j - 1] * v));
worst = Math.min(worst, Math.min(hi[i][j - 1] * v, lo[i][j - 1] * v));
}
hi[i][j] = best;
lo[i][j] = worst;
}
}
long r = hi[m - 1][n - 1];
return r < 0 ? -1 : (int) (r % 1000000007L);
}C++
int maxProductPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<long long>> hi(m, vector<long long>(n)), lo(m, vector<long long>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
long long v = grid[i][j];
if (i == 0 && j == 0) { hi[i][j] = lo[i][j] = v; continue; }
long long best = LLONG_MIN, worst = LLONG_MAX;
if (i > 0) {
best = max(best, max(hi[i - 1][j] * v, lo[i - 1][j] * v));
worst = min(worst, min(hi[i - 1][j] * v, lo[i - 1][j] * v));
}
if (j > 0) {
best = max(best, max(hi[i][j - 1] * v, lo[i][j - 1] * v));
worst = min(worst, min(hi[i][j - 1] * v, lo[i][j - 1] * v));
}
hi[i][j] = best;
lo[i][j] = worst;
}
}
long long r = hi[m - 1][n - 1];
return r < 0 ? -1 : (int)(r % 1000000007LL);
}JavaScript
var maxProductPath = function(grid) {
var m = grid.length, n = grid[0].length;
var hi = [], lo = [];
for (var i = 0; i < m; i++) {
hi.push([]); lo.push([]);
for (var j = 0; j < n; j++) {
var v = grid[i][j];
if (i === 0 && j === 0) { hi[i].push(v); lo[i].push(v); continue; }
var best = -Infinity, worst = Infinity;
if (i > 0) {
best = Math.max(best, hi[i - 1][j] * v, lo[i - 1][j] * v);
worst = Math.min(worst, hi[i - 1][j] * v, lo[i - 1][j] * v);
}
if (j > 0) {
best = Math.max(best, hi[i][j - 1] * v, lo[i][j - 1] * v);
worst = Math.min(worst, hi[i][j - 1] * v, lo[i][j - 1] * v);
}
hi[i].push(best); lo[i].push(worst);
}
}
var r = hi[m - 1][n - 1];
// |r| <= 4^25 < 2^53, so the double is exact; + 0 turns -0 into 0
return r < 0 ? -1 : (r % 1000000007) + 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming