Reconstruct a 2 row binary matrix

Array Greedy Matrix

48.7% acceptance

Feb 25, 2026

484

Given the following details of a matrix with n columns and 2 rows : The matrix is a binary matrix, which means each element in the matrix can be 0 or 1. The sum of elements of the 0-th(upper) row is given as upper. The sum of elements of the 1-st(lower) row is given as lower. The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n. Your task is to reconstruct the matrix with upper, lower and colsum. Return it as a 2-D integer array. If there are more than one valid solution, any of them will be accepted. If no valid solution exists, return an empty 2-D array.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn reconstruct_matrix(upper: i32, lower: i32, colsum: Vec<i32>) -> Vec<Vec<i32>> {
    let n = colsum.len();
    let mut row0 = vec![0i32; n];
    let mut row1 = vec![0i32; n];
    let mut u = upper;
    let mut l = lower;

    // First pass: handle colsum == 2
    for i in 0..n {
      if colsum[i] == 2 {
        row0[i] = 1;
        row1[i] = 1;
        u -= 1;
        l -= 1;
      }
    }
    if u < 0 || l < 0 { return vec![]; }

    // Second pass: handle colsum == 1
    for i in 0..n {
      if colsum[i] == 1 {
        if u > 0 {
          row0[i] = 1;
          u -= 1;
        } else if l > 0 {
          row1[i] = 1;
          l -= 1;
        } else {
          return vec![];
        }
      }
    }

    if u != 0 || l != 0 { return vec![]; }
    vec![row0, row1]
  }
}