#2906

Medium

LeetCode Problem Workspace

Construct Product Matrix

Solve the "Construct Product Matrix" problem by calculating the product of elements in 2D matrices without division.

Problem Statement

Given a 0-indexed 2D integer matrix grid of size n * m, the task is to construct a 0-indexed 2D matrix p of size n * m where each element p[i][j] is the product of all elements in grid[i] excluding grid[i][j] and all elements in grid[j] excluding grid[j][i].

You need to return the resulting matrix p. You cannot use the division operation while solving this problem, which adds complexity in handling large matrices efficiently.

Examples

Example 1

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

Output: [[24,12],[8,6]]

p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24 p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12 p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8 p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6 So the answer is [[24,12],[8,6]].

Example 2

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

Output: [[2],[0],[0]]

p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2. p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0. So p[0][1] = 0. p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0. So p[0][2] = 0. So the answer is [[2],[0],[0]].

Constraints

1 <= n == grid.length <= 105
1 <= m == grid[i].length <= 105
2 <= n * m <= 105
1 <= grid[i][j] <= 109

Solution Approach

Matrix Row and Column Product Calculation

To construct the product matrix, iterate over rows and columns. For each element p[i][j], calculate the product of all elements in row i excluding column j, and the product of all elements in column j excluding row i. Efficient handling of these operations is key, especially for larger matrices.

Prefix Product Arrays

Using prefix product arrays can optimize the solution by storing cumulative products for each row and column. This way, you can quickly compute the product of all elements except for the current one by dividing the row's and column's total products by the current element.

Avoiding Division by Calculating Prefix and Suffix Products

Instead of using division, calculate the product of all elements to the left and right of each element in the row, as well as the product of all elements above and below it in the column. This ensures that you are not dividing by zero and avoids the use of the division operator.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used. Using prefix and suffix products can make the algorithm more efficient by reducing redundant calculations. With this approach, the time complexity is O(n * m) and the space complexity is also O(n * m). Without prefix/suffix arrays, the time complexity may be higher, especially when recalculating products repeatedly.

What Interviewers Usually Probe

Can the candidate handle large matrix sizes efficiently?
How well does the candidate optimize the computation by avoiding divisions?
Does the candidate correctly handle edge cases such as very large integers or small matrices?

Common Pitfalls or Variants

Common pitfalls

Failure to avoid division can lead to incorrect answers, especially when working with large numbers.
Not optimizing for time complexity, especially when dealing with the upper constraint limits.
Overcomplicating the solution with unnecessary data structures instead of focusing on a direct approach.

Follow-up variants

Modifying the problem to include division (using modular arithmetic).
Handling sparse matrices where many elements are zero.
Extending to 3D matrices or matrices with more dimensions.

FAQ

What is the main challenge in the "Construct Product Matrix" problem?

The main challenge is constructing the product matrix without using the division operation, which requires optimizing the calculation of row and column products.

How can I avoid division when constructing the product matrix?

You can avoid division by using prefix and suffix products to calculate the product of all elements in the row and column except the current one.

What is the time complexity of solving the "Construct Product Matrix" problem?

The time complexity is O(n * m) with the optimal solution using prefix and suffix product arrays.

Can I handle large matrices efficiently in the "Construct Product Matrix" problem?

Yes, using optimized algorithms with prefix and suffix products will allow you to handle large matrices efficiently without recalculating products unnecessarily.

What are the edge cases to consider for the "Construct Product Matrix" problem?

Edge cases include very small matrices, large numbers, or matrices with a large number of zeroes that might require careful handling of multiplication.

terminal

Solution

Solution 1: Prefix and Suffix Decomposition

We can preprocess the suffix product (excluding itself) of each element, and then traverse the matrix to calculate the prefix product (excluding itself) of each element. The product of the two gives us the result for each position.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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 p

Continue Practicing

#3070 count submatrices with top left element and sum less than k #3212 count submatrices with equal frequency of x and y #3225 maximum score from grid operations