{x}
blog image

Reconstruct a 2-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

Solution Explanation: Reconstruct a 2-Row Binary Matrix

This problem involves reconstructing a 2xN binary matrix given the sum of each row (upper, lower) and the sum of each column (colsum). The solution uses a greedy approach for efficiency.

Approach:

The core idea is to iteratively fill the matrix column by column, making locally optimal choices based on the available sums. We prioritize filling the row with the larger remaining sum when a column sum is 1, ensuring we don't get stuck with an unsolvable situation.

  1. Initialization: Create a 2xN matrix (ans) filled with zeros.

  2. Iteration: Iterate through the colsum array. For each column j:

    • colsum[j] == 2: Both rows must have a 1 in this column. Decrement upper and lower.
    • colsum[j] == 1: Only one row can have a 1. If upper > lower, place the 1 in the top row (decrement upper); otherwise, place it in the bottom row (decrement lower).
    • colsum[j] == 0: Both rows have a 0 in this column.

  3. Validity Check: After processing all columns, check if both upper and lower are 0. If they are, a valid matrix has been constructed, and ans is returned. Otherwise, no valid solution exists, and an empty matrix is returned.

Time Complexity: O(N), where N is the number of columns. We iterate through the colsum array once.

Space Complexity: O(N), dominated by the space used for the 2xN matrix ans.

Code Examples (with explanations inline):

Python:

def reconstructMatrix(upper: int, lower: int, colsum: list[int]) -> list[list[int]]:
    n = len(colsum)  # Number of columns
    ans = [[0] * n for _ in range(2)]  # Initialize the 2xN matrix with zeros
 
    for j, v in enumerate(colsum): #Iterate through colsum
        if v == 2:  #Both rows have 1
            ans[0][j] = ans[1][j] = 1
            upper -= 1
            lower -= 1
        elif v == 1:  #Only one row has 1
            if upper > lower:
                ans[0][j] = 1
                upper -= 1
            else:
                ans[1][j] = 1
                lower -= 1
        #if v==0, no action needed as initialized to 0
 
        if upper < 0 or lower < 0:  # Check for invalid state (sums become negative)
            return []
 
    return ans if upper == 0 and lower == 0 else [] # Return the matrix if valid, otherwise empty list

Java:

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        int n = colsum.length;
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<>()); //First row
        ans.add(new ArrayList<>()); //Second row
 
        for (int j = 0; j < n; ++j) {
            ans.get(0).add(0);
            ans.get(1).add(0);  //Initialize rows with 0
 
            if (colsum[j] == 2) {
                ans.get(0).set(j, 1);
                ans.get(1).set(j, 1);
                upper--;
                lower--;
            } else if (colsum[j] == 1) {
                if (upper > lower) {
                    ans.get(0).set(j, 1);
                    upper--;
                } else {
                    ans.get(1).set(j, 1);
                    lower--;
                }
            }
            if (upper < 0 || lower < 0) {
                return new ArrayList<>(); // Return empty list if invalid state
            }
        }
        return (upper == 0 && lower == 0) ? ans : new ArrayList<>(); //Return matrix if valid
    }
}

The other languages (C++, Go, TypeScript) will follow a similar structure, adapting the syntax and data structures specific to each language. The core logic remains the same greedy approach described above.