# 2906. Construct Product Matrix

## 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 in grid except for the element grid[i][j]. This product is then taken modulo 12345.

Return the product matrix of grid.

Example 1:

Input: grid = [[1,2],[3,4]]
Output: [[24,12],[8,6]]
Explanation: p = grid * grid * grid = 2 * 3 * 4 = 24
p = grid * grid * grid = 1 * 3 * 4 = 12
p = grid * grid * grid = 1 * 2 * 4 = 8
p = grid * grid * grid = 1 * 2 * 3 = 6
So the answer is [[24,12],[8,6]].

Example 2:

Input: grid = [,,]
Output: [,,]
Explanation: p = grid * grid = 2 * 1 = 2.
p = grid * grid = 12345 * 1 = 12345. 12345 % 12345 = 0. So p = 0.
p = grid * grid = 12345 * 2 = 24690. 24690 % 12345 = 0. So p = 0.
So the answer is [,,].

Constraints:

• 1 <= n == grid.length <= 105
• 1 <= m == grid[i].length <= 105
• 2 <= n * m <= 105
• 1 <= grid[i][j] <= 109

## Solutions

• class Solution {
public int[][] constructProductMatrix(int[][] grid) {
final int mod = 12345;
int n = grid.length, m = grid.length;
int[][] p = new int[n][m];
long suf = 1;
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
p[i][j] = (int) suf;
suf = suf * grid[i][j] % mod;
}
}
long pre = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
p[i][j] = (int) (p[i][j] * pre % mod);
pre = pre * grid[i][j] % mod;
}
}
return p;
}
}

• class Solution {
public:
vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
const int mod = 12345;
int n = grid.size(), m = grid.size();
vector<vector<int>> p(n, vector<int>(m));
long long suf = 1;
for (int i = n - 1; i >= 0; --i) {
for (int j = m - 1; j >= 0; --j) {
p[i][j] = suf;
suf = suf * grid[i][j] % mod;
}
}
long long pre = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
p[i][j] = p[i][j] * pre % mod;
pre = pre * grid[i][j] % mod;
}
}
return p;
}
};

• class Solution:
def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
n, m = len(grid), len(grid)
p = [ * m for _ in range(n)]
mod = 12345
suf = 1
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
p[i][j] = suf
suf = suf * grid[i][j] % mod
pre = 1
for i in range(n):
for j in range(m):
p[i][j] = p[i][j] * pre % mod
pre = pre * grid[i][j] % mod
return p


• func constructProductMatrix(grid [][]int) [][]int {
const mod int = 12345
n, m := len(grid), len(grid)
p := make([][]int, n)
for i := range p {
p[i] = make([]int, m)
}
suf := 1
for i := n - 1; i >= 0; i-- {
for j := m - 1; j >= 0; j-- {
p[i][j] = suf
suf = suf * grid[i][j] % mod
}
}
pre := 1
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
p[i][j] = p[i][j] * pre % mod
pre = pre * grid[i][j] % mod
}
}
return p
}

• function constructProductMatrix(grid: number[][]): number[][] {
const mod = 12345;
const [n, m] = [grid.length, grid.length];
const p: number[][] = Array.from({ length: n }, () => Array.from({ length: m }, () => 0));
let suf = 1;
for (let i = n - 1; ~i; --i) {
for (let j = m - 1; ~j; --j) {
p[i][j] = suf;
suf = (suf * grid[i][j]) % mod;
}
}
let pre = 1;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < m; ++j) {
p[i][j] = (p[i][j] * pre) % mod;
pre = (pre * grid[i][j]) % mod;
}
}
return p;
}


• impl Solution {
pub fn construct_product_matrix(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let modulo: i32 = 12345;
let n = grid.len();
let m = grid.len();
let mut p: Vec<Vec<i32>> = vec![vec![0; m]; n];
let mut suf = 1;

for i in (0..n).rev() {
for j in (0..m).rev() {
p[i][j] = suf;
suf = (suf as i64 * grid[i][j] as i64 % modulo as i64) as i32;
}
}

let mut pre = 1;

for i in 0..n {
for j in 0..m {
p[i][j] = (p[i][j] as i64 * pre as i64 % modulo as i64) as i32;
pre = (pre as i64 * grid[i][j] as i64 % modulo as i64) as i32;
}
}

p
}
}