Maximum Non Negative Product in a Matrix

Medium
1554.

Maximum Non Negative Product in a Matrix

Maximum Non Negative Product in a Matrix is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.

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.length
  • n == grid[i].length
  • 1 <= m, n <= 13
  • -4 <= grid[i][j] <= 4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxProductPath = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • n == grid[i].length
  • 1 <= m, n <= 13
  • -4 <= grid[i][j] <= 4

Hints for Maximum Non Negative Product in a Matrix

  1. 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.

  2. Hint 2

    For every cell, track both the maximum and the minimum product of a path that ends there.

  3. 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

  1. Set hi[0][0] = lo[0][0] = grid[0][0].
  2. For every other cell with value v, collect hi * v and lo * v for the cell above and the cell to the left (whichever exist).
  3. hi[i][j] is the largest of those candidates and lo[i][j] the smallest.
  4. If hi[m-1][n-1] < 0 return -1; otherwise return it modulo 10^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 -1 only when the best product is strictly negative.
  • In JavaScript, 0 * -3 is -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 % 1000000007

Java

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