Reconstruct a 2-Row Binary Matrix

Reconstruct a 2-Row Binary Matrix

What is this problem about?

The Reconstruct a 2-Row Binary Matrix problem gives you upper and lower row sums and a list of column sums. Find a 2×n binary matrix where row 1 has upper ones, row 2 has lower ones, and column j has colsum[j] ones. This coding problem uses greedy assignment based on column sum values. The array, matrix, and greedy interview pattern is demonstrated.

Why is this asked in interviews?

American Express and Grab ask this to test greedy construction: columns with colsum=2 must have both rows = 1; columns with colsum=1 get one 1 (assigned greedily to whichever row still needs more ones). If constraints conflict, return empty.

Algorithmic pattern used

Greedy column-wise assignment. First, assign 1s to both rows for all columns with colsum=2 (mandatory). Check if upper/lower have sufficient remaining capacity. For columns with colsum=1: if upper > 0, assign to row 1; else assign to row 2. After processing, verify all row sums are exactly 0 (all ones assigned).

Example explanation

upper=2, lower=1, colsum=[1,1,1].

• colsum=2: none. upper=2,lower=1 unchanged.
• colsum=1: 3 columns. Assign: col0→row1(upper=1,lower=1), col1→row1(upper=0,lower=1), col2→row2(upper=0,lower=0). Result: [[1,1,0],[0,0,1]]. Row sums: 2 and 1 ✓. Valid.

Common mistakes candidates make

• Not processing colsum=2 columns first.
• Not checking remaining row sums after assignment.
• Assigning both 1s to the same row for colsum=2.
• Not returning empty when remaining upper+lower ≠ remaining colsum=1 count.

Interview preparation tip

Binary matrix construction problems are solved greedily by processing most-constrained columns first. Colsum=2 forces both rows to 1; colsum=1 gives flexibility. After mandatory assignments, distribute the flexible ones to whichever row needs more. Validate at the end. Practice similar "fill matrix under row/column sum constraints" problems.