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] <= 2Problem Overview: You receive three inputs: upper, lower, and an array colsum. The goal is to construct a 2 x n binary matrix where the first row sums to upper, the second row sums to lower, and each column sum matches colsum[i]. If no valid matrix exists, return an empty result.
Approach 1: Greedy Construction (O(n) time, O(n) space)
This problem works well with a greedy strategy because some column sums force a unique decision. If colsum[i] == 2, both rows must contain 1 at that column. If colsum[i] == 0, both rows must contain 0. The only flexible case is when colsum[i] == 1, where you choose which row receives the 1. Start by iterating through the array and assigning all forced columns (2) first, decrementing upper and lower. Then process columns with sum 1, placing the 1 in whichever row still has remaining quota. If either quota becomes negative or non‑zero after processing all columns, the matrix is impossible to construct.
This method relies on simple iteration over the array and constant‑time assignments. The greedy decision works because forced columns reduce the remaining capacity deterministically, leaving only balanced placement for colsum == 1. The algorithm runs in O(n) time with O(n) space for the result matrix. Problems like this often appear in interview sets related to greedy algorithms and constrained distribution using arrays.
Approach 2: Sorting-Based Allocation (O(n log n) time, O(n) space)
An alternative idea is to process columns in priority order. Create pairs of (colsum, index) and sort them in descending order so that columns requiring stronger constraints are handled first. Columns with value 2 are filled in both rows, while columns with value 1 are assigned based on which row still has remaining capacity. Sorting guarantees that the most restrictive columns are processed before flexible ones, which simplifies reasoning about feasibility.
After sorting, iterate through the ordered columns and update the matrix accordingly while tracking remaining values of upper and lower. If at any step neither row can accept a required value, the configuration is invalid. While the logic remains similar to the greedy approach, sorting adds an O(n log n) overhead. This approach can feel more intuitive when you think in terms of prioritizing constraints rather than scanning sequentially. The matrix construction itself still uses simple operations typical in matrix manipulation problems.
Recommended for interviews: The greedy construction is the expected solution. Interviewers look for recognition that columns with sum 2 and 0 are forced decisions, which simplifies the rest of the allocation. Explaining this reasoning clearly shows strong problem‑solving skills. The sorting approach works but adds unnecessary complexity compared to the linear greedy pass.
This problem can be effectively tackled with a greedy approach. The primary objective is to iterate through the colsum array and appropriately fill the values in two subarrays that represent the upper and lower rows of the matrix.
Here's the strategy:
The solution initiates two arrays to represent the two rows of the matrix. It first fills in columns where colsum[i] = 2 since these are mandatory 1s on both rows, decrementing both 'upper' and 'lower'. For columns where colsum[i] = 1, it attempts to fill the upper row first if possible, otherwise, the lower row. If at the end of processing, 'upper' or 'lower' still has remaining capacity, the solution returns NULL.
Time complexity: O(n), where n is the length of the colsum array, as the loop runs through the elements of the array.
Space complexity: O(n) due to the storage of the result array.
An alternative method involves treating each column sum specifically and sorting columns by their necessity. Sort colsum indices directly by values, and cater sums of 2 first, then sums of 1. This ensures sum handling in priority order.
Steps involved:
This Python solution increases potential efficiency during fill by sorting columns in descending order of necessity, handling the sums of 2 first. Its strategy allows earlier decisive fills in a given priority order, then addresses available 1s afterwards.
Python
JavaScript
Time complexity: O(n log n), for sorting indexes by colsum values and O(n) for fill operations.
Space complexity: O(n) for upper and lower row space.
First, we create an answer array ans, where ans[0] and ans[1] represent the first and second rows of the matrix, respectively.
Next, we traverse the array colsum from left to right. For the current element colsum[j], we have the following cases:
colsum[j] = 2, then we set both ans[0][j] and ans[1][j] to 1. In this case, both upper and lower are reduced by 1.colsum[j] = 1, then we set either ans[0][j] or ans[1][j] to 1. If upper \gt lower, then we prefer to set ans[0][j] to 1; otherwise, we prefer to set ans[1][j] to 1. In this case, either upper or lower is reduced by 1.colsum[j] = 0, then we set both ans[0][j] and ans[1][j] to 0.upper \lt 0 or lower \lt 0, then it is impossible to construct a matrix that meets the requirements, and we return an empty array.At the end of the traversal, if both upper and lower are 0, then we return ans; otherwise, we return an empty array.
The time complexity is O(n), where n is the length of the array colsum. Ignoring the space consumption of the answer array, the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time complexity: O(n), where n is the length of the colsum array, as the loop runs through the elements of the array. Space complexity: O(n) due to the storage of the result array. |
| Alternative Sorting Approach | Time complexity: O(n log n), for sorting indexes by colsum values and O(n) for fill operations. Space complexity: O(n) for upper and lower row space. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Construction | O(n) | O(n) | Best general solution; single pass assignment based on column constraints |
| Sorting-Based Allocation | O(n log n) | O(n) | When prioritizing strict constraints first or experimenting with ordered processing |
Reconstruct a 2-Row Binary Matrix(Leetcode 1253) • Coding Interviews • 615 views views
Watch 6 more video solutions →Practice Reconstruct a 2-Row Binary Matrix with our built-in code editor and test cases.
Practice on FleetCode