Construct Product Matrix — Solution in Python, Java & C++
Construct Product Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Construct Product Matrix is a medium coding problem on arrays, matrix and prefix sum, asked in Amazon, Google and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Prefix Sum
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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.lengthn == grid[i].length2 <= m * n <= 10^51 <= grid[i][j] <= 10^9
Hints for Construct Product Matrix
Hint 1
Division is not available:
12345is not prime, so many elements have no modular inverse.Hint 2
Flatten the grid and think about products of prefixes and suffixes.
Hint 3
p[k] = prefix[k] · suffix[k + 1].
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
- Compute
pre[k]= product of the firstkelements, mod12345. - Sweep from the end keeping
suf= product of everything after the current position. - Set
p[k] = pre[k] · suf, then fold the current element intosuf. - 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
12345before 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)]Java
public static int[][] constructProductMatrix(int[][] grid) {
final int MOD = 12345;
int m = grid.length, n = grid[0].length;
int total = m * n;
int[] flat = new int[total];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) flat[i * n + j] = grid[i][j] % MOD;
}
int[] pre = new int[total + 1];
pre[0] = 1;
for (int k = 0; k < total; k++) pre[k + 1] = (int) ((long) pre[k] * flat[k] % MOD);
int[] val = new int[total];
long suf = 1;
for (int k = total - 1; k >= 0; k--) {
val[k] = (int) (pre[k] * suf % MOD);
suf = suf * flat[k] % MOD;
}
int[][] out = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) out[i][j] = val[i * n + j];
}
return out;
}C++
vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
const long long MOD = 12345;
int m = (int) grid.size(), n = (int) grid[0].size();
int total = m * n;
vector<long long> flat(total);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) flat[i * n + j] = grid[i][j] % MOD;
}
vector<long long> pre(total + 1, 1);
for (int k = 0; k < total; k++) pre[k + 1] = pre[k] * flat[k] % MOD;
vector<vector<int>> out(m, vector<int>(n, 0));
long long suf = 1;
for (int k = total - 1; k >= 0; k--) {
out[k / n][k % n] = (int) (pre[k] * suf % MOD);
suf = suf * flat[k] % MOD;
}
return out;
}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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal