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.

#2906

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

构造乘积矩阵

给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p 。如果满足以下条件，则称 p 为 grid 的乘积矩阵：对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12…

数组矩阵前缀和

题目描述

给你一个下标从 0 开始、大小为 n * m 的二维整数矩阵 grid ，定义一个下标从 0 开始、大小为 n * m 的的二维矩阵 p。如果满足以下条件，则称 p 为 grid 的 乘积矩阵 ：

对于每个元素 p[i][j] ，它的值等于除了 grid[i][j] 外所有元素的乘积。乘积对 12345 取余数。

返回 grid 的乘积矩阵。

示例 1：

输入：grid = [[1,2],[3,4]]
输出：[[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
所以答案是 [[24,12],[8,6]] 。

示例 2：

输入：grid = [[12345],[2],[1]]
输出：[[2],[0],[0]]
解释：p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2
p[1][0] = grid[0][0] * grid[2][0] = 12345 * 1 = 12345. 12345 % 12345 = 0 ，所以 p[1][0] = 0
p[2][0] = grid[0][0] * grid[1][0] = 12345 * 2 = 24690. 24690 % 12345 = 0 ，所以 p[2][0] = 0
所以答案是 [[2],[0],[0]] 。

提示：

1 <= n == grid.length <= 10⁵
1 <= m == grid[i].length <= 10⁵
2 <= n * m <= 10⁵
1 <= grid[i][j] <= 10⁹

lightbulb

解题思路

方法一：前后缀分解

我们可以预处理出每个元素的后缀乘积（不包含自身），然后再遍历矩阵，计算得到每个元素的前缀乘积（不包含自身），将两者相乘即可得到每个位置的结果。

具体地，我们用 $p[i][j]$ 表示矩阵中第 $i$ 行第 $j$ 列元素的结果，定义一个变量 $suf$ 表示当前位置右下方的所有元素的乘积，初始时 $suf = 1$ 。我们从矩阵右下角开始遍历，对于每个位置 $(i, j)$ ，我们将 $suf$ 赋值给 $p[i][j]$ ，然后更新 $suf$ 为 $suf \times grid[i][j] \bmod 12345$ ，这样就可以得到每个位置的后缀乘积。

接下来我们从矩阵左上角开始遍历，对于每个位置 $(i, j)$ ，我们将 $p[i][j]$ 乘上 $pre$ ，再对 $12345$ 取模，然后更新 $pre$ 为 $pre \times grid[i][j] \bmod 12345$ ，这样就可以得到每个位置的前缀乘积。

遍历结束，返回结果矩阵 $p$ 即可。

时间复杂度 $O(n \times m)$ ，其中 $n$ 和 $m$ 分别是矩阵的行数和列数。忽略结果矩阵的空间占用，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#3070 元素和小于等于 k 的子矩阵的数目 #3212 统计 X 和 Y 频数相等的子矩阵数量 #3225 网格图操作后的最大分数