Construct Product Matrix — Medium Problem & Solution

Problem statement

Given an m × n grid, build the product matrix p, where p[i][j] is the product of all elements of grid except grid[i][j], taken modulo 12345.

Example 1

Input: grid = [[1,2],[3,4]]
Output: [[24,12],[8,6]]
Explanation: `p[0][0] = 2 · 3 · 4 = 24`.

Example 2

Input: grid = [[12345],[2],[1]]
Output: [[2],[0],[0]]
Explanation: `12345 % 12345` is 0, so every cell but the first becomes 0.

Example 3

Input: grid = [[1,1,1]]
Output: [[1,1,1]]

Constraints

• m == grid.length
• n == grid[i].length
• 2 <= m * n <= 10^5
• 1 <= grid[i][j] <= 10^9

How to solve Construct Product Matrix

Read the grid as one flat sequence. The product of everything except position k is the product of everything before it times the product of everything after it — two running products, no division.

Approach

1. Compute pre[k] = product of the first k elements, mod 12345.
2. Sweep from the end keeping suf = product of everything after the current position.
3. Set p[k] = pre[k] · suf, then fold the current element into suf.
4. Reshape the flat answers back into m × n.

Why it works

The obvious trick — divide the total product by grid[i][j] — fails because 12345 = 3 · 5 · 823 is composite, so an element sharing a factor with it has no inverse and a zero total product destroys the information. Prefix-suffix products avoid inverses entirely, which is the whole point of the problem.

Complexity

• Time — O(m · n)
• Space — O(m · n)

Pitfalls

• Dividing by the element is wrong under a composite modulus.
• Reduce each element mod 12345 before multiplying, or the intermediate exceeds 32 bits.
• The suffix must exclude the current element, so fold it in after writing the answer.

Reference solution

Python

from typing import List

def constructProductMatrix(grid: List[List[int]]) -> List[List[int]]:
    MOD = 12345
    m, n = len(grid), len(grid[0])
    flat = [grid[i][j] % MOD for i in range(m) for j in range(n)]
    total = m * n
    pre = [1] * (total + 1)
    for k in range(total):
        pre[k + 1] = pre[k] * flat[k] % MOD
    val = [0] * total
    suf = 1
    for k in range(total - 1, -1, -1):
        val[k] = pre[k] * suf % MOD
        suf = suf * flat[k] % MOD
    return [val[i * n:(i + 1) * n] for i in range(m)]

JavaScript

var constructProductMatrix = function(grid) {
    var MOD = 12345;
    var m = grid.length, n = grid[0].length, i, j, k;
    var total = m * n;
    var flat = [];
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) flat.push(grid[i][j] % MOD);
    }
    var pre = [1];
    for (k = 0; k < total; k++) pre.push((pre[k] * flat[k]) % MOD);
    var val = new Array(total);
    var suf = 1;
    for (k = total - 1; k >= 0; k--) {
        val[k] = (pre[k] * suf) % MOD;
        suf = (suf * flat[k]) % MOD;
    }
    var out = [];
    for (i = 0; i < m; i++) out.push(val.slice(i * n, i * n + n));
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium