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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6

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 <= 10^5
  • 1 <= m == grid[i].length <= 10^5
  • 2 <= n * m <= 10^5
  • 1 <= grid[i][j] <= 10^9

Solution

Method 1 – Prefix and Suffix Product (No Division)

Intuition

To compute the product of all elements except grid[i][j] for each cell, we can flatten the matrix, compute prefix and suffix products, and then reconstruct the result. This avoids division and works for any grid shape.

Approach

  1. Flatten the grid into a 1D array.
  2. Compute prefix products: prefix[i] = product of all elements before i.
  3. Compute suffix products: suffix[i] = product of all elements after i.
  4. For each cell, the result is prefix[i] * suffix[i] modulo 12345.
  5. Reshape the result back to the original grid shape.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<int> flat;
        for (auto& row : grid) for (int x : row) flat.push_back(x);
        int sz = n * m;
        vector<int> pre(sz+1, 1), suf(sz+1, 1);
        for (int i = 0; i < sz; ++i) pre[i+1] = pre[i] * flat[i] % 12345;
        for (int i = sz-1; i >= 0; --i) suf[i] = suf[i+1] * flat[i] % 12345;
        vector<vector<int>> ans(n, vector<int>(m));
        for (int i = 0; i < sz; ++i) ans[i/m][i%m] = pre[i] * suf[i+1] % 12345;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func ConstructProductMatrix(grid [][]int) [][]int {
    n, m := len(grid), len(grid[0])
    sz := n * m
    flat := make([]int, sz)
    k := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            flat[k] = grid[i][j]
            k++
        }
    }
    pre := make([]int, sz+1)
    suf := make([]int, sz+1)
    pre[0], suf[sz] = 1, 1
    for i := 0; i < sz; i++ { pre[i+1] = pre[i] * flat[i] % 12345 }
    for i := sz-1; i >= 0; i-- { suf[i] = suf[i+1] * flat[i] % 12345 }
    ans := make([][]int, n)
    for i := 0; i < n; i++ { ans[i] = make([]int, m) }
    for i := 0; i < sz; i++ { ans[i/m][i%m] = pre[i] * suf[i+1] % 12345 }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int[][] constructProductMatrix(int[][] grid) {
        int n = grid.length, m = grid[0].length, sz = n * m;
        int[] flat = new int[sz];
        int k = 0;
        for (int[] row : grid) for (int x : row) flat[k++] = x;
        int[] pre = new int[sz+1], suf = new int[sz+1];
        pre[0] = suf[sz] = 1;
        for (int i = 0; i < sz; i++) pre[i+1] = pre[i] * flat[i] % 12345;
        for (int i = sz-1; i >= 0; i--) suf[i] = suf[i+1] * flat[i] % 12345;
        int[][] ans = new int[n][m];
        for (int i = 0; i < sz; i++) ans[i/m][i%m] = pre[i] * suf[i+1] % 12345;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun constructProductMatrix(grid: Array<IntArray>): Array<IntArray> {
        val n = grid.size; val m = grid[0].size; val sz = n * m
        val flat = IntArray(sz)
        var k = 0
        for (row in grid) for (x in row) flat[k++] = x
        val pre = IntArray(sz+1) { 1 }; val suf = IntArray(sz+1) { 1 }
        for (i in 0 until sz) pre[i+1] = pre[i] * flat[i] % 12345
        for (i in sz-1 downTo 0) suf[i] = suf[i+1] * flat[i] % 12345
        val ans = Array(n) { IntArray(m) }
        for (i in 0 until sz) ans[i/m][i%m] = pre[i] * suf[i+1] % 12345
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def constructProductMatrix(self, grid: list[list[int]]) -> list[list[int]]:
        n, m = len(grid), len(grid[0])
        flat = [x for row in grid for x in row]
        sz = n * m
        pre = [1] * (sz + 1)
        suf = [1] * (sz + 1)
        for i in range(sz):
            pre[i+1] = pre[i] * flat[i] % 12345
        for i in range(sz-1, -1, -1):
            suf[i] = suf[i+1] * flat[i] % 12345
        ans = [[0]*m for _ in range(n)]
        for i in range(sz):
            ans[i//m][i%m] = pre[i] * suf[i+1] % 12345
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn construct_product_matrix(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = grid.len(); let m = grid[0].len(); let sz = n * m;
        let flat: Vec<i32> = grid.iter().flat_map(|row| row.iter()).cloned().collect();
        let mut pre = vec![1; sz+1];
        let mut suf = vec![1; sz+1];
        for i in 0..sz { pre[i+1] = pre[i] * flat[i] % 12345; }
        for i in (0..sz).rev() { suf[i] = suf[i+1] * flat[i] % 12345; }
        let mut ans = vec![vec![0; m]; n];
        for i in 0..sz { ans[i/m][i%m] = pre[i] * suf[i+1] % 12345; }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    constructProductMatrix(grid: number[][]): number[][] {
        const n = grid.length, m = grid[0].length, sz = n * m;
        const flat: number[] = grid.flat();
        const pre = Array(sz+1).fill(1), suf = Array(sz+1).fill(1);
        for (let i = 0; i < sz; i++) pre[i+1] = pre[i] * flat[i] % 12345;
        for (let i = sz-1; i >= 0; i--) suf[i] = suf[i+1] * flat[i] % 12345;
        const ans: number[][] = Array.from({length: n}, () => Array(m));
        for (let i = 0; i < sz; i++) ans[Math.floor(i/m)][i%m] = pre[i] * suf[i+1] % 12345;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n*m), where n and m are the dimensions of grid. Each element is processed a constant number of times.
  • 🧺 Space complexity: O(n*m), for the flattened array and prefix/suffix arrays.