Construct Product Matrix solution and explanation
Google
9 more videos on this problem
Construct Product Matrix | Simplified Approach | Dry Run | Leetcode 2906 | codestorywithMIKcodestorywithMIK · 17:57 · 8K views
2906. Construct Product Matrix || Leetcode Weekly Contest 367Ashish Kumar · 16:50 · 902 views
2906. Construct Product Matrix (Leetcode Medium)Programming Live with Larry · 23:04 · 473 views
Daily Leetcode #2184: Mar 24, 2026 - 2906. Construct Product MatrixProgramming Live with Larry · 17:36 · 471 views
2906. Construct Product Matrix | Leetcode Daily - PythonLeetcode Daily · 7:51 · 447 views
Construct Product Matrix | Leetcode 2906 | Java HindiKernel Queen 👑 · 7:21 · 274 views
Construct Product Matrix | LeetCode 2906 - Python (3 Solutions)impoldev · 12:13 · 237 views
Leetcode |2906 Construct Product Matrix | Java | Prefix ConceptCakot Coding · 22:25 · 151 views
Construct Product Matrix | LeetCode 2906 | Prefix-Suffix Product | Java Code | Developer CoderDeveloper Coder · 21:00 · 119 views
👉 2906. Construct Product Matrix | POTD 24 March 2026 | C++ | LeetCode SolutionTechie On Track · 8:04 · 36 views
The problem
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
Approach overview
Problem Overview: You are given an m x n grid. For every cell (i, j), compute the product of all elements in the matrix except grid[i][j]. Each result must be returned modulo 12345. The challenge is avoiding repeated multiplication across the entire matrix for every cell.
Approach 1: Brute Force Multiplication (O((mn)^2) time, O(1) space)
The most direct approach iterates through the matrix and recomputes the product of all elements except the current one. For each position (i, j), traverse the entire grid again and multiply every value except that cell. Apply modulo 12345 during multiplication to keep numbers small. This approach works but quickly becomes inefficient because each of the mn cells requires scanning the entire matrix again. Time complexity becomes O((mn)^2), which is too slow when the grid contains many elements.
Approach 2: Prefix and Suffix Decomposition (O(mn) time, O(mn) space)
The key insight is identical to the classic "product of array except self" pattern. Flatten the matrix conceptually into a 1D sequence of length mn. Instead of recomputing products repeatedly, build prefix and suffix products. The prefix array stores the product of all elements before index k, while the suffix array stores the product of all elements after k. The result for each position becomes (prefix[k] * suffix[k]) % 12345. Finally map the flattened index back into the array position (i, j).
This works because every element's contribution is captured either in the prefix or suffix side. Multiplication is performed exactly once per element in each pass. The algorithm performs two linear scans across the matrix elements, giving O(mn) time complexity. Extra storage for prefix and suffix products results in O(mn) space, although careful implementation can reduce auxiliary memory. The idea is closely related to prefix computation techniques often used to reuse partial results efficiently.
Recommended for interviews: The prefix and suffix decomposition approach is the expected solution. It demonstrates recognition of the "product except self" pattern and the ability to adapt it to a 2D matrix with modular arithmetic. Mentioning the brute force approach first shows you understand the baseline, but implementing the prefix–suffix method shows strong algorithmic optimization skills.
Solution
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 pclass 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;
}
};/**
* @param {number[][]} grid
* @return {number[][]}
*/
var constructProductMatrix = function (grid) {
const mod = 12345;
const [n, m] = [grid.length, grid[0].length];
const p = 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;
};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;
}public class Solution {
public int[][] ConstructProductMatrix(int[][] grid) {
const int mod = 12345;
int n = grid.Length, m = grid[0].Length;
int[][] p = new int[n][];
for (int i = 0; i < n; ++i) {
p[i] = new int[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;
}
}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
}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
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Multiplication | O((mn)^2) | O(1) | Useful only for understanding the baseline logic or when the matrix is extremely small |
| Prefix and Suffix Decomposition | O(mn) | O(mn) | Optimal general solution; avoids recomputing products and scales well for large matrices |
Frequently asked questions
Is Construct Product Matrix easy or hard?
Construct Product Matrix is generally considered a medium-level problem. The brute force idea is simple, but recognizing the prefix–suffix product pattern and applying it to a 2D matrix with modular arithmetic requires solid algorithmic intuition.
Construct Product Matrix Python/Java solution
Most implementations compute prefix and suffix products in two passes and store the result in a 2D matrix. The logic is identical across languages like Python, Java, C++, Go, JavaScript, Rust, and C#, with only syntax differences in array traversal and modular multiplication.
How to solve Construct Product Matrix in O(n)?
Flatten the matrix conceptually into a list of length mn and compute prefix products where prefix[i] is the product of all previous elements. Then compute suffix products from the right and multiply prefix[i] and suffix[i] to get the result for that position. Apply modulo 12345 at each multiplication step to keep values bounded.
What is the best approach for Construct Product Matrix?
The most efficient solution uses prefix and suffix products. Treat the matrix as a flattened array of size mn, compute prefix products from the left and suffix products from the right, then multiply them for each position. This avoids recomputing the full matrix product for every cell and runs in O(mn) time.
Is Construct Product Matrix asked at Google/Amazon/Meta?
Matrix transformation and prefix product patterns frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the underlying technique is closely related to the classic 'Product of Array Except Self' question commonly asked in interviews.
What data structure is used in Construct Product Matrix?
The solution primarily uses arrays to store prefix and suffix products. The matrix itself is traversed in row-major order and treated as a flattened sequence, which allows efficient product reuse across positions.
What is the time complexity of Construct Product Matrix?
The optimal prefix–suffix approach runs in O(mn) time where m and n are the matrix dimensions. Each element is processed twice—once in the prefix pass and once in the suffix pass. The brute force approach takes O((mn)^2) time because it recomputes the entire product for every cell.