Skip to main content
Talentd

Maximum Non Negative Product in a Matrix - Solution & Explanation

MediumArrayDynamic ProgrammingMatrix17 min readAsked at: Amazon, Microsoft, Meta +1
Practice this problem

Problem Statement

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.length
  • n == grid[i].length
  • 1 <= 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.

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.

Code

PythonJavaC++

Python

Java

C++

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaScriptC#

JavaScript

C#

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Min/Max Path Products

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.

Recursive DFS with Memoization

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.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DFS with MemoizationO(m*n)O(m*n)Useful for understanding the recurrence and exploring paths recursively
Dynamic Programming with Min/Max Path ProductsO(m*n)O(m*n)Best general solution for grids with positive and negative numbers

Video Solution

Maximum Non Negative Product in a Matrix | Recursion | Memo | Bottom Up | Leetcode 1594 |DP On Grids • codestorywithMIK • 18,007 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Non Negative Product in a Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays