MediumNo. 2906
Construct Product Matrix — LeetCode 2906 Python Solution
- Pattern
- Prefix Sum
- Topics
- Array, Matrix, Prefix Sum
- Reading time
- 3 min
- Source
- leetcode.com
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 in grid except for the element grid[i][j]. This product is then taken modulo 12345.
Example
- 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
Python solution
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 pComplexity
- Time
- O(n × m)where n and m are the number of rows and columns in the matrix, respectively
- Space · auxiliary
- O(1)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2906. Construct Product Matrix is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0304 | Range Sum Query 2D - Immutable | Medium |
| 1314 | Matrix Block Sum | Medium |
| 1895 | Largest Magic Square | Medium |
| 2017 | Grid Game | Medium |
| 2245 | Maximum Trailing Zeros in a Cornered Path | Medium |
| 2428 | Maximum Sum of an Hourglass | Medium |
Frequently asked questions
- How hard is LeetCode 2906. Construct Product Matrix?
LeetCode 2906. Construct Product Matrix is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2906. Construct Product Matrix?
The Python solution on this page runs in O(n × m), where n and m are the number of rows and columns in the matrix, respectively.
- What is the space complexity of LeetCode 2906. Construct Product Matrix?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2906. Construct Product Matrix cover?
LeetCode 2906. Construct Product Matrix is tagged Array, Matrix and Prefix Sum on LeetCode.