Given the following details of a matrix with n columns and 2 rows :
0 or 1.upper.lower.colsum[i], where colsum is given as an integer array with length n.Your task is to reconstruct the matrix with upper, lower and colsum.
Return it as a 2-D integer array.
If there are more than one valid solution, any of them will be accepted.
If no valid solution exists, return an empty 2-D array.
Example 1:
Input: upper = 2, lower = 1, colsum = [1,1,1] Output: [[1,1,0],[0,0,1]] Explanation: [[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 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]]
Constraints:
1 <= colsum.length <= 10^50 <= upper, lower <= colsum.length0 <= colsum[i] <= 2In #1253 Reconstruct a 2-Row Binary Matrix, you are given two row sums (upper and lower) and a colsum array describing how many 1s must appear in each column. The goal is to reconstruct a valid 2 x n binary matrix that satisfies these constraints.
A common strategy is a greedy approach. First, handle columns where colsum[i] == 2, since both rows must contain 1 in those positions. Deduct these from both row sums immediately. Next, process columns where colsum[i] == 1. Place the 1 in the row that still has the larger remaining capacity (upper or lower). Columns with colsum[i] == 0 remain 0 in both rows.
At each step, ensure the row sums never become negative and that the final counts match the required totals. This linear pass over the columns makes the solution efficient. The approach runs in O(n) time with O(n) space for storing the resulting matrix.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy column assignment | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You cannot do anything about colsum[i] = 2 case or colsum[i] = 0 case. Then you put colsum[i] = 1 case to the upper row until upper has reached. Then put the rest into lower row.
Fill 0 and 2 first, then fill 1 in the upper row or lower row in turn but be careful about exhausting permitted 1s in each row.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Columns with colsum equal to 2 are forced placements because both rows must contain a 1 in that column. Handling them first reduces ambiguity and correctly updates the remaining row sums before assigning flexible columns.
Problems similar to this appear in technical interviews because they test greedy reasoning and constraint handling. While the exact question may vary, the pattern of reconstructing structures from partial sums is commonly tested.
A simple 2D array or two lists representing the two rows is sufficient. The algorithm mainly relies on iterating through the colsum array and updating row capacities, so no complex data structures are required.
The optimal approach uses a greedy strategy. First fill columns where colsum equals 2, then distribute columns with colsum equals 1 between the two rows based on the remaining row sums. This ensures constraints are satisfied while scanning the array only once.