We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reconstruct a 2-Row Binary Matrix

Number: 1379

Difficulty: Medium

Paid? No

Companies: American Express, Grab

Problem Description

Given a 2-row binary matrix with n columns, reconstruct the matrix given the row sums (upper and lower) and an array colsum where colsum[i] is the sum of the two entries in the i-th column. Each column’s sum can be 0, 1, or 2. A column with a sum of 2 forces both rows to have a 1 at that column. For columns with a sum of 1, assign the single 1 to an appropriate row based on the remaining required row sum. If no valid assignment exists, return an empty matrix.

Key Insights

  • Columns with colsum = 2 must have both rows set to 1, which decreases both the upper and lower remaining sums.
  • Columns with colsum = 0 are trivially assigned as 0 in both rows.
  • For columns with colsum = 1, a greedy approach is used: assign the 1 to the upper row if it still needs ones; otherwise, use the lower row.
  • After processing all columns, both upper and lower needs should exactly meet 0. Any mismatch indicates an invalid configuration.

Space and Time Complexity

Time Complexity: O(n) – iterate through the colsum array once (or twice in case of two passes). Space Complexity: O(n) – storing the final result matrix with 2 rows and n columns.

Solution

The solution follows a two-pass strategy. In the first pass, process all columns with colsum = 2 by setting both rows to 1 (and updating the upper and lower counts accordingly). In the second pass, process columns with colsum = 1: assign the 1 to the upper row if possible; otherwise, assign it to the lower row. If at any step the remaining upper or lower counts become negative, or if after all assignments the counts do not exactly drop to 0, the reconstruction is impossible and an empty array is returned.

Code Solutions

# Python solution with detailed comments

def reconstructMatrix(upper, lower, colsum):
    n = len(colsum)
    # Initialize the matrix rows with zeros
    upper_row = [0] * n
    lower_row = [0] * n

    # First pass: Assign columns where colsum is 2
    for i in range(n):
        if colsum[i] == 2:
            upper_row[i] = 1  # Must assign a 1 to the upper row
            lower_row[i] = 1  # Must assign a 1 to the lower row
            upper -= 1        # Decrement remaining upper sum
            lower -= 1        # Decrement remaining lower sum

    # If at any point the remaining upper or lower is negative, it's invalid.
    if upper < 0 or lower < 0:
        return []

    # Second pass: Process columns with colsum 1
    for i in range(n):
        if colsum[i] == 1:
            # Greedily assign 1 to upper if possible
            if upper > 0:
                upper_row[i] = 1
                upper -= 1
            else:
                lower_row[i] = 1
                lower -= 1

    # If after assignment the remaining upper or lower is non-zero, return empty
    if upper != 0 or lower != 0:
        return []
    
    return [upper_row, lower_row]

# Example usage:
#print(reconstructMatrix(2, 1, [1,1,1]))
← Back to All Questions