How do you solve Construct Product Matrix on LeetCode?

Construct Product Matrix (LeetCode #2906) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n * m) time complexity and O(n * m) space complexity. Key insight: Using prefix and suffix products allows us to avoid repeated multiplication, significantly improving efficiency.

What is the brute force solution for Construct Product Matrix?

The brute force approach for Construct Product Matrix is Brute Force, with O(n² * m²) time complexity and O(1) space complexity. In the brute force approach, we calculate the product for each element by multiplying all other elements in the matrix. This is straightforward but inefficient, especially for larger matrices. The optimal Optimal Solution approach improves this to O(n * m).

What algorithm or data structure is used to solve Construct Product Matrix?

Construct Product Matrix uses the following concepts: Array, Matrix, Prefix Sum. The recommended patterns to study are: Prefix Sum, Suffix Array.

What are the interview tips for Construct Product Matrix?

Clearly explain your thought process and approach before jumping into coding. Consider edge cases and constraints while discussing your solution. Practice explaining your code and reasoning as if you are teaching someone else.

What are common mistakes when solving Construct Product Matrix?

Forgetting to apply modulo during multiplication can lead to incorrect results. Not handling edge cases, such as single-row or single-column matrices.

#2906

Construct Product Matrix

Medium

ArrayMatrixPrefix SumPrefix SumSuffix Array

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n² * m²)	O(n * m)
Space	O(1)	O(n * m)

💡

Intuition

Time O(n * m)Space O(n * m)

In the optimal approach, we use prefix and suffix products to efficiently compute the product for each element without redundant calculations. This reduces the time complexity significantly.

⚙️

Algorithm

5 steps

1Step 1: Create two 2D arrays, prefix and suffix, to store products of elements before and after each position.
2Step 2: Fill the prefix array where prefix[i][j] is the product of all elements in the row up to column j (excluding grid[i][j]).
3Step 3: Fill the suffix array where suffix[i][j] is the product of all elements in the row after column j (excluding grid[i][j]).
4Step 4: For each element p[i][j], calculate it as (prefix[i][j] * suffix[i][j]) % 12345.
5Step 5: Return the result matrix.

solution.py21 lines

1# Full working Python code
2
3def construct_product_matrix(grid):
4    n, m = len(grid), len(grid[0])
5    result = [[0] * m for _ in range(n)]
6    prefix = [[1] * m for _ in range(n)]
7    suffix = [[1] * m for _ in range(n)]
8
9    for i in range(n):
10        for j in range(1, m):
11            prefix[i][j] = (prefix[i][j - 1] * grid[i][j - 1]) % 12345
12
13    for i in range(n):
14        for j in range(m - 2, -1, -1):
15            suffix[i][j] = (suffix[i][j + 1] * grid[i][j + 1]) % 12345
16
17    for i in range(n):
18        for j in range(m):
19            result[i][j] = (prefix[i][j] * suffix[i][j]) % 12345
20
21    return result

ℹ

Complexity note: This complexity arises because we traverse the matrix a few times (once for prefix, once for suffix, and once for the result), leading to linear time complexity relative to the number of elements.

1Using prefix and suffix products allows us to avoid repeated multiplication, significantly improving efficiency.
2Modulo operations help manage large numbers and prevent overflow.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.