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.

Description Hints 2 Solution Video 15:13

1253. Reconstruct a 2-Row Binary Matrix

Medium49.4% acceptance1 company

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

Asked at 1 company

Grab

Topics

Hints open one at a time

Hint 1

You cannot do anything about colsum[i] = 2 case or colsum[i] = 0 case. Then you put colsum[i] = 1 case to the upper row until upper has reached. Then put the rest into lower row.

Hint 2

Fill 0 and 2 first, then fill 1 in the upper row or lower row in turn but be careful about exhausting permitted 1s in each row.

15:13

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution