Question

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[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 <= 105
• 1 <= m == grid[i].length <= 105
• 2 <= n * m <= 105
• 1 <= grid[i][j] <= 109

Solutions

Solution 1: Prefix and Suffix Decomposition

We can preprocess the suffix product (excluding itself) of each element, and then traverse the matrix to calculate the prefix product (excluding itself) of each element. The product of the two gives us the result for each position.

Specifically, we use $p[i][j]$ to represent the result of the element in the $i$-th row and $j$-th column of the matrix. We define a variable $suf$ to represent the product of all elements below and to the right of the current position. Initially, $suf$ is set to $1$. We start traversing from the bottom right corner of the matrix. For each position $(i, j)$, we assign $suf$ to $p[i][j]$, and then update $suf$ to $suf \times grid[i][j] \bmod 12345$. This way, we can obtain the suffix product of each position.

Next, we start traversing from the top left corner of the matrix. For each position $(i, j)$, we multiply $p[i][j]$ by $pre$, take the result modulo $12345$, and then update $pre$ to $pre \times grid[i][j] \bmod 12345$. This way, we can obtain the prefix product of each position.

After the traversal, we return the result matrix $p$.

The time complexity is $O(n \times m)$, where $n$ and $m$ are the number of rows and columns in the matrix, respectively. Ignoring the space occupied by the result matrix, the space complexity is $O(1)$.

class Solution:
  def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
    n, m = len(grid), len(grid[0])
    p = [[0] * 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

class Solution {
  public int[][] constructProductMatrix(int[][] grid) {
    final int mod = 12345;
    int n = grid.length, m = grid[0].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[0].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;
  }
};

func constructProductMatrix(grid [][]int) [][]int {
  const mod int = 12345
  n, m := len(grid), len(grid[0])
  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[0].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[0].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
  }
}