Leetcode 2906. Construct Product Matrix
Problem Statement
Given a 0-indexed 2D integer array grid of size n × m, construct a 2D array p of the same dimensions such that:
grid except grid[i][j], taken modulo 12345.
In other words — for every cell, multiply together every other cell in the entire matrix (not just the row or column), then take mod 12345.
Intuition
Think of the flattened 1D sequence of all elements. For any index i, the product of everything except element i can be split into two parts:
We call these two parts the prefix product and the suffix product. If we compute both in two separate linear sweeps, we get the answer for every cell in just O(n×m) time — far better than the O(n²m²) brute force.
This is the classic "product of array except self" technique, extended to a 2D grid by flattening it row-by-row.
Approach — Step by Step
Flatten the 2D grid conceptually
We don't create a new array — we use the index formula row = i/m, col = i%m to treat grid as 1D. Total length N = n × m.
Prefix pass — left to right
Iterate i from 0 to N−1. Store into result[i/m][i%m] the running product of all elements before index i. Start with prefix = 1.
Suffix pass — right to left, in-place
Iterate i from N−1 down to 0. Multiply each result[i] by a running suffix variable (product of all elements after i). Update suffix after each step.
Apply modulo at every step
Take % 12345 after each multiplication to keep values small and prevent overflow. Use long for intermediate products before casting back to int.
Walkthrough — Example
Input: grid = [[1,2,3],[4,5,6]] → flattened: [1, 2, 3, 4, 5, 6]
For index 2 (value = 3): prefix[2] = 1×2 = 2, suffix[2] = 4×5×6 = 120 → result = 2×120 = 240 ✓
Java Solution
1class Solution {
2 public int[][] constructProductMatrix(int[][] grid) {
3 int n = grid.length, m = grid[0].length;
4 int N = n * m;
5 final int MOD = 12345;
6
7 int[][] result = new int[n][m];
8
9 // Pass 1: prefix sweep (left → right)
10 long prefix = 1;
11 for (int i = 0; i < N; i++) {
12 result[i / m][i % m] = (int) prefix;
13 prefix = prefix * grid[i / m][i % m] % MOD;
14 }
15
16 // Pass 2: suffix sweep (right → left), in-place
17 long suffix = 1;
18 for (int i = N - 1; i >= 0; i--) {
19 result[i / m][i % m] = (int) (result[i / m][i % m] * suffix % MOD);
20 suffix = suffix * grid[i / m][i % m] % MOD;
21 }
22
23 return result;
24 }
25}
long for prefix and suffix?Complexity Analysis
Time complexity: O(n × m) — Two single passes over the flattened 1D array of length N = n×m. Each element is visited exactly twice.
Space complexity: O(1) extra — We use only two scalar variables (prefix and suffix) beyond the output array. The output grid itself is O(n×m) but is required by the problem.
Other Approaches
| Approach | Time | Space | Verdict |
|---|---|---|---|
| Brute Force Nested loops per cell |
O(n²m²) | O(1) | TLE |
| Prefix + Suffix ★ Two linear sweeps |
O(nm) | O(1) | Optimal |
| Log-Sum Trick log(product) = sum of logs |
O(nm) | O(nm) | Wrong — float errors |
| Modular Inverse Fermat's little theorem |
O(nm log p) | O(1) | Fails — 12345 not prime |