Maximum Non Negative Product in a Matrix - Practice Coding Problems

Maximum Non Negative Product in a 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 10⁹ + 7. If the maximum product is negative, return -1.

Notice that the modulo is performed after getting the maximum product.

Input & Output

Example 1 — All Negative Numbers

$ Input: grid = [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]

› Output: 36

💡 Note: Path: (-1) → (-2) → (-3) → (-3) → (-2). Product = (-1) × (-2) × (-3) × (-3) × (-2) = 36

Example 2 — Mix of Positive and Negative

$ Input: grid = [[1,-2,1],[1,-2,1],[3,-4,1]]

› Output: 8

💡 Note: Path: (1) → (1) → (3) → (-4) → (1). Product = 1 × 1 × 3 × (-4) × 1 = -12, but best path gives 8

Example 3 — All Negative Result

$ Input: grid = [[-1,-1],[-1,-1]]

› Output: -1

💡 Note: All possible paths result in negative products: (-1) × (-1) × (-1) = -1

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 15
-4 ≤ grid[i][j] ≤ 4

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Matrix with positive and negative numbers

Find Paths

Only right and down moves allowed

Calculate Products

Track maximum non-negative product

Key Takeaway

🎯 Key Insight: Negative numbers can create positive products when multiplied together - track both max and min values!

Asked in

G Google 25 a Amazon 18 M Microsoft 15

Use 2D Dynamic Programming to track both maximum and minimum products at each cell. The key insight is that negative numbers can become positive when multiplied together. Best approach: O(m×n) time, O(m×n) space.

Common Approaches

Approach	Time	Space	Notes
✓ 2D Dynamic Programming	O(m×n)	O(m×n)	Track maximum and minimum products at each cell
Brute Force DFS	O(2^(m+n))	O(m+n)	Try all possible paths using depth-first search

2D Dynamic Programming — Algorithm Steps

Initialize DP arrays for max and min products
For each cell, calculate max/min from top and left neighbors
Handle negative numbers by swapping max/min
Return result from bottom-right cell

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set up DP arrays for max and min products

Fill DP

Calculate max/min from top and left neighbors

Handle Negatives

Swap max/min when multiplying by negative numbers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MOD 1000000007
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

int solution(int** grid, int m, int n) {
    // dp_max[i][j] = maximum product ending at (i,j)
    // dp_min[i][j] = minimum product ending at (i,j)
    long long** dp_max = malloc(m * sizeof(long long*));
    long long** dp_min = malloc(m * sizeof(long long*));
    for (int i = 0; i < m; i++) {
        dp_max[i] = malloc(n * sizeof(long long));
        dp_min[i] = malloc(n * sizeof(long long));
    }
    
    dp_max[0][0] = dp_min[0][0] = grid[0][0];
    
    // Fill first row
    for (int j = 1; j < n; j++) {
        dp_max[0][j] = dp_min[0][j] = dp_max[0][j-1] * grid[0][j];
    }
    
    // Fill first column
    for (int i = 1; i < m; i++) {
        dp_max[i][0] = dp_min[i][0] = dp_max[i-1][0] * grid[i][0];
    }
    
    // Fill rest of the grid
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (grid[i][j] >= 0) {
                dp_max[i][j] = max(dp_max[i-1][j], dp_max[i][j-1]) * grid[i][j];
                dp_min[i][j] = min(dp_min[i-1][j], dp_min[i][j-1]) * grid[i][j];
            } else {
                dp_max[i][j] = min(dp_min[i-1][j], dp_min[i][j-1]) * grid[i][j];
                dp_min[i][j] = max(dp_max[i-1][j], dp_max[i][j-1]) * grid[i][j];
            }
        }
    }
    
    long long result = dp_max[m-1][n-1];
    
    for (int i = 0; i < m; i++) {
        free(dp_max[i]);
        free(dp_min[i]);
    }
    free(dp_max);
    free(dp_min);
    
    return result >= 0 ? result % MOD : -1;
}

int main() {
    // Example grid allocation
    int** grid = malloc(3 * sizeof(int*));
    for (int i = 0; i < 3; i++) {
        grid[i] = malloc(3 * sizeof(int));
    }
    
    // Example: [[-1,-2,-3],[-2,-3,-3],[-3,-3,-2]]
    grid[0][0] = -1; grid[0][1] = -2; grid[0][2] = -3;
    grid[1][0] = -2; grid[1][1] = -3; grid[1][2] = -3;
    grid[2][0] = -3; grid[2][1] = -3; grid[2][2] = -2;
    
    printf("%d\n", solution(grid, 3, 3));
    
    for (int i = 0; i < 3; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Visit each cell once in the m×n grid

✓ Linear Growth

Space Complexity

O(m×n)

Two DP arrays of size m×n for max and min products

⚡ Linearithmic Space

35.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler