1253. Reconstruct a 2-Row Binary Matrix - Solution

Q: Is Reconstruct a 2-Row Binary Matrix easy or hard?

The problem is rated Medium because the implementation is simple but recognizing the greedy constraint logic requires careful reasoning. Once you realize columns with sum 2 and 0 are forced placements, the rest of the matrix construction becomes straightforward.

Q: Reconstruct a 2-Row Binary Matrix Python/Java solution

The greedy algorithm is straightforward to implement in Python, Java, C++, C#, or JavaScript. Create two arrays of length n, iterate through colsum, handle forced columns first, and assign flexible columns based on remaining upper and lower counts. The implementation runs in O(n) time in all languages.

Q: How to solve Reconstruct a 2-Row Binary Matrix in O(n)?

Iterate through colsum and first handle columns with value 2 by placing 1 in both rows and decreasing upper and lower. Next process columns with value 1, assigning the 1 to whichever row still has remaining quota. If either upper or lower becomes negative or remains non-zero at the end, no valid matrix exists. This single pass approach achieves O(n) time complexity.

Q: What is the best approach for Reconstruct a 2-Row Binary Matrix?

The greedy approach is the best solution. Handle forced columns first: if colsum[i] is 2, both rows must contain 1; if it is 0, both rows contain 0. For columns with sum 1, assign the 1 to the row that still has remaining capacity. This runs in O(n) time and constructs the matrix in a single pass.

Q: Is Reconstruct a 2-Row Binary Matrix asked at Google/Amazon/Meta?

Variants of constrained matrix construction and greedy allocation appear in interviews at companies like Amazon, Google, and Meta. The problem tests your ability to identify forced choices and apply a greedy strategy while maintaining row sum constraints.

Q: What data structure is used in Reconstruct a 2-Row Binary Matrix?

The solution mainly uses arrays to represent the two rows of the matrix and the input column sums. Greedy decisions are applied while iterating through the array. No advanced data structures are required beyond simple array manipulation.

Q: What is the time complexity of Reconstruct a 2-Row Binary Matrix?

The optimal greedy solution runs in O(n) time where n is the number of columns in the matrix. Each column is processed once and assignments are constant time operations. Space complexity is O(n) because the algorithm stores the resulting 2 x n matrix.

The 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.

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

Approach overview

Problem Overview: You receive three inputs: upper, lower, and an array colsum. The goal is to construct a 2 x n binary matrix where the first row sums to upper, the second row sums to lower, and each column sum matches colsum[i]. If no valid matrix exists, return an empty result.

Approach 1: Greedy Construction (O(n) time, O(n) space)

This problem works well with a greedy strategy because some column sums force a unique decision. If colsum[i] == 2, both rows must contain 1 at that column. If colsum[i] == 0, both rows must contain 0. The only flexible case is when colsum[i] == 1, where you choose which row receives the 1. Start by iterating through the array and assigning all forced columns (2) first, decrementing upper and lower. Then process columns with sum 1, placing the 1 in whichever row still has remaining quota. If either quota becomes negative or non‑zero after processing all columns, the matrix is impossible to construct.

This method relies on simple iteration over the array and constant‑time assignments. The greedy decision works because forced columns reduce the remaining capacity deterministically, leaving only balanced placement for colsum == 1. The algorithm runs in O(n) time with O(n) space for the result matrix. Problems like this often appear in interview sets related to greedy algorithms and constrained distribution using arrays.

Approach 2: Sorting-Based Allocation (O(n log n) time, O(n) space)

An alternative idea is to process columns in priority order. Create pairs of (colsum, index) and sort them in descending order so that columns requiring stronger constraints are handled first. Columns with value 2 are filled in both rows, while columns with value 1 are assigned based on which row still has remaining capacity. Sorting guarantees that the most restrictive columns are processed before flexible ones, which simplifies reasoning about feasibility.

After sorting, iterate through the ordered columns and update the matrix accordingly while tracking remaining values of upper and lower. If at any step neither row can accept a required value, the configuration is invalid. While the logic remains similar to the greedy approach, sorting adds an O(n log n) overhead. This approach can feel more intuitive when you think in terms of prioritizing constraints rather than scanning sequentially. The matrix construction itself still uses simple operations typical in matrix manipulation problems.

Recommended for interviews: The greedy construction is the expected solution. Interviewers look for recognition that columns with sum 2 and 0 are forced decisions, which simplifies the rest of the allocation. Explaining this reasoning clearly shows strong problem‑solving skills. The sorting approach works but adds unnecessary complexity compared to the linear greedy pass.

Approach 1: Greedy Approach

This problem can be effectively tackled with a greedy approach. The primary objective is to iterate through the colsum array and appropriately fill the values in two subarrays that represent the upper and lower rows of the matrix.

Here's the strategy:

First fill the columns with colsum[i] = 2. Such columns must have a '1' in both upper and lower rows, reducing both the respective sums by one.
Next handle columns with colsum[i] = 1, distributing the '1's between upper and lower rows based on their remaining capacities.
Finally, ensure that both upper sum and lower sum reach zero. If they don't, it means a valid solution isn't found.

Python

def reconstructMatrix(upper, lower, colsum):
    upper_row = [0] * len(colsum)
    lower_row = [0] * len(colsum)

    for i, c in enumerate(colsum):
        if c == 2:
            if upper > 0 and lower > 0:
                upper_row[i] = 1
                lower_row[i] = 1
                upper -= 1
                lower -= 1
            else:
                return []

    for i, c in enumerate(colsum):
        if c == 1:
            if upper > lower:
                upper_row[i] = 1
                upper -= 1
            elif lower > 0:
                lower_row[i] = 1
                lower -= 1

    if upper == 0 and lower == 0:
        return [upper_row, lower_row]
    else:
        return []

Java

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        List<List<Integer>> result = new ArrayList<>();
        int n = colsum.length;
        List<Integer> topRow = new ArrayList<>();
        List<Integer> bottomRow = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            topRow.add(0);
            bottomRow.add(0);
        }

        for (int i = 0; i < n; i++) {
            if (colsum[i] == 2) {
                if (upper > 0 && lower > 0) {
                    topRow.set(i, 1);
                    bottomRow.set(i, 1);
                    upper--;
                    lower--;
                } else {
                    return new ArrayList<>();
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (colsum[i] == 1) {
                if (upper > lower) {
                    topRow.set(i, 1);
                    upper--;
                } else {
                    bottomRow.set(i, 1);
                    lower--;
                }
            }
        }

        if (upper != 0 || lower != 0) {
            return new ArrayList<>();
        }
        result.add(topRow);
        result.add(bottomRow);
        return result;
    }
}

C++

#include <vector>
using namespace std;

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

JavaScript

function reconstructMatrix(upper, lower, colsum) {
    let upperRow = Array(colsum.length).fill(0);
    let lowerRow = Array(colsum.length).fill(0);

    for (let i = 0; i < colsum.length; i++) {
        if (colsum[i] === 2) {
            if (upper > 0 && lower > 0) {
                upperRow[i] = 1;
                lowerRow[i] = 1;
                upper--;
                lower--;
            } else {
                return [];
            }
        }
    }

    for (let i = 0; i < colsum.length; i++) {
        if (colsum[i] === 1) {
            if (upper > lower) {
                upperRow[i] = 1;
                upper--;
            } else if (lower > 0) {
                lowerRow[i] = 1;
                lower--;
            }
        }
    }

    if (upper === 0 && lower === 0) {
        return [upperRow, lowerRow];
    } else {
        return [];
    }
}

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

int** reconstructMatrix(int upper, int lower, int* colsum, int colsumSize, int* returnSize, int** returnColumnSizes) {
    int** matrix = (int**)malloc(2 * sizeof(int*));
    for (int i = 0; i < 2; i++) {
        matrix[i] = (int*)calloc(colsumSize, sizeof(int));
    }
    
    *returnColumnSizes = (int*)malloc(colsumSize * sizeof(int));
    for (int i = 0; i < colsumSize; i++) {
        (*returnColumnSizes)[i] = 2;
    }
    *returnSize = 2;

    for (int i = 0; i < colsumSize; i++) {
        if (colsum[i] == 2) {
            if (upper > 0 && lower > 0) {
                matrix[0][i] = 1;
                matrix[1][i] = 1;
                upper--;
                lower--;
            } else {
                return NULL;
            }
        }
    }

    for (int i = 0; i < colsumSize; i++) {
        if (colsum[i] == 1) {
            if (upper > 0) {
                matrix[0][i] = 1;
                upper--;
            } else if (lower > 0) {
                matrix[1][i] = 1;
                lower--;
            } else {
                return NULL;
            }
        }
    }

    if (upper != 0 || lower != 0) {
        return NULL;
    }
    
    return matrix;
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> ReconstructMatrix(int upper, int lower, int[] colsum) {
        List<IList<int>> result = new List<IList<int>>();
        int[] topRow = new int[colsum.Length];
        int[] bottomRow = new int[colsum.Length];

        for (int i = 0; i < colsum.Length; i++) {
            if (colsum[i] == 2) {
                if (upper > 0 && lower > 0) {
                    topRow[i] = 1;
                    bottomRow[i] = 1;
                    upper--;
                    lower--;
                } else {
                    return new List<IList<int>>();
                }
            }
        }
        for (int i = 0; i < colsum.Length; i++) {
            if (colsum[i] == 1) {
                if (upper > lower) {
                    topRow[i] = 1;
                    upper--;
                } else {
                    bottomRow[i] = 1;
                    lower--;
                }
            }
        }
        if (upper != 0 || lower != 0) {
            return new List<IList<int>>();
        }
        result.Add(topRow);
        result.Add(bottomRow);
        return result;
    }
}

This Python solution follows a greedy approach, processing columns with sum of 2 first, decrementing 'upper' and 'lower' appropriately. It then processes sums of 1 based on remaining capacity.

Complexity

Time complexity: O(n), iterating through the column sums once.

Space complexity: O(n) for lists used for upper and lower rows.

Try this approach in the editor

Approach 2: Alternative Sorting Approach

An alternative method involves treating each column sum specifically and sorting columns by their necessity. Sort colsum indices directly by values, and cater sums of 2 first, then sums of 1. This ensures sum handling in priority order.

Steps involved:

Track indices of 2s and 1s separately.
Fill values using sort order, ensuring columns of 2s are dealt with first, followed by 1s based on descending 'upper' and 'lower' to equalize fill.

Python

def reconstructMatrix(upper, lower, colsum):
    sorted_indices = sorted(range(len(colsum)), key=lambda i: -colsum[i])
    upper_row = [0] * len(colsum)
    lower_row = [0] * len(colsum)
    
    for i in sorted_indices:
        if colsum[i] == 2:
            if upper > 0 and lower > 0:
                upper_row[i] = 1
                lower_row[i] = 1
                upper -= 1
                lower -= 1
            else:
                return []

    for i in sorted_indices:
        if colsum[i] == 1:
            if upper > 0:
                upper_row[i] = 1
                upper -= 1
            elif lower > 0:
                lower_row[i] = 1
                lower -= 1

    if upper == 0 and lower == 0:
        return [upper_row, lower_row]
    else:
        return []

JavaScript

function reconstructMatrix(upper, lower, colsum) {
    const sortedIndices = [...Array(colsum.length).keys()].sort((a, b) => colsum[b] - colsum[a]);
    const upperRow = Array(colsum.length).fill(0);
    const lowerRow = Array(colsum.length).fill(0);

    for (let i of sortedIndices) {
        if (colsum[i] === 2) {
            if (upper > 0 && lower > 0) {
                upperRow[i] = 1;
                lowerRow[i] = 1;
                upper--;
                lower--;
            } else {
                return [];
            }
        }
    }

    for (let i of sortedIndices) {
        if (colsum[i] === 1) {
            if (upper > lower) {
                upperRow[i] = 1;
                upper--;
            } else if (lower > 0) {
                lowerRow[i] = 1;
                lower--;
            }
        }
    }

    if (upper === 0 && lower === 0) {
        return [upperRow, lowerRow];
    } else {
        return [];
    }
}

This Python solution increases potential efficiency during fill by sorting columns in descending order of necessity, handling the sums of 2 first. Its strategy allows earlier decisive fills in a given priority order, then addresses available 1s afterwards.

Complexity

Time complexity: O(n log n), for sorting indexes by colsum values and O(n) for fill operations.

Space complexity: O(n) for upper and lower row space.

Try this approach in the editor

Approach 3: Greedy

First, we create an answer array ans, where ans[0] and ans[1] represent the first and second rows of the matrix, respectively.

Next, we traverse the array colsum from left to right. For the current element colsum[j], we have the following cases:

If colsum[j] = 2, then we set both ans[0][j] and ans[1][j] to 1. In this case, both upper and lower are reduced by 1.
If colsum[j] = 1, then we set either ans[0][j] or ans[1][j] to 1. If upper \gt lower, then we prefer to set ans[0][j] to 1; otherwise, we prefer to set ans[1][j] to 1. In this case, either upper or lower is reduced by 1.
If colsum[j] = 0, then we set both ans[0][j] and ans[1][j] to 0.
If upper \lt 0 or lower \lt 0, then it is impossible to construct a matrix that meets the requirements, and we return an empty array.

At the end of the traversal, if both upper and lower are 0, then we return ans; otherwise, we return an empty array.

The time complexity is O(n), where n is the length of the array colsum. Ignoring the space consumption of the answer array, the space complexity is O(1).

TypeScript

function reconstructMatrix(upper: number, lower: number, colsum: number[]): number[][] {
    const n = colsum.length;
    const ans: number[][] = Array(2)
        .fill(0)
        .map(() => Array(n).fill(0));
    for (let j = 0; j < n; ++j) {
        if (colsum[j] === 2) {
            ans[0][j] = ans[1][j] = 1;
            upper--;
            lower--;
        } else if (colsum[j] === 1) {
            if (upper > lower) {
                ans[0][j] = 1;
                upper--;
            } else {
                ans[1][j] = 1;
                lower--;
            }
        }
        if (upper < 0 || lower < 0) {
            break;
        }
    }
    return upper || lower ? [] : ans;
}

func reconstructMatrix(upper int, lower int, colsum []int) [][]int {
	n := len(colsum)
	ans := make([][]int, 2)
	for i := range ans {
		ans[i] = make([]int, n)
	}
	for j, v := range colsum {
		if v == 2 {
			ans[0][j], ans[1][j] = 1, 1
			upper--
			lower--
		}
		if v == 1 {
			if upper > lower {
				upper--
				ans[0][j] = 1
			} else {
				lower--
				ans[1][j] = 1
			}
		}
		if upper < 0 || lower < 0 {
			break
		}
	}
	if upper != 0 || lower != 0 {
		return [][]int{}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time complexity: O(n), iterating through the column sums once. Space complexity: O(n) for lists used for upper and lower rows.
Alternative Sorting Approach	Time complexity: O(n log n), for sorting indexes by colsum values and O(n) for fill operations. Space complexity: O(n) for upper and lower row space.
Greedy	–

Approach

Complexity

Greedy Approach

Time complexity: O(n), iterating through the column sums once.

Space complexity: O(n) for lists used for upper and lower rows.

Alternative Sorting Approach

Time complexity: O(n log n), for sorting indexes by colsum values and O(n) for fill operations.

Space complexity: O(n) for upper and lower row space.

Greedy

–

Complexity analysis

Approach	Time	Space	When to Use
Greedy Construction	O(n)	O(n)	Best general solution; single pass assignment based on column constraints
Sorting-Based Allocation	O(n log n)	O(n)	When prioritizing strict constraints first or experimenting with ordered processing

Frequently asked questions

Is Reconstruct a 2-Row Binary Matrix easy or hard?

The problem is rated Medium because the implementation is simple but recognizing the greedy constraint logic requires careful reasoning. Once you realize columns with sum 2 and 0 are forced placements, the rest of the matrix construction becomes straightforward.

Reconstruct a 2-Row Binary Matrix Python/Java solution

The greedy algorithm is straightforward to implement in Python, Java, C++, C#, or JavaScript. Create two arrays of length n, iterate through colsum, handle forced columns first, and assign flexible columns based on remaining upper and lower counts. The implementation runs in O(n) time in all languages.

How to solve Reconstruct a 2-Row Binary Matrix in O(n)?

Iterate through colsum and first handle columns with value 2 by placing 1 in both rows and decreasing upper and lower. Next process columns with value 1, assigning the 1 to whichever row still has remaining quota. If either upper or lower becomes negative or remains non-zero at the end, no valid matrix exists. This single pass approach achieves O(n) time complexity.

What is the best approach for Reconstruct a 2-Row Binary Matrix?

The greedy approach is the best solution. Handle forced columns first: if colsum[i] is 2, both rows must contain 1; if it is 0, both rows contain 0. For columns with sum 1, assign the 1 to the row that still has remaining capacity. This runs in O(n) time and constructs the matrix in a single pass.

Is Reconstruct a 2-Row Binary Matrix asked at Google/Amazon/Meta?

Variants of constrained matrix construction and greedy allocation appear in interviews at companies like Amazon, Google, and Meta. The problem tests your ability to identify forced choices and apply a greedy strategy while maintaining row sum constraints.

What data structure is used in Reconstruct a 2-Row Binary Matrix?

The solution mainly uses arrays to represent the two rows of the matrix and the input column sums. Greedy decisions are applied while iterating through the array. No advanced data structures are required beyond simple array manipulation.

What is the time complexity of Reconstruct a 2-Row Binary Matrix?

The optimal greedy solution runs in O(n) time where n is the number of columns in the matrix. Each column is processed once and assignments are constant time operations. Space complexity is O(n) because the algorithm stores the resulting 2 x n matrix.

Reconstruct a 2-Row Binary Matrix solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Alternative Sorting Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Reconstruct a 2-Row Binary Matrix solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Alternative Sorting Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems