# Maximum Non Negative Product in a Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix)
Canonical: https://scaleengineer.com/dsa/problems/maximum-non-negative-product-in-a-matrix
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
---
## 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:**

![](https://assets.glich.co/dsa/maximum-non-negative-product-in-a-matrix/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/maximum-non-negative-product-in-a-matrix/image1.jpg) 

**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:**

![](https://assets.glich.co/dsa/maximum-non-negative-product-in-a-matrix/image2.jpg) 

**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`

# Approaches
## Brute Force using Recursion
This approach explores every possible path from the top-left to the bottom-right corner using recursion. For each path, it calculates the product of its elements and keeps track of the maximum non-negative product found so far.
**Time:** O(C(m+n-2, m-1)) - The number of paths from `(0,0)` to `(m-1, n-1)` is given by the binomial coefficient `C((m-1)+(n-1), m-1)`. This grows exponentially, making it very slow. · **Space:** O(m + n) - The space complexity is determined by the maximum depth of the recursion stack, which corresponds to the length of a path from `(0,0)` to `(m-1, n-1)`.
**Pros:** Simple to conceptualize and implement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force method involves a straightforward depth-first search (DFS) from the starting cell `(0, 0)`. We define a recursive helper function, say `solve(row, col, currentProduct)`, that explores paths. This function is called for every possible next step (down or right).

The `currentProduct` parameter accumulates the product of values along the path. When the recursion reaches the destination cell `(m-1, n-1)`, we have a complete path. We then check if the final product is non-negative. If it is, we compare it with a global maximum product and update it if the current path's product is larger.

Since we explore all paths, we are guaranteed to find the maximum product. However, the number of paths grows exponentially with the size of the grid, making this solution impractical for all but the smallest grids.

```java
class Solution {
    long maxProduct = -1;
    int MOD = 1_000_000_007;

    public int maxProductPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        solve(grid, 0, 0, 1L);
        if (maxProduct == -1) {
            return -1;
        }
        return (int) (maxProduct % MOD);
    }

    private void solve(int[][] grid, int r, int c, long currentProduct) {
        int m = grid.length;
        int n = grid[0].length;

        if (r >= m || c >= n) {
            return;
        }

        currentProduct *= grid[r][c];

        if (r == m - 1 && c == n - 1) {
            if (currentProduct >= 0) {
                maxProduct = Math.max(maxProduct, currentProduct);
            }
            return;
        }
        
        solve(grid, r + 1, c, currentProduct);
        solve(grid, r, c + 1, currentProduct);
    }
}
```
### Algorithm
- Initialize a global variable `maxProduct` to -1.
- Create a recursive function `solve(row, col, currentProduct)`.
- The function takes the current row, column, and the product of the path so far.
- **Base Case:** If `row == m-1` and `col == n-1`, we have reached the destination.
  - Calculate the final product: `finalProduct = currentProduct * grid[row][col]`.
  - If `finalProduct >= 0`, update `maxProduct = max(maxProduct, finalProduct)`.
  - Return.
- **Recursive Step:**
  - Calculate the new product for the current cell: `newProduct = currentProduct * grid[row][col]`.
  - If `row + 1 < m`, call `solve(row + 1, col, newProduct)`.
  - If `col + 1 < n`, call `solve(row, col, newProduct)`.
- Start the process by calling `solve(0, 0, 1)`.
- After the recursion completes, if `maxProduct` is still -1, it means no non-negative path exists. Otherwise, return `maxProduct % (10^9 + 7)`.

## Dynamic Programming
This approach uses dynamic programming to solve the problem efficiently. The key insight is that due to negative numbers, a path with a minimum (large negative) product could become a maximum positive product in a subsequent step. Therefore, we maintain two DP tables: one for the maximum product (`maxDp`) and one for the minimum product (`minDp`) to reach each cell.
**Time:** O(m * n) - We iterate through each cell of the grid exactly once to compute the DP values. · **Space:** O(m * n) - We use two 2D arrays of the same size as the input grid to store the intermediate maximum and minimum products.
**Pros:** Guaranteed to find the optimal solution.; Much more efficient than brute force, with a polynomial time complexity.; Handles all cases including positive, negative, and zero values correctly.
**Cons:** Uses `O(m*n)` space, which can be substantial for very large grids, although it's acceptable for the given constraints.
### Explanation
We create two 2D arrays, `maxDp[m][n]` and `minDp[m][n]`, to store the maximum and minimum path products ending at cell `(i, j)`, respectively. We iterate through the grid, filling these tables.

- **Initialization**: The values for `(0,0)` are `maxDp[0][0] = minDp[0][0] = grid[0][0]`.
- **Transitions**: For any other cell `(i, j)`, the path to it must come from either `(i-1, j)` (top) or `(i, j-1)` (left). The product at `(i, j)` is `grid[i][j]` multiplied by the product from one of these previous cells.
  - If `grid[i][j]` is non-negative, the new maximum product is `grid[i][j]` times the maximum of the previous maximum products (`max(maxDp[i-1][j], maxDp[i][j-1])`). Similarly for the minimum product.
  - If `grid[i][j]` is negative, the roles are swapped: the new maximum product is `grid[i][j]` times the minimum of the previous minimum products (`min(minDp[i-1][j], minDp[i][j-1])`), as multiplying by a negative flips the sign and magnitude order.
- **Final Result**: After filling the tables, `maxDp[m-1][n-1]` holds the maximum product for any path from `(0,0)` to `(m-1,n-1)`. If this value is negative, no non-negative path exists. Otherwise, we return the result modulo `10^9 + 7`.

```java
class Solution {
    public int maxProductPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        long[][] maxDp = new long[m][n];
        long[][] minDp = new long[m][n];
        int MOD = 1_000_000_007;

        maxDp[0][0] = minDp[0][0] = grid[0][0];

        for (int i = 1; i < m; i++) {
            long val = grid[i][0];
            maxDp[i][0] = maxDp[i - 1][0] * val;
            minDp[i][0] = minDp[i - 1][0] * val;
        }

        for (int j = 1; j < n; j++) {
            long val = grid[0][j];
            maxDp[0][j] = maxDp[0][j - 1] * val;
            minDp[0][j] = minDp[0][j - 1] * val;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                long val = grid[i][j];
                if (val >= 0) {
                    maxDp[i][j] = Math.max(maxDp[i - 1][j], maxDp[i][j - 1]) * val;
                    minDp[i][j] = Math.min(minDp[i - 1][j], minDp[i][j - 1]) * val;
                } else {
                    maxDp[i][j] = Math.min(minDp[i - 1][j], minDp[i][j - 1]) * val;
                    minDp[i][j] = Math.max(maxDp[i - 1][j], maxDp[i][j - 1]) * val;
                }
            }
        }

        long result = maxDp[m - 1][n - 1];
        if (result < 0) {
            return -1;
        }
        return (int) (result % MOD);
    }
}
```
### Algorithm
- Get grid dimensions `m` and `n`.
- Create two `m x n` DP tables, `maxDp` and `minDp`, of type `long`.
- **Base Case:** Initialize `maxDp[0][0] = grid[0][0]` and `minDp[0][0] = grid[0][0]`.
- **Fill first row:** For `j` from 1 to `n-1`, calculate `maxDp[0][j]` and `minDp[0][j]` based on the values at `(0, j-1)` and `grid[0][j]`, considering the sign of `grid[0][j]`.
- **Fill first column:** For `i` from 1 to `m-1`, calculate `maxDp[i][0]` and `minDp[i][0]` based on the values at `(i-1, 0)` and `grid[i][0]`.
- **Fill the rest of the tables:** For `i` from 1 to `m-1` and `j` from 1 to `n-1`:
  - Let `val = grid[i][j]`.
  - If `val >= 0`:
    - `maxDp[i][j] = val * max(maxDp[i-1][j], maxDp[i][j-1])`
    - `minDp[i][j] = val * min(minDp[i-1][j], minDp[i][j-1])`
  - If `val < 0`:
    - `maxDp[i][j] = val * min(minDp[i-1][j], minDp[i][j-1])`
    - `minDp[i][j] = val * max(maxDp[i-1][j], maxDp[i][j-1])`
- The result is `maxDp[m-1][n-1]`. If it's negative, return -1. Otherwise, return `result % (10^9 + 7)`.

## Space-Optimized Dynamic Programming
This approach builds upon the standard dynamic programming solution but optimizes the space complexity. We observe that to compute the values for the current row, we only need the values from the previous row. Therefore, instead of storing the entire 2D DP tables, we can use 1D arrays to store the information for just one row at a time, reducing space from `O(m*n)` to `O(n)`.
**Time:** O(m * n) - The time complexity remains the same as the standard DP approach, as we still need to visit each cell once. · **Space:** O(n) - We use two 1D arrays of size `n` (the number of columns) to store the DP states for the current row.
**Pros:** Optimal time complexity of `O(m*n)`.; Highly efficient space complexity of `O(n)` (or `O(min(m,n))` if we choose the smaller dimension).; The most efficient solution for this problem.
**Cons:** The logic for in-place updates can be slightly more complex to implement correctly compared to the 2D DP approach.
### Explanation
Instead of using 2D DP tables, we can use two 1D arrays, `maxDp` and `minDp`, each of size `n` (the number of columns). `maxDp[j]` will store the maximum product to reach the cell in the current row at column `j`.

We first initialize the arrays based on the first row of the grid. Then, we iterate from the second row to the last. For each row `i`, we update the `maxDp` and `minDp` arrays. When calculating the values for cell `(i, j)`, we need the values from the cell above, `(i-1, j)`, which are stored in `maxDp[j]` and `minDp[j]` from the previous iteration, and the values from the cell to the left, `(i, j-1)`, which are the just-computed `maxDp[j-1]` and `minDp[j-1]` for the current row. This in-place update scheme allows us to use only `O(n)` extra space.

```java
class Solution {
    public int maxProductPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        long[] maxDp = new long[n];
        long[] minDp = new long[n];
        int MOD = 1_000_000_007;

        // Initialize first cell
        maxDp[0] = minDp[0] = grid[0][0];

        // Initialize first row
        for (int j = 1; j < n; j++) {
            long val = grid[0][j];
            if (val >= 0) {
                maxDp[j] = maxDp[j - 1] * val;
                minDp[j] = minDp[j - 1] * val;
            } else {
                maxDp[j] = minDp[j - 1] * val;
                minDp[j] = maxDp[j - 1] * val;
            }
        }

        // Iterate through the rest of the rows
        for (int i = 1; i < m; i++) {
            // Update first column of the current row
            long val_col0 = grid[i][0];
            long tempMax = maxDp[0];
            maxDp[0] = (val_col0 >= 0) ? maxDp[0] * val_col0 : minDp[0] * val_col0;
            minDp[0] = (val_col0 >= 0) ? minDp[0] * val_col0 : tempMax * val_col0;

            // Update the rest of the row
            for (int j = 1; j < n; j++) {
                long val = grid[i][j];
                long max_from_top = maxDp[j];
                long min_from_top = minDp[j];
                long max_from_left = maxDp[j - 1];
                long min_from_left = minDp[j - 1];
                
                if (val >= 0) {
                    maxDp[j] = Math.max(max_from_top, max_from_left) * val;
                    minDp[j] = Math.min(min_from_top, min_from_left) * val;
                } else {
                    maxDp[j] = Math.min(min_from_top, min_from_left) * val;
                    minDp[j] = Math.max(max_from_top, max_from_left) * val;
                }
            }
        }

        long result = maxDp[n - 1];
        if (result < 0) {
            return -1;
        }
        return (int) (result % MOD);
    }
}
```
### Algorithm
- Create two 1D arrays, `maxDp` and `minDp`, of size `n`.
- **Initialize for the first row:**
  - Set `maxDp[0] = minDp[0] = grid[0][0]`.
  - For `j` from 1 to `n-1`, calculate `maxDp[j]` and `minDp[j]` based on `maxDp[j-1]`, `minDp[j-1]`, and `grid[0][j]`.
- **Iterate through subsequent rows (`i` from 1 to `m-1`):**
  - First, update `maxDp[0]` and `minDp[0]` for the current row `i` based on their previous values and `grid[i][0]`.
  - Then, for `j` from 1 to `n-1`, calculate the new `maxDp[j]` and `minDp[j]`.
  - The new values for `(i, j)` depend on the values from `(i-1, j)` (the old `maxDp[j]`, `minDp[j]`) and `(i, j-1)` (the new `maxDp[j-1]`, `minDp[j-1]`).
- After iterating through all rows, `maxDp[n-1]` holds the final maximum product.
- Return the result, handling the negative case and modulo operation as before.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int maxProductPath(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    long[][][] dp = new long[m][n][2];
    dp[0][0][0] = grid[0][0];
    dp[0][0][1] = grid[0][0];
    for (int i = 1; i < m; ++i) {
      dp[i][0][0] = dp[i - 1][0][0] * grid[i][0];
      dp[i][0][1] = dp[i - 1][0][1] * grid[i][0];
    }
    for (int j = 1; j < n; ++j) {
      dp[0][j][0] = dp[0][j - 1][0] * grid[0][j];
      dp[0][j][1] = dp[0][j - 1][1] * grid[0][j];
    }
    for (int i = 1; i < m; ++i) {
      for (int j = 1; j < n; ++j) {
        int v = grid[i][j];
        if (v >= 0) {
          dp[i][j][0] = Math.min(dp[i - 1][j][0], dp[i][j - 1][0]) * v;
          dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) * v;
        } else {
          dp[i][j][0] = Math.max(dp[i - 1][j][1], dp[i][j - 1][1]) * v;
          dp[i][j][1] = Math.min(dp[i - 1][j][0], dp[i][j - 1][0]) * v;
        }
      }
    }
    long ans = dp[m - 1][n - 1][1];
    return ans < 0 ? -1 : (int)(ans % MOD);
  }
}

```

### CPP

```cpp
using ll = long long ; const int mod = 1e9 + 7 ; class Solution { public: int maxProductPath ( vector < vector < int >>& grid ) { int m = grid . size (); int n = grid [ 0 ]. size (); vector < vector < vector < ll >>> dp ( m , vector < vector < ll >> ( n , vector < ll > ( 2 , grid [ 0 ][ 0 ]))); for ( int i = 1 ; i < m ; ++ i ) { dp [ i ][ 0 ][ 0 ] = dp [ i - 1 ][ 0 ][ 0 ] * grid [ i ][ 0 ]; dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 1 ] * grid [ i ][ 0 ]; } for ( int j = 1 ; j < n ; ++ j ) { dp [ 0 ][ j ][ 0 ] = dp [ 0 ][ j - 1 ][ 0 ] * grid [ 0 ][ j ]; dp [ 0 ][ j ][ 1 ] = dp [ 0 ][ j - 1 ][ 1 ] * grid [ 0 ][ j ]; } for ( int i = 1 ; i < m ; ++ i ) { for ( int j = 1 ; j < n ; ++ j ) { int v = grid [ i ][ j ]; if ( v >= 0 ) { dp [ i ][ j ][ 0 ] = min ( dp [ i - 1 ][ j ][ 0 ], dp [ i ][ j - 1 ][ 0 ]) * v ; dp [ i ][ j ][ 1 ] = max ( dp [ i - 1 ][ j ][ 1 ], dp [ i ][ j - 1 ][ 1 ]) * v ; } else { dp [ i ][ j ][ 0 ] = max ( dp [ i - 1 ][ j ][ 1 ], dp [ i ][ j - 1 ][ 1 ]) * v ; dp [ i ][ j ][ 1 ] = min ( dp [ i - 1 ][ j ][ 0 ], dp [ i ][ j - 1 ][ 0 ]) * v ; } } } ll ans = dp [ m - 1 ][ n - 1 ][ 1 ]; return ans < 0 ? - 1 : ( int ) ( ans % mod ); } };
```

### Python

```python
class Solution:
    def maxProductPath(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) mod = 10 ** 9 + 7 dp = [[[grid[0][0]] * 2 for _ in range(n)] for _ in range(m)] for i in range(1, m): dp[i][0] = [dp[i - 1][0][0] * grid[i][0]] * 2 for j in range(1, n): dp[0][j] = [dp[0][j - 1][0] * grid[0][j]] * 2 for i in range(1, m): for j in range(1, n): v = grid[i][j] if v >= 0: dp[i][j][0] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * v dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * v else: dp[i][j][0] = max(dp[i - 1][j][1], dp[i][j - 1][1]) * v dp[i][j][1] = min(dp[i - 1][j][0], dp[i][j - 1][0]) * v ans = dp[- 1][- 1][1] return - 1 if ans < 0 else ans % mod

```