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 ingridexcept for the elementgrid[i][j]. This product is then taken modulo12345.
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 <= 1051 <= m == grid[i].length <= 1052 <= n * m <= 1051 <= 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 { 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 } }