Reconstruct a 2-Row Binary Matrix

Problem Description

Given a binary matrix with 2 rows and n columns, reconstruct the matrix based on the provided sums for the upper and lower rows, as well as the column sums. The sum of elements in the upper row is given as upper, the sum of elements in the lower row is given as lower, and the sum of elements in each column is specified by the array colsum. Return the reconstructed matrix or an empty array if no valid solution exists.

Key Insights

• Each column can have either:
  • Both rows filled with 1 (if colsum[i] is 2),
  • Only the upper row filled (if colsum[i] is 1 and upper is available),
  • Only the lower row filled (if colsum[i] is 1 and lower is available).
• The total number of 1s in both rows should equal upper + lower.
• If the sum of colsum exceeds upper + lower, it's impossible to construct the matrix.

Space and Time Complexity

Time Complexity: O(n), where n is the length of colsum, as we iterate through the array once.
Space Complexity: O(n), for storing the resultant 2D matrix.

Solution

The solution involves iterating over the colsum array and determining how to fill each column based on the current values of upper and lower. For each column:

1. If colsum[i] equals 2, assign 1 to both rows and decrease both upper and lower by 1.
2. If colsum[i] equals 1, assign 1 to the upper row if upper is greater than 0; otherwise, assign 1 to the lower row and decrease the respective counter.
3. If after processing all columns, upper or lower is not zero, it indicates an invalid configuration.

Code Solutions