Description
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 ingridexcept for the elementgrid[i][j]. This product is then taken modulo12345.
Return the product matrix of grid.
Example 1:
Input: grid = [[1,2],[3,4]] Output: [[24,12],[8,6]] Explanation: p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24 p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12 p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8 p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6 So the answer is [[24,12],[8,6]].
Example 2:
Input: grid = [[12345],[2],[1]] Output: [[2],[0],[0]] Explanation: p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2. p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0. So p[0][1] = 0. p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0. So p[0][2] = 0. So the answer is [[2],[0],[0]].
Constraints:
1 <= n == grid.length <= 1051 <= m == grid[i].length <= 1052 <= n * m <= 1051 <= grid[i][j] <= 109
Solutions
This code computes a product matrix where each element is replaced by the product of all other elements in the grid (excluding itself), using modulo 12345. The algorithm flattens the 2D grid into a 1D array and uses two passes: first, it builds a prefix array that stores the cumulative product of all elements before each position, and a suffix array that stores the cumulative product of all elements after each position (computed by traversing the grid in reverse). Then, in a second pass, it reconstructs the result grid by multiplying the prefix and suffix values at each position—the product before and product after that element—giving the desired product of all other elements. The modulo operation % MOD keeps values within bounds throughout the computation.
/**
* @param {number[][]} grid
* @return {number[][]}
*/
var constructProductMatrix = function(grid) {
const m = grid.length;
const n = grid[0].length;
const len = m * n;
const prefix = new Array(len).fill(1);
const suffix = new Array(len).fill(1);
const MOD = 12345;
for (let row = 0; row < m; row++) {
for (let col = 0; col < n; col++) {
const pos = row * n + col;
const before = pos > 0 ? prefix[pos - 1] : 1;
prefix[pos] = (before * grid[row][col]) % MOD;
const rev = len - 1 - pos;
const after = rev < len - 1 ? suffix[rev + 1] : 1;
suffix[rev] = (after * grid[m - 1 - row][n - 1 - col]) % MOD;
}
}
for (let row = 0; row < m; row++) {
for (let col = 0; col < n; col++) {
const pos = row * n + col;
const before = pos > 0 ? prefix[pos - 1] : 1;
const after = pos < len - 1 ? suffix[pos + 1] : 1;
grid[row][col] = (before * after) % MOD;
}
}
return grid;
};