LeetCode 2906 - Construct Product Matrix

The problem asks us to construct a new matrix p from a given matrix grid. For every position (i, j), the value p[i][j] must equal the product of every element in the matrix except grid[i][j], and the result must be taken modulo 12345.

leetcodemediumarraymatrixprefix-sum

LeetCode Problem 2906

Difficulty: 🟡 Medium
Topics: Array, Matrix, Prefix Sum

Solution

Problem Understanding

The problem asks us to construct a new matrix p from a given matrix grid. For every position (i, j), the value p[i][j] must equal the product of every element in the matrix except grid[i][j], and the result must be taken modulo 12345.

In other words, if the matrix contains k = n * m elements in total, then for each cell we multiply the other k - 1 elements together.

For example, suppose the matrix is:

[[1, 2],
 [3, 4]]

For cell (0,0), we exclude 1 and multiply:

2 * 3 * 4 = 24

For cell (0,1), we exclude 2 and multiply:

1 * 3 * 4 = 12

The same logic applies to every position.

The constraints are extremely important:

  • n * m <= 10^5
  • Each value can be as large as 10^9

A naive solution that recomputes the product for every cell would require iterating through the entire matrix repeatedly, which would be far too slow.

Another important observation is that the modulus 12345 is not prime. That means we cannot safely use modular division or modular inverses. Many product-array problems use total product divided by current element, but that approach does not work reliably here.

The constraints guarantee:

  • The matrix always contains at least two elements.
  • All numbers are positive.
  • The matrix can be very tall or very wide, but the total number of elements is at most 100000.

Several edge cases are important:

  • A value may already be divisible by 12345, causing products to become 0 mod 12345.
  • A single row or single column matrix still needs correct handling.
  • Large values require modular multiplication throughout to avoid overflow and unnecessary huge numbers.
  • Since division cannot be used, we need a multiplication-only strategy.

Approaches

Brute Force Approach

The most straightforward solution is to compute every answer independently.

For each cell (i, j):

  1. Initialize a product variable to 1.
  2. Iterate through the entire matrix.
  3. Multiply every element except grid[i][j].
  4. Take modulo 12345.
  5. Store the result.

This approach is correct because it directly follows the problem definition. However, it is computationally expensive.

If the matrix contains k = n * m elements, then for every one of the k positions we iterate through all k elements again.

This produces a time complexity of:

O(k^2)

Since k can be 100000, this would require up to 10^10 operations, which is completely infeasible.

Key Insight

The problem is essentially a 2D version of the classic "product of array except self" problem.

Instead of recomputing products repeatedly, we can flatten the matrix into a one-dimensional sequence and use:

  • Prefix products
  • Suffix products

For every index:

answer[i] = product of elements before i
          * product of elements after i

This works because every element except the current one belongs either to the left side or the right side.

Since division is not used, the method works even though 12345 is not prime.

We compute:

  • Prefix product while scanning left to right
  • Suffix product while scanning right to left

Each position is processed only a constant number of times.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((n*m)^2) O(1) extra Recomputes full product for every cell
Optimal O(n*m) O(n*m) Uses prefix and suffix products

Algorithm Walkthrough

Optimal Prefix-Suffix Product Algorithm

  1. Flatten the matrix logically into a one-dimensional traversal order.

We do not necessarily need to create a separate flattened array, but conceptually the matrix becomes:

index = i * m + j

This allows us to treat the matrix like a single array. 2. Create an output array of size n * m.

This array will temporarily store prefix products and later final answers. 3. Perform a left-to-right pass to compute prefix products.

Maintain a running product variable called prefix.

For each index:

  • Store the current prefix product into the answer array.
  • Multiply prefix by the current grid value.
  • Apply modulo 12345.

After this step:

answer[i] = product of all elements before i
  1. Perform a right-to-left pass to compute suffix products.

Maintain another running product variable called suffix.

For each index from right to left:

  • Multiply answer[i] by suffix.
  • Apply modulo 12345.
  • Multiply suffix by the current grid value.
  • Apply modulo 12345.

Now:

answer[i] =
    (product before i) *
    (product after i)

which equals the product of all elements except itself. 5. Convert the one-dimensional answer array back into a 2D matrix.

Since the original matrix dimensions are known, reconstruct rows of length m.

Why it works

For every position i, every element except grid[i] lies either before it or after it in traversal order.

The prefix pass computes:

product of all elements before i

The suffix pass computes:

product of all elements after i

Multiplying them together gives exactly the product of every element except the current one.

Because multiplication is associative, the order does not matter. Since modulo arithmetic is applied consistently after every multiplication, the final values are correct modulo 12345.

Python Solution

from typing import List

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        MOD = 12345
        
        n = len(grid)
        m = len(grid[0])
        size = n * m
        
        result = [1] * size
        
        prefix = 1
        
        # Prefix products
        for idx in range(size):
            row = idx // m
            col = idx % m
            
            result[idx] = prefix
            
            prefix = (prefix * grid[row][col]) % MOD
        
        suffix = 1
        
        # Suffix products
        for idx in range(size - 1, -1, -1):
            row = idx // m
            col = idx % m
            
            result[idx] = (result[idx] * suffix) % MOD
            
            suffix = (suffix * grid[row][col]) % MOD
        
        # Convert back to 2D matrix
        answer = []
        
        for i in range(n):
            row_start = i * m
            answer.append(result[row_start:row_start + m])
        
        return answer

The implementation begins by determining the matrix dimensions and total number of elements.

The result array initially stores prefix products. During the first traversal, result[idx] receives the product of all previous elements.

The prefix variable continuously accumulates products modulo 12345.

The second traversal moves from right to left. The suffix variable stores the product of all elements after the current index. Multiplying the stored prefix product with the current suffix product produces the final answer for that position.

Finally, the flat array is reshaped into a matrix using slicing.

The algorithm never uses division, which is critical because modular inverses are not guaranteed to exist under modulus 12345.

Go Solution

func constructProductMatrix(grid [][]int) [][]int {
	const MOD = 12345

	n := len(grid)
	m := len(grid[0])
	size := n * m

	result := make([]int, size)

	prefix := 1

	// Prefix products
	for idx := 0; idx < size; idx++ {
		row := idx / m
		col := idx % m

		result[idx] = prefix

		prefix = (prefix * grid[row][col]) % MOD
	}

	suffix := 1

	// Suffix products
	for idx := size - 1; idx >= 0; idx-- {
		row := idx / m
		col := idx % m

		result[idx] = (result[idx] * suffix) % MOD

		suffix = (suffix * grid[row][col]) % MOD
	}

	// Convert back to 2D matrix
	answer := make([][]int, n)

	for i := 0; i < n; i++ {
		answer[i] = make([]int, m)

		for j := 0; j < m; j++ {
			answer[i][j] = result[i*m+j]
		}
	}

	return answer
}

The Go implementation follows the exact same logic as the Python solution.

One important difference is explicit slice allocation. Go requires preallocating the result matrix row by row.

Another consideration is integer overflow. Since we apply modulo 12345 after every multiplication, intermediate values remain small enough for standard integer arithmetic.

Go slices are used instead of arrays because matrix dimensions are dynamic.

Worked Examples

Example 1

Input:

grid = [[1,2],
        [3,4]]

Flattened order:

[1, 2, 3, 4]

Prefix Pass

Index Value Stored Prefix New Prefix
0 1 1 1
1 2 1 2
2 3 2 6
3 4 6 24

Result array after prefix pass:

[1, 1, 2, 6]

Suffix Pass

Initial suffix:

1
Index Value Result Before Suffix Final Value New Suffix
3 4 6 1 6 4
2 3 2 4 8 12
1 2 1 12 12 24
0 1 1 24 24 24

Final flat result:

[24, 12, 8, 6]

Converted back to matrix:

[[24,12],
 [8,6]]

Example 2

Input:

grid = [[12345],
        [2],
        [1]]

Flattened order:

[12345, 2, 1]

Since:

12345 % 12345 = 0

many products become zero modulo 12345.

Prefix Pass

Index Value Stored Prefix New Prefix
0 12345 1 0
1 2 0 0
2 1 0 0

Prefix result:

[1,0,0]

Suffix Pass

Index Value Result Before Suffix Final Value
2 1 0 1 0
1 2 0 1 0
0 12345 1 2 2

Final matrix:

[[2],
 [0],
 [0]]

Complexity Analysis

Measure Complexity Explanation
Time O(n*m) Each element is processed twice
Space O(n*m) Output storage plus flat intermediate array

The algorithm performs one prefix traversal and one suffix traversal. Each traversal touches every element exactly once.

No nested iteration over the entire matrix occurs, so the complexity is linear in the number of elements.

The auxiliary space comes primarily from storing the flattened result array. The returned matrix itself is required output space.

Test Cases

from typing import List

class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        MOD = 12345
        
        n = len(grid)
        m = len(grid[0])
        size = n * m
        
        result = [1] * size
        
        prefix = 1
        
        for idx in range(size):
            row = idx // m
            col = idx % m
            
            result[idx] = prefix
            prefix = (prefix * grid[row][col]) % MOD
        
        suffix = 1
        
        for idx in range(size - 1, -1, -1):
            row = idx // m
            col = idx % m
            
            result[idx] = (result[idx] * suffix) % MOD
            suffix = (suffix * grid[row][col]) % MOD
        
        answer = []
        
        for i in range(n):
            answer.append(result[i * m:(i + 1) * m])
        
        return answer

sol = Solution()

# Example 1
assert sol.constructProductMatrix([[1, 2], [3, 4]]) == [
    [24, 12],
    [8, 6]
]  # basic 2x2 matrix

# Example 2
assert sol.constructProductMatrix([[12345], [2], [1]]) == [
    [2],
    [0],
    [0]
]  # modulus causes zeros

# Single row matrix
assert sol.constructProductMatrix([[2, 3, 4]]) == [
    [12, 8, 6]
]  # one-dimensional row case

# Single column matrix
assert sol.constructProductMatrix([[2], [3], [4]]) == [
    [12],
    [8],
    [6]
]  # one-dimensional column case

# All ones
assert sol.constructProductMatrix([[1, 1], [1, 1]]) == [
    [1, 1],
    [1, 1]
]  # identity multiplication

# Large values
assert sol.constructProductMatrix([[1000000000, 1000000000]]) == [
    [10000, 10000]
]  # large integer handling

# Contains value divisible by MOD
assert sol.constructProductMatrix([[12345, 5]]) == [
    [5, 0]
]  # modulo zero propagation

# Minimum valid size
assert sol.constructProductMatrix([[7, 9]]) == [
    [9, 7]
]  # smallest allowed matrix

# Mixed dimensions
assert sol.constructProductMatrix([
    [1, 2, 3],
    [4, 5, 6]
]) == [
    [720, 360, 240],
    [180, 144, 120]
]  # rectangular matrix

print("All tests passed!")

Test Summary

Test Why
[[1,2],[3,4]] Validates standard case
[[12345],[2],[1]] Validates modulus zero behavior
Single row matrix Ensures flattening logic works
Single column matrix Ensures vertical traversal works
All ones Checks multiplicative identity
Large values Verifies modulo arithmetic correctness
Value divisible by modulus Tests zero propagation
Minimum valid size Tests smallest constraints
Rectangular matrix Confirms non-square handling

Edge Cases

Elements Divisible by 12345

If any element is divisible by 12345, then that value becomes 0 under modulo arithmetic. This can easily create many zeros in the final answers.

A division-based approach would fail here because modular inverses may not exist. The prefix-suffix approach avoids division entirely, so it handles these cases naturally and correctly.

Single Row or Single Column Matrices

A matrix may effectively behave like a one-dimensional array:

[[1,2,3,4]]

or

[[1],[2],[3],[4]]

Incorrect index mapping could easily produce wrong results when converting between flattened and 2D coordinates.

The implementation consistently uses:

row = idx // m
col = idx % m

which works correctly regardless of matrix shape.

Very Large Numbers

Grid values can be as large as 10^9, and multiplying many such values together would create astronomically large integers.

The implementation applies modulo 12345 after every multiplication step. This keeps intermediate values bounded and efficient while preserving correctness under modular arithmetic.