Reconstruct a 2-Row Binary Matrix - Video Solutions
Reconstruct a 2-Row Binary Matrix(Leetcode 1253)
Reconstruct a 2-Row Binary Matrix - Video Solution
Watch 6 video solutions for Reconstruct a 2-Row Binary Matrix, a medium level problem involving Array, Greedy, Matrix. This walkthrough by Coding Interviews has 620 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
0or1. - 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], wherecolsumis given as an integer array with lengthn.
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^50 <= upper, lower <= colsum.length0 <= 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.
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 |