Start by placing 2s in both rows where the column sum is 2, then fill 1s in the upper row until its limit is reached. The remaining 1s go to the lower row, ensuring the sum invariants are satisfied. This approach guarantees a valid reconstruction or identifies impossibility quickly.
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.
How GhostInterview Helps
- Automatically applies greedy plus invariant validation to place 2s and 1s correctly in the matrix.
- Highlights columns that violate row sums, showing exactly why a solution is impossible.
- Provides a step-by-step reconstructed matrix matching upper, lower, and column sum constraints.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Reconstruct a 2-Row Binary Matrix instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Reconstruct a 2-Row Binary Matrix from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Compute the minimum number of adjacent row swaps to transform a binary grid so all upper-triangle cells are zero using a greedy approach.
Open problem page#1605 Find Valid Matrix Given Row and Column SumsGiven row and column sums, find any valid matrix of non-negative integers that satisfies them.
Open problem page#861 Score After Flipping MatrixMaximize the score of a binary matrix by flipping rows and columns using a greedy approach and validation of invariants.
Open problem page