Reconstruct a 2-Row Binary Matrix - Video Solutions

Problem 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.