Welcome to Subscribe On Youtube

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]mod12345$. 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]mod12345$. 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)$.

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• 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;
      }
  };
  

• 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
  
  

• 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
      }
  }
  
  

All Problems

All Solutions