Construct product matrix

Array Matrix Prefix Sum

32.1% acceptance

Feb 25, 2026

261

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn construct_product_matrix(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    const MODULO: i64 = 12345;
    let n = grid.len();
    let m = grid[0].len();
    let total = n * m;

    let flat: Vec<i64> = grid.iter()
      .flat_map(|r| r.iter().map(|&x| x as i64 % MODULO))
      .collect();

    let mut prefix = vec![1i64; total + 1];
    for i in 0..total {
      prefix[i + 1] = prefix[i] * flat[i] % MODULO;
    }

    let mut suffix = vec![1i64; total + 1];
    for i in (0..total).rev() {
      suffix[i] = suffix[i + 1] * flat[i] % MODULO;
    }

    let mut result = vec![vec![0i32; m]; n];
    for i in 0..n {
      for j in 0..m {
        let idx = i * m + j;
        result[i][j] = (prefix[idx] * suffix[idx + 1] % MODULO) as i32;
      }
    }
    result
  }
}