LeetCode 1253 - Reconstruct a 2-Row Binary Matrix

The problem asks us to reconstruct a binary matrix with exactly two rows and n columns given three constraints: the sum

leetcodemediumarraygreedymatrix

LeetCode Problem 1253

Difficulty: 🟡 Medium
Topics: Array, Greedy, Matrix

Solution

Problem Understanding

The problem asks us to reconstruct a binary matrix with exactly two rows and n columns given three constraints: the sum of elements in the upper row (upper), the sum of elements in the lower row (lower), and the sum of elements in each column (colsum). Each element in the matrix is either 0 or 1. The colsum[i] represents the total number of 1s in the i-th column. If colsum[i] is 2, both rows must have a 1 in that column; if it is 1, either the upper or lower row has a 1; if it is 0, both rows have 0.

The input constraints indicate that the number of columns can be very large, up to 10^5, which rules out naive approaches that try every combination. Additionally, upper and lower are bounded by the number of columns, so any reconstruction must not exceed these sums. The problem guarantees that colsum values are only 0, 1, or 2, simplifying the decision logic.

Key edge cases include scenarios where upper or lower cannot accommodate the required number of 1s, when colsum contains multiple 2s exceeding the row sums, and when colsum length is minimal (1) or maximal (10^5).

Approaches

A brute-force approach would attempt to generate all possible combinations of 0 and 1 placements for each column that satisfy colsum[i], and then check if the resulting rows sum to upper and lower. This method is correct in principle but computationally infeasible because for n columns, there are up to 2^n combinations for columns where colsum[i] == 1.

The optimal approach relies on a greedy strategy and the observation that the columns with colsum[i] == 2 are fixed: both rows must have 1 there. Columns with colsum[i] == 1 can be assigned to either the upper or lower row, prioritizing whichever row has remaining sum capacity. By iterating through the columns in order and assigning 1s greedily while decrementing upper and lower, we can efficiently reconstruct the matrix or detect that it is impossible.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Attempts all combinations of placements for columns with colsum[i] == 1
Optimal O(n) O(n) Greedily assign 1s based on colsum[i] values and remaining upper and lower sums

Algorithm Walkthrough

  1. Initialize two lists upper_row and lower_row with zeros of length n to represent the two rows.
  2. Iterate through colsum from index 0 to n-1.
  3. If colsum[i] == 2, assign 1 to both upper_row[i] and lower_row[i]. Decrement both upper and lower by 1. If either upper or lower becomes negative, return an empty matrix as it is impossible.
  4. If colsum[i] == 1, assign 1 to the row (upper or lower) that still has remaining sum capacity. Prefer the upper row first if upper > 0. Decrement the corresponding row sum. If both upper and lower are zero when a 1 is needed, return an empty matrix.
  5. If colsum[i] == 0, leave both upper_row[i] and lower_row[i] as 0.
  6. After processing all columns, if upper or lower is not zero, return an empty matrix because the row sums do not match the given constraints.
  7. Return [upper_row, lower_row].

Why it works: The invariant is that after processing each column, the remaining upper and lower counts reflect the number of 1s we still need to place. Columns with 2 must be 1 in both rows, and columns with 1 are placed greedily in a row with remaining capacity. This ensures that no constraints are violated while respecting the sum requirements.

Python Solution

from typing import List

class Solution:
    def reconstructMatrix(self, upper: int, lower: int, colsum: List[int]) -> List[List[int]]:
        n = len(colsum)
        upper_row = [0] * n
        lower_row = [0] * n
        
        for i in range(n):
            if colsum[i] == 2:
                if upper <= 0 or lower <= 0:
                    return []
                upper_row[i] = 1
                lower_row[i] = 1
                upper -= 1
                lower -= 1
            elif colsum[i] == 1:
                if upper > 0:
                    upper_row[i] = 1
                    upper -= 1
                elif lower > 0:
                    lower_row[i] = 1
                    lower -= 1
                else:
                    return []
        if upper != 0 or lower != 0:
            return []
        return [upper_row, lower_row]

In this implementation, we initialize two rows with zeros and iterate through colsum. We handle the fixed case colsum[i] == 2 first, decrementing the sums. For colsum[i] == 1, we assign 1 to whichever row can still accommodate it. If the sums mismatch at the end or a placement is impossible, we return an empty list.

Go Solution

func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
    n := len(colsum)
    upperRow := make([]int, n)
    lowerRow := make([]int, n)
    
    for i := 0; i < n; i++ {
        if colsum[i] == 2 {
            if upper <= 0 || lower <= 0 {
                return [][]int{}
            }
            upperRow[i] = 1
            lowerRow[i] = 1
            upper--
            lower--
        } else if colsum[i] == 1 {
            if upper > 0 {
                upperRow[i] = 1
                upper--
            } else if lower > 0 {
                lowerRow[i] = 1
                lower--
            } else {
                return [][]int{}
            }
        }
    }
    if upper != 0 || lower != 0 {
        return [][]int{}
    }
    return [][]int{upperRow, lowerRow}
}

In Go, we use slices to represent the rows and carefully handle nil versus empty slice returns. Logic mirrors Python, with explicit decrements and checks for feasibility.

Worked Examples

Example 1: upper = 2, lower = 1, colsum = [1,1,1]

i colsum[i] upper_row lower_row upper lower
0 1 1 0 1 1
1 1 1 0 0 1
2 1 0 1 0 0

Output: [[1,1,0],[0,0,1]]

Example 2: upper = 2, lower = 3, colsum = [2,2,1,1]

First column colsum[0] == 2 requires decrementing upper and lower by 1. After second column colsum[1] == 2, upper becomes 0, lower becomes 1. For colsum[2] == 1, upper is 0, assign 1 to lower. For colsum[3] == 1, upper is 0, lower is 0, impossible. Output: [].

Example 3: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]

Following greedy allocation based on remaining upper and lower sums produces the output matrix:

[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]].

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through colsum with constant work per column
Space O(n) Two additional rows of length n are stored

The greedy algorithm ensures we only iterate once, and the matrix output itself requires O(n) space.

Test Cases

# Provided examples
assert Solution().reconstructMatrix(2, 1, [1,1,1]) == [[1,1,0],[0,0,1]]  # multiple correct outputs possible
assert Solution().reconstructMatrix(2, 3, [2,2,1,1]) == []  # impossible
assert Solution().reconstructMatrix(5, 5, [2,1,2,0,1,0,1,2,0,1]) == [[1,1