Reconstruct a 2-Row Binary Matrix

medium greedy matrix simulation

Problem

Given the sum of the upper row upper, the sum of the lower row lower, and an array colsum where colsum[i] is the sum of column i, construct any binary matrix with 2 rows and colsum.length columns that satisfies all of these. Return it as a list of two rows, or an empty list if no valid matrix exists.

Inputupper = 2, lower = 1, colsum = [1, 1, 1]

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

Row sums are 2 and 1; each column sums to 1. Greedy gives the upper row priority while it still needs more 1s.

upper

lower

colsum (comma-separated, each 0/1/2)

def reconstruct_matrix(upper, lower, colsum):
    n = len(colsum)
    top = [0] * n
    bot = [0] * n
    for i, c in enumerate(colsum):
        if c == 2:
            top[i] = bot[i] = 1
            upper -= 1
            lower -= 1
        elif c == 1:
            if upper >= lower:
                top[i] = 1
                upper -= 1
            else:
                bot[i] = 1
                lower -= 1
        if upper < 0 or lower < 0:
            return []
    if upper != 0 or lower != 0:
        return []
    return [top, bot]

function reconstructMatrix(upper, lower, colsum) {
  const n = colsum.length;
  const top = new Array(n).fill(0);
  const bot = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    const c = colsum[i];
    if (c === 2) {
      top[i] = bot[i] = 1;
      upper--; lower--;
    } else if (c === 1) {
      if (upper >= lower) { top[i] = 1; upper--; }
      else { bot[i] = 1; lower--; }
    }
    if (upper < 0 || lower < 0) return [];
  }
  if (upper !== 0 || lower !== 0) return [];
  return [top, bot];
}

class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        Integer[] top = new Integer[n], bot = new Integer[n];
        Arrays.fill(top, 0); Arrays.fill(bot, 0);
        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                top[i] = bot[i] = 1; upper--; lower--;
            } else if (colsum[i] == 1) {
                if (upper >= lower) { top[i] = 1; upper--; }
                else { bot[i] = 1; lower--; }
            }
            if (upper < 0 || lower < 0) return new ArrayList<>();
        }
        if (upper != 0 || lower != 0) return new ArrayList<>();
        return List.of(Arrays.asList(top), Arrays.asList(bot));
    }
}

vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
    int n = colsum.size();
    vector<int> top(n, 0), bot(n, 0);
    for (int i = 0; i < n; i++) {
        if (colsum[i] == 2) {
            top[i] = bot[i] = 1; upper--; lower--;
        } else if (colsum[i] == 1) {
            if (upper >= lower) { top[i] = 1; upper--; }
            else { bot[i] = 1; lower--; }
        }
        if (upper < 0 || lower < 0) return {};
    }
    if (upper != 0 || lower != 0) return {};
    return { top, bot };
}

Explanation

We have to rebuild a 2-row matrix where we know how many 1s go in the top row (upper), how many in the bottom row (lower), and the sum of each column. The trick is to decide each column left to right with a simple greedy rule.

For a column whose sum is 2, both cells must be 1, so we place ones in both rows and spend one from each budget. For a column whose sum is 0, both cells are 0 and nothing is spent.

The interesting case is a column summing to 1: exactly one cell is a 1. We give it to whichever row still needs more ones right now — if upper >= lower we put it on top, otherwise on the bottom. Always feeding the hungrier row keeps both budgets balanced so we never get stuck.

Example: upper = 2, lower = 1, colsum = [1, 1, 1]. Column 0: upper(2) >= lower(1), top gets it → upper = 1. Column 1: upper(1) >= lower(1), top again → upper = 0. Column 2: now lower wins → bottom. Result [[1,1,0],[0,0,1]].

If any budget ever drops below zero, or if leftover budget isn't exactly zero at the end, no valid matrix exists and we return an empty list.

Time: O(n) Space: O(n)