How do you solve Reconstruct a 2-Row Binary Matrix on LeetCode?

Reconstruct a 2-Row Binary Matrix (LeetCode #1253) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The sum of colsum must equal the total of upper and lower for a valid solution.

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

The optimal solution for Reconstruct a 2-Row Binary Matrix runs in O(n) time and uses O(1) space. The complexity is O(n) because we only make a single pass through the colsum array, filling the matrix based on the conditions.

What is the brute force solution for Reconstruct a 2-Row Binary Matrix?

The brute force approach for Reconstruct a 2-Row Binary Matrix is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach would involve trying to fill the matrix by checking all possible combinations of 0s and 1s for each column, which is inefficient. We will check each column and decide how to fill it based on the constraints provided. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Reconstruct a 2-Row Binary Matrix?

Reconstruct a 2-Row Binary Matrix uses the following concepts: Array, Greedy, Matrix. The recommended patterns to study are: Greedy, Array.

What are the interview tips for Reconstruct a 2-Row Binary Matrix?

Clearly explain your thought process while solving the problem. Consider edge cases, such as when upper or lower is zero. Practice writing clean and efficient code, as clarity is key in interviews.

What are common mistakes when solving Reconstruct a 2-Row Binary Matrix?

Not checking if upper and lower sums are exhausted before returning the result. Confusing the filling order for columns with a value of 1.

#1253

Reconstruct a 2-Row Binary Matrix

Medium

ArrayGreedyMatrixGreedyArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution directly fills the matrix based on the values in colsum, ensuring we respect the constraints for upper and lower sums without unnecessary checks. This is efficient and straightforward.

⚙️

Algorithm

4 steps

1Step 1: Initialize a 2D array of size 2 x n with all zeros.
2Step 2: Iterate through each column in colsum.
3Step 3: For each column, if colsum[i] is 2, fill both rows with 1 and decrease upper and lower accordingly; if colsum[i] is 1, fill the upper row if possible, otherwise fill the lower row.
4Step 4: After filling, check if upper and lower are both zero; if so, return the result, otherwise return an empty array.

solution.py19 lines

1# Full working Python code
2
3def reconstructMatrix(upper, lower, colsum):
4    n = len(colsum)
5    result = [[0] * n for _ in range(2)]
6    for i in range(n):
7        if colsum[i] == 2:
8            result[0][i] = 1
9            result[1][i] = 1
10            upper -= 1
11            lower -= 1
12        elif colsum[i] == 1:
13            if upper > 0:
14                result[0][i] = 1
15                upper -= 1
16            else:
17                result[1][i] = 1
18                lower -= 1
19    return result if upper == 0 and lower == 0 else []

ℹ

Complexity note: The complexity is O(n) because we only make a single pass through the colsum array, filling the matrix based on the conditions.

1The sum of colsum must equal the total of upper and lower for a valid solution.
2Filling the matrix based on the constraints of colsum ensures that we respect the limits of upper and lower.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.