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

• 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