Problem Description

You need to reconstruct a 2×n binary matrix based on given constraints about its row sums and column sums.

You're given:

• upper: the sum of all elements in the first (upper) row
• lower: the sum of all elements in the second (lower) row
• colsum: an array of length n where colsum[i] represents the sum of elements in column i

The matrix you construct must be binary (containing only 0s and 1s) and must satisfy all three constraints:

• The sum of the first row equals upper
• The sum of the second row equals lower
• For each column i, the sum of its two elements equals colsum[i]

Since each column has only 2 elements and the matrix is binary, colsum[i] can only be 0, 1, or 2:

• If colsum[i] = 0, both elements in column i must be 0
• If colsum[i] = 1, exactly one element in column i must be 1
• If colsum[i] = 2, both elements in column i must be 1

Return any valid 2×n matrix that satisfies all constraints. If no valid solution exists, return an empty 2-D array.

For example, if upper = 2, lower = 1, and colsum = [1, 1, 1], one valid answer would be [[1, 1, 0], [0, 0, 1]] because the first row sums to 2, the second row sums to 1, and each column sums to 1.

Intuition

The key insight is that we can build the matrix column by column, making greedy decisions based on the column sum constraints.

For each column, we know exactly how many 1s it needs based on colsum[i]. The question is just where to place them:

• When colsum[i] = 2, we have no choice - both rows must have a 1 in this column. This uses up one 1 from both upper and lower counts.

• When colsum[i] = 0, we have no choice either - both rows must have a 0 in this column.

• When colsum[i] = 1, we have flexibility - we can place the 1 in either row. This is where the greedy strategy comes in.

The greedy choice for colsum[i] = 1 is to place the 1 in whichever row still needs more 1s. If upper > lower, we place it in the upper row; otherwise, in the lower row. This helps balance out the remaining 1s we need to place.

Why does this greedy approach work? Because we're not creating any future constraints that could make the problem unsolvable. Each column is independent - as long as we have enough 1s left to distribute (upper and lower don't go negative), and we end up using exactly the right number of 1s for each row (both upper and lower reach 0), we'll have a valid solution.

The algorithm fails and returns an empty array in two cases:

1. During construction, if upper or lower becomes negative (we've placed too many 1s in that row)
2. After construction, if upper or lower is not exactly 0 (we haven't placed enough 1s in that row)

Learn more about Greedy patterns.

Solution Approach

We implement a greedy algorithm that constructs the matrix column by column:

1. Initialize the answer matrix: Create a 2×n matrix ans filled with zeros. This will store our result with ans[0] representing the upper row and ans[1] representing the lower row.

2. Process each column: Iterate through the colsum array. For each column j with sum value v:

   • Case 1: v = 2: Both cells in this column must be 1.

     ans[0][j] = ans[1][j] = 1
     upper, lower = upper - 1, lower - 1

     We set both rows to 1 and decrement both upper and lower counters.

   • Case 2: v = 1: Exactly one cell in this column must be 1.

     if upper > lower:
         upper -= 1
         ans[0][j] = 1
     else:
         lower -= 1
         ans[1][j] = 1

     We use a greedy strategy: place the 1 in whichever row needs more 1s. If upper > lower, place it in the upper row; otherwise, place it in the lower row.

   • Case 3: v = 0: Both cells remain 0 (already initialized), so no action needed.

3. Validity check during construction: After processing each column, check if upper < 0 or lower < 0. If either becomes negative, it means we've placed more 1s in that row than allowed, so return an empty array immediately.

4. Final validation: After processing all columns, verify that both upper and lower equal exactly 0. This ensures we've placed exactly the right number of 1s in each row. If both are 0, return ans; otherwise, return an empty array.

The time complexity is O(n) where n is the number of columns, as we process each column once. The space complexity is O(n) for storing the answer matrix (not counting the output space).

Example Walkthrough

Let's walk through an example with upper = 3, lower = 2, and colsum = [2, 1, 1, 0, 1].

We need to construct a 2×5 binary matrix where:

• The upper row sums to 3
• The lower row sums to 2
• Each column i sums to colsum[i]

Step 1: Initialize

• Create a 2×5 matrix filled with zeros: [[0,0,0,0,0], [0,0,0,0,0]]
• Track remaining 1s needed: upper = 3, lower = 2

Step 2: Process column 0 (colsum[0] = 2)

• Both cells must be 1
• Set ans[0][0] = 1 and ans[1][0] = 1
• Update counters: upper = 2, lower = 1
• Matrix: [[1,0,0,0,0], [1,0,0,0,0]]

Step 3: Process column 1 (colsum[1] = 1)

• Exactly one cell must be 1
• Compare: upper = 2 > lower = 1, so place 1 in upper row
• Set ans[0][1] = 1
• Update: upper = 1
• Matrix: [[1,1,0,0,0], [1,0,0,0,0]]

Step 4: Process column 2 (colsum[2] = 1)

• Exactly one cell must be 1
• Compare: upper = 1 = lower = 1, so place 1 in lower row (tie broken by else condition)
• Set ans[1][2] = 1
• Update: lower = 0
• Matrix: [[1,1,0,0,0], [1,0,1,0,0]]

Step 5: Process column 3 (colsum[3] = 0)

• Both cells remain 0 (no change needed)
• Matrix: [[1,1,0,0,0], [1,0,1,0,0]]

Step 6: Process column 4 (colsum[4] = 1)

• Exactly one cell must be 1
• Compare: upper = 1 > lower = 0, so place 1 in upper row
• Set ans[0][4] = 1
• Update: upper = 0
• Matrix: [[1,1,0,0,1], [1,0,1,0,0]]

Step 7: Final validation

• Check: upper = 0 ✓ and lower = 0 ✓
• Both are exactly 0, so we have a valid solution

Result: [[1,1,0,0,1], [1,0,1,0,0]]

Let's verify:

• Upper row sum: 1+1+0+0+1 = 3 ✓
• Lower row sum: 1+0+1+0+0 = 2 ✓
• Column sums: [2,1,1,0,1] ✓

The greedy strategy successfully distributed the 1s to satisfy all constraints!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array colsum. The algorithm iterates through the colsum array exactly once using a single for loop with enumerate(). Inside the loop, all operations (comparisons, assignments, and arithmetic operations) are performed in constant time O(1). Therefore, the overall time complexity is O(n).

Space Complexity: O(1) (excluding the output array). The algorithm uses only a constant amount of extra space for variables like n, j, and v. The answer array ans of size 2 × n is required for the output and is not counted towards the space complexity as per the reference. If we were to include the output array, the space complexity would be O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Greedy Strategy for Column Sum = 1

The Pitfall: When colsum[i] = 1, the code uses a greedy approach that places the 1 in whichever row has more remaining sum (upper_remaining > lower_remaining). However, this strategy can fail in certain cases where it makes locally optimal choices that prevent a globally valid solution.

Example of Failure:

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

Following the current greedy approach:

• Column 0 (sum=2): Both rows get 1, upper_remaining=3, lower_remaining=1
• Column 1 (sum=1): Since 3 > 1, upper row gets 1, upper_remaining=2, lower_remaining=1
• Column 2 (sum=1): Since 2 > 1, upper row gets 1, upper_remaining=1, lower_remaining=1
• Column 3 (sum=1): Since 1 == 1, lower row gets 1, upper_remaining=1, lower_remaining=0
• Column 4 (sum=1): Since 1 > 0, upper row gets 1, upper_remaining=0, lower_remaining=0

Result: [[1,1,1,0,1], [1,0,0,1,0]] - This works, but only by chance.

Better Example Showing the Issue: Consider if we need to place 1s more strategically based on future columns with sum=2.

2. Not Pre-validating Total Sum Constraints

The Pitfall: The code doesn't check upfront if the problem is solvable. It discovers invalidity during construction, which is inefficient.

The Problem: Before starting construction, we should verify:

• The sum of all colsum values equals upper + lower
• We have enough columns with sum=2 and sum=1 to satisfy both row constraints

Solution - Improved Code:

class Solution:
    def reconstructMatrix(
        self, upper: int, lower: int, colsum: List[int]
    ) -> List[List[int]]:
        n = len(colsum)
      
        # Pre-validation: Check if total sum matches
        total_sum = sum(colsum)
        if total_sum != upper + lower:
            return []
      
        # Count columns by their sum values
        count_2 = sum(1 for x in colsum if x == 2)
        count_1 = sum(1 for x in colsum if x == 1)
      
        # Check if it's possible to distribute 1s
        # Columns with sum=2 contribute 1 to both rows
        # After placing these, we need to distribute remaining 1s
        upper_needed = upper - count_2
        lower_needed = lower - count_2
      
        # Check if we have negative needs or insufficient columns with sum=1
        if upper_needed < 0 or lower_needed < 0:
            return []
        if upper_needed + lower_needed != count_1:
            return []
      
        # Now construct the matrix
        matrix = [[0] * n for _ in range(2)]
        upper_remaining = upper_needed  # 1s still needed for upper row (excluding sum=2 columns)
      
        for col_idx, col_sum in enumerate(colsum):
            if col_sum == 2:
                matrix[0][col_idx] = 1
                matrix[1][col_idx] = 1
            elif col_sum == 1:
                # Place 1 in upper row if we still need 1s there
                if upper_remaining > 0:
                    matrix[0][col_idx] = 1
                    upper_remaining -= 1
                else:
                    matrix[1][col_idx] = 1
      
        return matrix

Key Improvements:

1. Pre-validation: Checks total sum constraint and feasibility before construction
2. Simplified greedy logic: Instead of comparing remaining sums, we simply fill the upper row first until it reaches its quota, then fill the lower row
3. Early termination: Returns empty array immediately if constraints can't be satisfied
4. More predictable behavior: The solution is deterministic and easier to reason about