Maximum Non Negative Product in a Matrix

#1094 Most AskedMedium

Maximum Non Negative Product in a Matrix #1094 Most Asked

Medium

6 views

Topics:

ArraysDynamic Programming

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 10⁹ + 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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what is the range of values within each cell? Can the matrix be empty or null?
Can any of the numbers in the matrix be zero?
What should be returned if there is no path with a non-negative product?
Is there a specific starting or ending point for the path through the matrix, or can I start from any cell and end at any cell?
Is it guaranteed that the input matrix will always be rectangular (i.e., all rows have the same length)?

Brute Force Solution

Approach

The brute force approach in this problem means exploring every possible path from the top-left to the bottom-right of the matrix. For each path, we'll calculate the product of the numbers we encounter along the way, and then we compare all the product results to find the largest non-negative value.

Here's how the algorithm would work step-by-step:

Begin at the starting point in the top-left corner of the grid.
Consider every possible path to move from the current position to either the cell directly to the right or the cell directly below.
Continue this process of moving right or down until you reach the bottom-right corner of the grid. Each unique combination of right and down moves forms a complete path.
For each of these paths, multiply all the numbers encountered along that path to obtain a product.
Keep track of all the products calculated from each path.
Once every possible path from the top-left to the bottom-right has been explored and its product calculated, find the largest product among all those collected. Remember, we only care about non-negative values.
If the largest product found is non-negative, that's the answer. If all products are negative, the result is -1.

Code Implementation

def maximum_non_negative_product_brute_force(matrix):
    all_products = []
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    def explore_paths(row_index, column_index, current_product):
        # Multiply the current element into the product
        current_product *= matrix[row_index][column_index]

        # Base case: Reached the destination
        if row_index == number_of_rows - 1 and column_index == number_of_columns - 1:
            all_products.append(current_product)
            return

        # Explore moving down
        if row_index + 1 < number_of_rows:
            explore_paths(row_index + 1, column_index, current_product)

        # Explore moving right
        if column_index + 1 < number_of_columns:
            explore_paths(row_index, column_index + 1, current_product)

    # Start the exploration from the top-left corner
    explore_paths(0, 0, 1)

    max_product = -1

    # Find the maximum non-negative product
    for product in all_products:
        if product >= 0:
            max_product = max(max_product, product)

    return max_product

Big(O) Analysis

Time Complexity

O(2^(m+n)) – The described brute force approach explores every possible path from the top-left to the bottom-right corner of an m x n matrix. Each path consists of m-1 downward moves and n-1 rightward moves in any order. The total number of paths is equivalent to choosing n-1 right moves out of (m-1)+(n-1) total moves, which is (m+n-2) choose (n-1), or (m+n-2)! / ((n-1)! * (m-1)!). In the worst-case scenario, where m and n are approximately equal (let's say both are roughly 'n'), the number of paths becomes proportional to 2^(2n) which simplifies to 2^(m+n). For each path, we compute the product of the elements which takes O(m+n) time. This leads to time complexity close to O((m+n) * 2^(m+n)). Since we are looking for the dominant term, the overall time complexity is O(2^(m+n)).

Space Complexity

O(2^(m+n)) – The brute force approach explores every possible path from the top-left to the bottom-right. In an m x n matrix, each path consists of m-1 down moves and n-1 right moves. The number of such paths grows exponentially. To store all these paths or the intermediate product values for each path (implicitly gathering results from each path), the auxiliary space needed scales with the number of paths. Thus, the space complexity is proportional to the number of paths, roughly O(2^(m+n)), where m is the number of rows and n is the number of columns.

Optimal Solution

Approach

The goal is to find a path through a grid from top-left to bottom-right that maximizes the product of the numbers we encounter. Since negative numbers can flip our product, we need to keep track of both the largest and smallest products we've seen so far.

Here's how the algorithm would work step-by-step:

Start at the top-left corner of the grid.
At each cell, calculate the largest and smallest possible products to reach that cell from the start.
To do this, multiply the current cell's value by both the largest and smallest products of the cell above it and the cell to its left. This accounts for potentially flipping signs with negative numbers.
Keep the maximum and minimum of these values as the new largest and smallest products for the current cell.
Continue this process until you reach the bottom-right corner.
The largest product at the bottom-right corner is our answer. If it's negative, it means no positive product path exists, so return -1.

Code Implementation

def maximum_non_negative_product(grid):
    rows = len(grid)
    cols = len(grid[0])

    max_products = [[0] * cols for _ in range(rows)]
    min_products = [[0] * cols for _ in range(rows)]

    max_products[0][0] = grid[0][0]
    min_products[0][0] = grid[0][0]

    for col_index in range(1, cols):
        max_products[0][col_index] = max_products[0][col_index - 1] * grid[0][col_index]
        min_products[0][col_index] = min_products[0][col_index - 1] * grid[0][col_index]

    for row_index in range(1, rows):
        max_products[row_index][0] = max_products[row_index - 1][0] * grid[row_index][0]
        min_products[row_index][0] = min_products[row_index - 1][0] * grid[row_index][0]

    for row_index in range(1, rows):
        for col_index in range(1, cols):
            # Need to consider both max and min from above/left
            temp_max = max(max_products[row_index - 1][col_index], max_products[row_index][col_index - 1])
            temp_min = min(min_products[row_index - 1][col_index], min_products[row_index][col_index - 1])

            max_products[row_index][col_index] = max(temp_max * grid[row_index][col_index], temp_min * grid[row_index][col_index])
            min_products[row_index][col_index] = min(temp_max * grid[row_index][col_index], temp_min * grid[row_index][col_index])

    # Negative result means no positive product path exists.
    if max_products[rows - 1][cols - 1] < 0:
        return -1
    else:
        return max_products[rows - 1][cols - 1]

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm iterates through each cell of the m x n matrix to compute the maximum and minimum products achievable at that cell. We visit each cell exactly once. For each cell, a constant number of operations is performed (multiplications and comparisons). Therefore, the overall time complexity is proportional to the number of cells in the matrix, resulting in O(m * n) time complexity, where 'm' is the number of rows and 'n' is the number of columns in the matrix. If m = n, it would be O(n²).

Space Complexity

O(m*n) – The algorithm maintains two matrices, `max_products` and `min_products`, of the same dimensions as the input matrix (m rows and n columns), to store the maximum and minimum product values seen so far at each cell. Thus the auxiliary space is proportional to the size of the input matrix. Therefore the space complexity is O(m*n) where m and n are dimensions of the input matrix.

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 immediately as there is no path.
1x1 matrix with a negative number	Return the single negative number as the result, as it's the only path.
Matrix with all zero values	Return 0, as any path will result in a zero product.
Matrix containing only negative numbers	Minimize the number of negative numbers in the path, consider both max and min at each point.
Large matrix leading to integer overflow	Use long data type to store the products to prevent integer overflow during multiplication.
Path with zero product exists	If any path contains a zero, the maximum product along that path will be zero, consider all other paths.
Matrix with mixed positive and negative numbers	Maintain both maximum and minimum products at each cell because a negative number can turn a minimum into a maximum.
Maximum sized matrix (constraints)	The solution should have a time complexity that scales linearly with the number of cells in the matrix, likely O(m*n) where m and n are dimensions.

Null or empty matrix

How to Handle:

Return 0 immediately as there is no path.

1x1 matrix with a negative number

How to Handle:

Return the single negative number as the result, as it's the only path.

Matrix with all zero values

How to Handle:

Return 0, as any path will result in a zero product.

Matrix containing only negative numbers

How to Handle:

Minimize the number of negative numbers in the path, consider both max and min at each point.

Large matrix leading to integer overflow

How to Handle:

Use long data type to store the products to prevent integer overflow during multiplication.

Path with zero product exists

How to Handle:

If any path contains a zero, the maximum product along that path will be zero, consider all other paths.

Matrix with mixed positive and negative numbers

How to Handle:

Maintain both maximum and minimum products at each cell because a negative number can turn a minimum into a maximum.

Maximum sized matrix (constraints)

How to Handle:

The solution should have a time complexity that scales linearly with the number of cells in the matrix, likely O(m*n) where m and n are dimensions.