Reconstruct a 2-Row Binary Matrix - Practice Coding Problems

Reconstruct a 2-Row Binary Matrix - Problem

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.

Input & Output

Example 1 — Basic Valid Case

$ Input: upper = 1, lower = 1, colsum = [1,1,0]

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

💡 Note: Column 0 needs sum 1: place 1 in upper row. Column 1 needs sum 1: place 1 in lower row. Column 2 needs sum 0: both rows get 0. Row sums: upper=1, lower=1 ✓

Example 2 — Column Sum 2

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

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

💡 Note: Column 0 needs sum 2: place 1 in both rows. Column 1 needs sum 1: place 1 in upper row (has higher remaining quota). Column 2 needs sum 0. Final sums: upper=2, lower=1 ✓

Example 3 — Impossible Case

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

› Output: []

💡 Note: Column sums total 4 but upper+lower=2. Impossible to satisfy both constraints, so return empty array.

Constraints

1 ≤ colsum.length ≤ 10⁵
0 ≤ upper, lower ≤ colsum.length
0 ≤ colsum[i] ≤ 2

Visualization

Tap to expand

Understanding the Visualization

Input

Row sums (upper=1, lower=1) and column sums [1,1,0]

Process

Greedily assign 1s to satisfy both row and column constraints

Output

Valid 2×3 binary matrix [[1,0,0],[0,1,0]]

Key Takeaway

🎯 Key Insight: Each column sum dictates exactly how many 1s it needs - use greedy quota tracking

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to process columns greedily based on their sum constraints while tracking remaining row quotas. For columns with sum=2, both rows get 1. For sum=1, assign to the row with higher remaining quota. Best approach is Greedy with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Column-by-Column	O(n)	O(1)	Process each column based on its sum constraint and remaining row quotas
Brute Force - Try All Combinations	O(2^(2n))	O(1)	Generate all possible 2×n binary matrices and check constraints

Greedy Column-by-Column — Algorithm Steps

Check if total column sums equals upper + lower
For each column with sum=2, place 1s in both rows
For columns with sum=1, place 1 in the row with higher remaining quota
For columns with sum=0, place 0s in both rows

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set up matrix and track remaining row quotas

Process

For each column, assign based on sum and quotas

Validate

Check if all quotas are satisfied

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** solution(int upper, int lower, int* colsum, int colsumSize, int* returnSize, int** returnColumnSizes) {
    int n = colsumSize;
    
    // Check if solution is possible
    int totalSum = 0;
    for (int i = 0; i < n; i++) {
        totalSum += colsum[i];
    }
    if (totalSum != upper + lower) {
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }
    
    int** matrix = (int**)malloc(2 * sizeof(int*));
    matrix[0] = (int*)calloc(n, sizeof(int));
    matrix[1] = (int*)calloc(n, sizeof(int));
    
    int upperRemaining = upper;
    int lowerRemaining = lower;
    
    // Process each column
    for (int j = 0; j < n; j++) {
        if (colsum[j] == 2) {
            // Both rows must have 1
            matrix[0][j] = 1;
            matrix[1][j] = 1;
            upperRemaining--;
            lowerRemaining--;
        } else if (colsum[j] == 1) {
            // One row must have 1, choose greedily
            if (upperRemaining > lowerRemaining) {
                matrix[0][j] = 1;
                upperRemaining--;
            } else {
                matrix[1][j] = 1;
                lowerRemaining--;
            }
        }
        // colsum[j] == 0: both stay 0
        
        // Early termination if impossible
        if (upperRemaining < 0 || lowerRemaining < 0) {
            free(matrix[0]);
            free(matrix[1]);
            free(matrix);
            *returnSize = 0;
            *returnColumnSizes = NULL;
            return NULL;
        }
    }
    
    // Final validation
    if (upperRemaining == 0 && lowerRemaining == 0) {
        *returnSize = 2;
        *returnColumnSizes = (int*)malloc(2 * sizeof(int));
        (*returnColumnSizes)[0] = n;
        (*returnColumnSizes)[1] = n;
        return matrix;
    } else {
        free(matrix[0]);
        free(matrix[1]);
        free(matrix);
        *returnSize = 0;
        *returnColumnSizes = NULL;
        return NULL;
    }
}

int main() {
    int upper, lower;
    scanf("%d", &upper);
    scanf("%d", &lower);
    
    // Simple parsing for small arrays
    int colsum[20];
    int n = 0;
    char c;
    scanf(" %c", &c); // '['
    while (scanf("%d", &colsum[n]) == 1) {
        n++;
        scanf("%c", &c);
        if (c == ']') break;
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(upper, lower, colsum, n, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through n columns

✓ Linear Growth

Space Complexity

O(1)

Only storing result matrix and quota variables

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Column-by-Column — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler