What is the best strategy for reconstructing a 2-row binary matrix?

Use greedy placement for columns with colsum[i] = 1 and immediately assign 2s to both rows, validating upper and lower counters.

Why is invariant validation crucial in this problem?

It ensures that forced assignments like colsum[i] = 2 do not violate row sums and the final matrix is feasible.

Can multiple solutions exist for the same upper, lower, and colsum?

Yes, different valid placements of 1s in columns with colsum[i] = 1 can produce multiple correct matrices.

What should be returned if no valid matrix exists?

Return an empty array to indicate reconstruction is impossible under the given constraints.

How does the greedy choice plus invariant pattern apply here?

It drives the placement of 2s and 1s efficiently while continuously checking that row sums remain achievable.

#1253

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

重构 2 行二进制矩阵

给你一个 2 行 n 列的二进制数组：矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是 0 就是 1 。第 0 行的元素之和为 upper 。第 1 行的元素之和为 lower 。第 i 列（从 0 开始编号）的元素之和为 colsum[i] ， colsum 是一个长度为 n 的整数数组…

数组贪心矩阵

题目描述

给你一个 2 行 n 列的二进制数组：

矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是 0 就是 1。
第 0 行的元素之和为 upper。
第 1 行的元素之和为 lower。
第 i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。

你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。

如果有多个不同的答案，那么任意一个都可以通过本题。

如果不存在符合要求的答案，就请返回一个空的二维数组。

示例 1：

输入：upper = 2, lower = 1, colsum = [1,1,1]
输出：[[1,1,0],[0,0,1]]
解释：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。

示例 2：

输入：upper = 2, lower = 3, colsum = [2,2,1,1]
输出：[]

示例 3：

输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
输出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

提示：

1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

lightbulb

解题思路

方法一：贪心

我们先创建一个答案数组 $ans$ ，其中 $ans[0]$ 和 $ans[1]$ 分别表示矩阵的第一行和第二行。

接下来，从左到右遍历数组 $colsum$ ，对于当前遍历到的元素 $colsum[j]$ ，我们有以下几种情况：

如果 $colsum[j] = 2$ ，那么我们将 $ans[0][j]$ 和 $ans[1][j]$ 都置为 $1$ 。此时 $upper$ 和 $lower$ 都减去 $1$ 。
如果 $colsum[j] = 1$ ，那么我们将 $ans[0][j]$ 或 $ans[1][j]$ 置为 $1$ 。如果 $upper \gt lower$ ，那么我们优先将 $ans[0][j]$ 置为 $1$ ，否则我们优先将 $ans[1][j]$ 置为 $1$ 。此时 $upper$ 或 $lower$ 减去 $1$ 。
如果 $colsum[j] = 0$ ，那么我们将 $ans[0][j]$ 和 $ans[1][j]$ 都置为 $0$ 。
如果 $upper \lt 0$ 或 $lower \lt 0$ ，那么说明无法构造出满足要求的矩阵，我们返回一个空数组。

遍历结束，如果 $upper$ 和 $lower$ 都为 $0$ ，那么我们返回 $ans$ ，否则我们返回一个空数组。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $colsum$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def reconstructMatrix(
        self, upper: int, lower: int, colsum: List[int]
    ) -> List[List[int]]:
        n = len(colsum)
        ans = [[0] * n for _ in range(2)]
        for j, v in enumerate(colsum):
            if v == 2:
                ans[0][j] = ans[1][j] = 1
                upper, lower = upper - 1, lower - 1
            if v == 1:
                if upper > lower:
                    upper -= 1
                    ans[0][j] = 1
                else:
                    lower -= 1
                    ans[1][j] = 1
            if upper < 0 or lower < 0:
                return []
        return ans if lower == upper == 0 else []

speed

复杂度分析

指标	值
时间	complexity is O(n) since each column is processed once. Space complexity is O(n) for storing the reconstructed matrix with two rows.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
How do you handle columns with colsum[i] = 2 without violating upper or lower limits?
question_mark
Can you ensure greedy placement of 1s maintains the total row sums?
question_mark
What validation step confirms a reconstructed matrix is actually feasible?

warning

常见陷阱

外企场景

error
Placing 1s without tracking upper or lower counters can exceed row sums.
error
Failing to handle colsum[i] = 2 as forced assignment leads to incorrect matrices.
error
Returning a matrix without verifying that upper and lower sums reach zero can give invalid solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing more than 2 rows requires adjusting greedy assignment per row while maintaining column sums.
arrow_right_alt
If negative numbers appear in colsum, the approach must include feasibility checks for invalid inputs.
arrow_right_alt
Reconstructing in-place without extra memory shifts the complexity focus to careful counter updates.

help

常见问题

外企场景

继续练习

#1536 排布二进制网格的最少交换次数 #1605 给定行和列的和求可行矩阵 #861 翻转矩阵后的得分