Maximum Non Negative Product In A Matrix - Leetcode Solution

Problem Statement:

You are given a matrix of size n x m. You need to find the maximum non-negative product that can be obtained by traversing from the top-left corner to the bottom-right corner of the matrix. You can only move down or right from any cell.

If the maximum non-negative product is greater than or equal to zero, return the product. Otherwise, return -1.

Solution:

The first thing we need to do is to traverse from the top-left corner to the bottom-right corner of the matrix. We can do this using dynamic programming.

We can create a 2D array dp of size n x m where dp[i][j] represents the maximum non-negative product we can obtain by starting from cell (0,0) and traversing from the top-left corner to cell (i,j).

Initially, we can set dp[0][0] = matrix[0][0]. Now, we need to fill the rest of the dp array.

For any cell (i,j), we can either come from cell (i-1,j) or cell (i,j-1). We need to choose the cell that gives us the maximum non-negative product.

If matrix[i][j] is negative, we can ignore it because multiplying it with any other number will only decrease the product. So, in this case, dp[i][j] will be -1.

If matrix[i][j] is zero, we can still choose either cell (i-1,j) or cell (i,j-1) because multiplying zero with any number will always give us zero. So, in this case, dp[i][j] will be zero.

If matrix[i][j] is positive, we need to choose the cell that gives us the maximum non-negative product. So, we need to update dp[i][j] as follows:

• If dp[i-1][j] is negative, we can ignore it because multiplying it with matrix[i][j] will only decrease the product. So, we need to choose cell (i,j-1) and update dp[i][j] as dp[i][j-1] * matrix[i][j].

• If dp[i][j-1] is negative, we can ignore it because multiplying it with matrix[i][j] will only decrease the product. So, we need to choose cell (i-1,j) and update dp[i][j] as dp[i-1][j] * matrix[i][j].

• If both dp[i-1][j] and dp[i][j-1] are positive, we need to choose the cell that gives us the maximum non-negative product. So, we need to compare dp[i-1][j] * matrix[i][j] and dp[i][j-1] * matrix[i][j] and choose the maximum product. Then, we need to update dp[i][j] as the maximum product.

After filling the dp array, we can get the maximum non-negative product by accessing dp[n-1][m-1]. If it is greater than or equal to zero, we can return it. Otherwise, we can return -1.

Time Complexity:

The time complexity of the solution is O(n * m) because we traverse through each cell of the matrix once and perform constant time operations.

Space Complexity:

The space complexity of the solution is O(n * m) because we use a 2D array dp of size n x m.

1