What is the primary strategy used to solve 'Find Valid Matrix Given Row and Column Sums'?

The primary strategy is to use a greedy approach, iterating through the matrix and placing the smallest of the remaining rowSum or colSum values in each cell, updating the sums after each placement.

How do I ensure that the matrix I construct satisfies the row and column sums?

After constructing the matrix, verify that the sum of each row and column matches the corresponding values in rowSum and colSum. This acts as a final validation step.

Can there be multiple valid matrices for the problem?

Yes, there can be multiple valid matrices, as long as they satisfy the row and column sum conditions. The problem only requires finding one valid solution.

What are some common pitfalls in solving this problem?

Common mistakes include failing to update the rowSum and colSum after each matrix entry, skipping the validation step, or not handling edge cases such as zero sums correctly.

How can I optimize the solution for larger matrices?

The algorithm scales well for larger matrices, but you may optimize by using more efficient ways to select the smallest row or column sum and ensure that the matrix construction is done in minimal time.

#1605

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

给定行和列的和求可行矩阵

给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。请找到大小为 rowSum.length x colSum.length 的任…

数组贪心矩阵

题目描述

给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。

请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵，且该矩阵满足 rowSum 和 colSum 的要求。

请你返回任意一个满足题目要求的二维矩阵，题目保证存在 至少一个 可行矩阵。

示例 1：

输入：rowSum = [3,8], colSum = [4,7]
输出：[[3,0],
      [1,7]]
解释：
第 0 行：3 + 0 = 3 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求，且所有矩阵元素都是非负的。
另一个可行的矩阵为：[[1,2],
                  [3,5]]

示例 2：

输入：rowSum = [5,7,10], colSum = [8,6,8]
输出：[[0,5,0],
      [6,1,0],
      [2,0,8]]

示例 3：

输入：rowSum = [14,9], colSum = [6,9,8]
输出：[[0,9,5],
      [6,0,3]]

示例 4：

输入：rowSum = [1,0], colSum = [1]
输出：[[1],
      [0]]

示例 5：

输入：rowSum = [0], colSum = [0]
输出：[[0]]

提示：

1 <= rowSum.length, colSum.length <= 500
0 <= rowSum[i], colSum[i] <= 10⁸
sum(rowSum) == sum(colSum)

lightbulb

解题思路

方法一：贪心 + 构造

我们可以先初始化一个 $m$ 行 $n$ 列的答案矩阵 $ans$ 。

接下来，遍历矩阵的每一个位置 $(i, j)$ ，将该位置的元素设为 $x = min(rowSum[i], colSum[j])$ ，并将 $rowSum[i]$ 和 $colSum[j]$ 分别减去 $x$ 。遍历完所有的位置后，我们就可以得到一个满足题目要求的矩阵 $ans$ 。

以上策略的正确性说明如下：

根据题目的要求，我们知道 $rowSum$ 和 $colSum$ 的和是相等的，那么 $rowSum[0]$ 一定小于等于 $\sum_{j = 0}^{n - 1} colSum[j]$ 。所以，在经过 $n$ 次操作后，一定能够使得 $rowSum[0]$ 为 $0$ ，并且保证对任意 $j \in [0, n - 1]$ ，都有 $colSum[j] \geq 0$ 。

因此，我们把原问题缩小为一个 $m-1$ 行和 $n$ 列的子问题，继续进行上述的操作，直到 $rowSum$ 和 $colSum$ 中的所有元素都为 $0$ ，就可以得到一个满足题目要求的矩阵 $ans$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别为 $rowSum$ 和 $colSum$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def restoreMatrix(self, rowSum: List[int], colSum: List[int]) -> List[List[int]]:
        m, n = len(rowSum), len(colSum)
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                x = min(rowSum[i], colSum[j])
                ans[i][j] = x
                rowSum[i] -= x
                colSum[j] -= x
        return ans

speed

复杂度分析

指标	值
时间	O(N \times M)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate follows the greedy strategy and constructs the matrix step by step.
question_mark
Look for any validation steps after matrix construction to ensure the row and column sums are satisfied.
question_mark
Assess how efficiently the candidate updates the row and column sums during the matrix population process.

warning

常见陷阱

外企场景

error
Failing to update the rowSum and colSum properly after each placement.
error
Not validating the final matrix to ensure the row and column sums match the expected values.
error
Incorrectly handling edge cases such as when row or column sums are zero.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Given a larger matrix, ensure the algorithm scales well with larger inputs by optimizing the matrix traversal.
arrow_right_alt
Add constraints where some elements of the matrix must be zero, and handle such situations while maintaining the row and column sum requirements.
arrow_right_alt
Consider adding further constraints, such as ensuring the matrix contains only certain numbers or patterns, and adapt the greedy approach accordingly.

help

常见问题

外企场景

继续练习

#1536 排布二进制网格的最少交换次数 #1727 重新排列后的最大子矩阵 #1253 重构 2 行二进制矩阵