Practice Construct Product Matrix
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Return a matrix of the same dimensions as grid whose entry at each position is the product of every grid entry except the entry at that position, modulo 12345.
Source: Construct Product Matrix on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
grid = [[1,2],[3,4]]
[[24,12],[8,6]]
For the cell containing 1, multiply the other values: 2 * 3 * 4 = 24. Excluding 2 gives 1 * 3 * 4 = 12; excluding 3 gives 1 * 2 * 4 = 8; excluding 4 gives 1 * 2 * 3 = 6. These results are already below 12345 and keep their original positions, yielding [[24,12],[8,6]]. A prefix product before each flattened position multiplied by its suffix product after that position excludes exactly that one entry without dividing.
# Example 2
grid = [[12345],[2],[1]]
[[2],[0],[0]]
Excluding 12345 leaves 2 * 1 = 2. Excluding 2 leaves 12345 * 1, whose remainder modulo 12345 is 0. Excluding 1 leaves 12345 * 2, which also has remainder 0. The result is [[2],[0],[0]]. Although every input is positive, a factor can become zero after taking the modulus. Do not reduce the total product and then divide by the current entry: the reduced total is zero here and cannot recover the first answer. Prefix and suffix products avoid modular division entirely.
Constraints
How to solve Construct Product Matrix
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Flatten the grid in row-major order and treat it as product-except-self: each answer is the product of everything before the position times the product of everything after it, both reduced modulo 12345. Division never appears, which matters because 12345 is composite and modular inverses generally do not exist.
Why brute force is not enough
Recomputing the product of all other cells for every position is O((n*m)^2), about 10^10 for n*m up to 10^5. Dividing a total product by each entry fails twice: the reduced total may be zero, and division modulo a composite number is undefined for entries sharing a factor with 12345.
Approach
- Allocate the output with the grid's shape and view its cells as one sequence of length n*m.
- Forward pass: keep a running prefix product modulo 12345 and, before folding in the current cell, store the prefix into the output cell, so each output cell holds the product of all earlier cells.
- Backward pass: keep a running suffix product; at each cell multiply the stored prefix by the suffix, reduce, and only then fold the cell's own value into the suffix.
- Reduce each grid value modulo 12345 before multiplying so intermediates stay near 1.5 * 10^8 and fit comfortably in 64-bit arithmetic.
Walkthrough of Example 2
grid = [[12345],[2],[1]] → [[2],[0],[0]]
- Flattened cells are 12345, 2, 1.
- Forward pass from prefix 1: cell 0 stores 1 and the prefix becomes 12345 mod 12345 = 0; cells 1 and 2 store 0 and the prefix stays 0.
- Backward pass from suffix 1: cell 2 becomes 0 * 1 = 0, suffix becomes 1.
- Cell 1 becomes 0 * 1 = 0, suffix becomes 2.
- Cell 0 becomes 1 * 2 = 2. Reshaped, the result is [[2],[0],[0]].
Time and space
Time O(n * m) · Space O(1). Both passes visit each of the n*m cells once with constant work, and beyond the required output only two running products are kept.
Interview pitfalls
- Dividing the total product by each entry; 12345 = 3 * 5 * 823 is not prime, so entries divisible by 3, 5 or 823 have no inverse.
- Multiplying raw values up to 10^9 into a running product before reducing, overflowing 64 bits within a few steps.
- Inconsistent conversion between flat index and (row, column) for single-row or single-column grids.
- Assuming results are nonzero because inputs are positive; a product can legitimately reduce to 0.
- Allocating separate prefix and suffix arrays when the output matrix can hold the prefix values.
Follow-up questions interviewers ask
- How would you exclude an entire row and column rather than a single cell?
- With a prime modulus, would dividing by modular inverses be acceptable, and what about entries that are multiples of the prime?
- How would you support point updates followed by single-cell queries, perhaps with a segment tree of modular products?
Further reading on the technique: Prefix sum
Related LeetCode Problems
Practice more problems similar to Construct Product Matrix.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.