1253. Reconstruct a 2-Row Binary Matrix LeetCode Solution

In this guide, you will get 1253. Reconstruct a 2-Row Binary Matrix LeetCode Solution with the best time and space complexity. The solution to Reconstruct a -Row Binary Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Reconstruct a -Row Binary Matrix solution in C++
Reconstruct a -Row Binary Matrix solution in Java
Reconstruct a -Row Binary Matrix solution in Python
Additional Resources

1253. Reconstruct a 2-Row Binary Matrix LeetCode Solution image

Problem Statement of Reconstruct a -Row Binary Matrix

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.

Example 1:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2:

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []

Example 3:

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Constraints:

1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

Complexity Analysis

Time Complexity:
Space Complexity:

1253. Reconstruct a 2-Row Binary Matrix LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> reconstructMatrix(int upper, int lower,
                                        vector<int>& colsum) {
    if (upper + lower != accumulate(colsum.begin(), colsum.end(), 0))
      return {};
    if (min(upper, lower) <
        ranges::count_if(colsum, [](int c) { return c == 2; }))
      return {};

    vector<vector<int>> ans(2, vector<int>(colsum.size()));

    for (int j = 0; j < colsum.size(); ++j)
      if (colsum[j] == 2) {
        ans[0][j] = 1;
        ans[1][j] = 1;
        --upper;
        --lower;
      }

    for (int j = 0; j < colsum.size(); ++j) {
      if (colsum[j] == 1 && upper > 0) {
        ans[0][j] = 1;
        --colsum[j];
        --upper;
      }

      if (colsum[j] == 1 && lower > 0) {
        ans[1][j] = 1;
        --lower;
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1253. Reconstruct a 2-Row Binary Matrix LeetCode Solution in Java

class Solution {
  public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
    if (upper + lower != Arrays.stream(colsum).sum())
      return new ArrayList<>();

    int count = 0;
    for (int c : colsum)
      if (c == 2)
        ++count;

    if (Math.min(upper, lower) < count)
      return new ArrayList<>();

    int[][] ans = new int[2][colsum.length];

    for (int j = 0; j < colsum.length; ++j)
      if (colsum[j] == 2) {
        ans[0][j] = 1;
        ans[1][j] = 1;
        --upper;
        --lower;
      }

    for (int j = 0; j < colsum.length; ++j) {
      if (colsum[j] == 1 && upper > 0) {
        ans[0][j] = 1;
        --colsum[j];
        --upper;
      }

      if (colsum[j] == 1 && lower > 0) {
        ans[1][j] = 1;
        --lower;
      }
    }

    return new ArrayList(Arrays.asList(ans[0], ans[1]));
  }
}
// code provided by PROGIEZ

1253. Reconstruct a 2-Row Binary Matrix LeetCode Solution in Python

class Solution:
  def reconstructMatrix(self, upper: int, lower: int, colsum: list[int]) -> list[list[int]]:
    if upper + lower != sum(colsum):
      return []
    if min(upper, lower) < colsum.count(2):
      return []

    ans = [[0] * len(colsum) for _ in range(2)]

    for j, c in enumerate(colsum):
      if c == 2:
        ans[0][j] = 1
        ans[1][j] = 1
        upper -= 1
        lower -= 1

    for j, c in enumerate(colsum):
      if c == 1 and upper > 0:
        ans[0][j] = 1
        c -= 1
        upper -= 1
      if c == 1 and lower > 0:
        ans[1][j] = 1
        lower -= 1

    return ans
 # code by PROGIEZ