Skip to main content
Talentd

Reconstruct a 2-Row Binary Matrix - Solution & Explanation

MediumArrayGreedyMatrix20 min readAsked at: Grab
Practice this problem

Problem Statement

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.

The solution initiates two arrays to represent the two rows of the matrix. It first fills in columns where colsum[i] = 2 since these are mandatory 1s on both rows, decrementing both 'upper' and 'lower'. For columns where colsum[i] = 1, it attempts to fill the upper row first if possible, otherwise, the lower row. If at the end of processing, 'upper' or 'lower' still has remaining capacity, the solution returns NULL.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n), where n is the length of the colsum array, as the loop runs through the elements of the array.

Space complexity: O(n) due to the storage of the result array.

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.

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.

Code

PythonJavaScript

Python

JavaScript

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time complexity: O(n), where n is the length of the colsum array, as the loop runs through the elements of the array.

Space complexity: O(n) due to the storage of the result array.

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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy ConstructionO(n)O(n)Best general solution; single pass assignment based on column constraints
Sorting-Based AllocationO(n log n)O(n)When prioritizing strict constraints first or experimenting with ordered processing

Video Solution

Reconstruct a 2-Row Binary Matrix(Leetcode 1253) • Coding Interviews • 620 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Reconstruct a 2-Row Binary Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Valid Matrix Given Row and Column Sums