#1253

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Reconstruct a 2-Row Binary Matrix

Reconstruct a 2-row binary matrix by distributing column sums while respecting upper and lower row limits using greedy placement.

array greedy matrix

Problem Statement

You are given an integer upper, an integer lower, and an array colsum representing the sum of each column in a 2-row binary matrix with n columns. Reconstruct a binary matrix that matches these row sums and column sums, or return an empty array if impossible.

Each element of the matrix must be 0 or 1, with each column sum matching colsum[i], the sum of the top and bottom element in that column. The total of the top row must equal upper, and the bottom row must equal lower. Return any valid solution as a 2-D array.

Examples

Example 1

Input: upper = 2, lower = 1, colsum = [1,1,1]

Output: [[1,1,0],[0,0,1]]

[[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2

Input: upper = 2, lower = 3, colsum = [2,2,1,1]

Output: []

Example details omitted.

Example 3

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]

Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Example details omitted.

Constraints

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

Solution Approach

Handle Forced 2s

For columns where colsum[i] equals 2, both rows must have a 1. Deduct these from upper and lower counters immediately. This step is unavoidable and ensures the invariant that each 2 is split across both rows.

Greedy Placement of 1s

Iterate through columns where colsum[i] is 1. Place a 1 in the upper row if upper > 0, otherwise in the lower row. Update upper and lower counters accordingly. This greedy choice fills rows without violating row sum constraints.

Validation and Return

After placement, check that upper and lower counters are both zero. If so, the constructed matrix is valid. Otherwise, return an empty array to indicate no solution exists. This ensures the final solution respects all invariants.

Complexity Analysis

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

Time complexity is O(n) since each column is processed once. Space complexity is O(n) for storing the reconstructed matrix with two rows.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Greedy

First, we create an answer array $ans$, where $ans[0]$ and $ans[1]$ represent the first and second rows of the matrix, respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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 []

Continue Practicing

#1536 minimum swaps to arrange a binary grid #1605 find valid matrix given row and column sums #861 score after flipping matrix