Construct Product Matrix - Practice Coding Problems

Construct Product Matrix - Problem

Given a 0-indexed 2D integer matrix grid of size n * m, we define a 0-indexed 2D matrix p of size n * m as the product matrix of grid if the following condition is met:

Each element p[i][j] is calculated as the product of all elements in grid except for the element grid[i][j]. This product is then taken modulo 12345.

Return the product matrix of grid.

Input & Output

Example 1 — Basic 2x3 Matrix

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

› Output: [[720,360,240],[180,144,120]]

💡 Note: For grid[0][0]=1: product of all others = 2×3×4×5×6 = 720. For grid[1][1]=5: product = 1×2×3×4×6 = 144. Each result taken modulo 12345.

Example 2 — Single Row

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

› Output: [[24,12,8,6]]

💡 Note: For each element, multiply all others: 2×3×4=24, 1×3×4=12, 1×2×4=8, 1×2×3=6

Example 3 — Contains Zero

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

› Output: [[120,0,0],[0,0,0]]

💡 Note: When matrix contains zero, only the zero position gets non-zero result (product of all non-zero elements). All other positions get 0 since they exclude the zero.

Constraints

1 ≤ n, m ≤ 10⁵
1 ≤ n * m ≤ 10⁵
-10⁹ ≤ grid[i][j] ≤ 10⁹
The answer is taken modulo 12345

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D grid with integer values

Calculate Products

For each cell, multiply all other cells

Apply Modulo

Take each result modulo 12345

Key Takeaway

🎯 Key Insight: Use prefix and suffix products to avoid recalculating the same multiplications for each cell

Asked in

G Google 35 a Amazon 28 M Microsoft 22 A Apple 18

The key insight is to avoid recalculating products by using prefix and suffix arrays. Instead of computing O(nm) products for each cell, we precompute prefix products (left to right) and suffix products (right to left), then combine them. Best approach uses prefix product technique with Time: O(nm), Space: O(nm).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Calculate Each Product Separately	O(n²m²)	O(1)	For each cell, multiply all other elements in the matrix
Prefix Product Approach	O(nm)	O(nm)	Use prefix and suffix products to calculate efficiently

Brute Force - Calculate Each Product Separately — Algorithm Steps

Iterate through each cell (i,j) in the matrix
For each cell, iterate through all cells and multiply elements except grid[i][j]
Apply modulo 12345 to the result

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Cell

Choose target cell (i,j)

Multiply Others

Multiply all cells except (i,j)

Apply Modulo

Take result modulo 12345

Code -

solution.c — C

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

int** solution(int** grid, int n, int m, int* returnSize, int** returnColumnSizes) {
    *returnSize = n;
    *returnColumnSizes = (int*)malloc(n * sizeof(int));
    int** result = (int**)malloc(n * sizeof(int*));
    const int MOD = 12345;
    
    for (int i = 0; i < n; i++) {
        (*returnColumnSizes)[i] = m;
        result[i] = (int*)malloc(m * sizeof(int));
        
        for (int j = 0; j < m; j++) {
            long long product = 1;
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < m; c++) {
                    if (r != i || c != j) {
                        product = (product * grid[r][c]) % MOD;
                    }
                }
            }
            result[i][j] = product;
        }
    }
    
    return result;
}

int main() {
    // Simple input parsing for demo
    int n = 2, m = 3;
    int** grid = (int**)malloc(n * sizeof(int*));
    grid[0] = (int*)malloc(m * sizeof(int));
    grid[1] = (int*)malloc(m * sizeof(int));
    
    // Example: [[1,2,3],[4,5,6]]
    grid[0][0] = 1; grid[0][1] = 2; grid[0][2] = 3;
    grid[1][0] = 4; grid[1][1] = 5; grid[1][2] = 6;
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(grid, n, m, &returnSize, &returnColumnSizes);
    
    // Print result
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²m²)

For each of nm cells, we iterate through all nm cells to calculate product

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Brute Force - Calculate Each Product Separately — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler