Watch 10 video solutions for Construct Product Matrix, a medium level problem involving Array, Matrix, Prefix Sum. This walkthrough by codestorywithMIK has 7,890 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 <= 1051 <= m == grid[i].length <= 1052 <= n * m <= 1051 <= grid[i][j] <= 109Problem 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.
| 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 |