Abstract / Summary

Given the top row and the sum of each column, create the bottom row of a two-row binary matrix so each column's total matches the given sums.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 49% (70k+ submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of reconstructing a 2-row binary matrix from three inputs: the required sum of the first row (upper), the required sum of the second row (lower), and a list describing the sum of each column (colsum). The algorithm determines whether a feasible matrix exists and, if so, builds one concrete solution.

Key Steps

Validation of total column sum

if sum(colsum) != upper + lower:
    return []

Before any construction begins, the code checks that the total number of ones required by the rows matches the total number of ones implied by the column specifications. If the sums differ, reconstruction is impossible and an empty list is returned immediately.

Handling columns with sum 0 and sum 2

one = []
two = []
for c in colsum:
    if   c == 0:
        one.append(0)
        two.append(0)
    elif c == 2:
        one.append(1)
        two.append(1)
        upper -= 1
        lower -= 1
    else: # c == 1
        ...

During a single traversal of colsum, the algorithm treats columns whose required sum is 0 by placing a 0 in both rows. For columns with a required sum of 2, a 1 is placed in both rows, and the remaining capacities of upper and lower are decremented accordingly. This step ensures that mandatory placements are resolved early, reducing the decision space for the remaining columns.

Distributing columns with sum 1

    else: # c == 1
        if upper >= lower:
            one.append(1)
            two.append(0)
            upper -= 1
        else:
            one.append(0)
            two.append(1)
            lower -= 1

When a column requires exactly one 1, the algorithm decides which row receives it based on the current remaining capacities. If the first row still needs at least as many ones as the second row, the 1 is assigned to the first row; otherwise, it goes to the second row. After the assignment, the corresponding counter (upper or lower) is decreased. This greedy choice respects the remaining row sums while preserving feasibility for the rest of the columns.

Final verification and result construction

return [ one, two ] if upper == 0 and lower == 0 else []

After processing all columns, the algorithm verifies that both row counters have been reduced to zero, meaning the constructed rows exactly satisfy the required sums. If this condition holds, the two rows are returned as a list of lists; otherwise, an empty list signals that no valid reconstruction exists.

Edge Cases Handled

The code explicitly addresses several boundary conditions. When the total sum of colsum does not equal the combined row requirements, it aborts early, covering cases where the input is inherently contradictory. Columns with a sum of 0 are safely filled with zeros, guaranteeing that no unintended ones are introduced. Columns with a sum of 2 are forced to contain ones in both rows, and the algorithm correctly updates both upper and lower to reflect this consumption. For columns with a sum of 1, the decision logic ensures that the row with the larger remaining quota receives the one, preventing premature exhaustion of either row’s capacity. Finally, the concluding check that both upper and lower have reached zero catches any leftover imbalance that might arise from earlier assignments, ensuring that only fully consistent matrices are returned.

Performance Optimizations

The implementation achieves efficiency by processing the input in a single linear pass. All necessary information-row assignments and counter updates-is handled within the same loop, eliminating the need for additional passes or auxiliary data structures. The use of two parallel lists (one and two) to accumulate the rows avoids repeated list concatenations, which can be costly. By decrementing upper and lower immediately after each mandatory placement, the algorithm maintains up-to-date state, allowing the greedy decision for columns with sum 1 to be made with constant-time checks. The early exit on mismatched total sums prevents unnecessary work on inputs that cannot be satisfied, further reducing runtime for invalid cases.

Imagine there are two rows of boxes that need to be filled with either a zero or a one. You are told exactly how many ones must be in the top row and the bottom row. Also, each column has a label that tells you how many ones should be inside that specific column.

First, the code checks if the total number of ones in all the column labels matches the total number of ones allowed for the top and bottom rows combined. If the numbers do not add up, it is impossible to fill the boxes, so the process stops.

The code then walks through each column one by one to decide what goes in the boxes. If a column label is zero, both boxes get a zero because there are no ones to place. If a column label is two, both boxes must get a one, which uses up one of the spots available for the top row and one for the bottom row.

When a column label is one, there is a choice to make. The code looks at how many ones are still needed for the top row versus the bottom row. It gives a one to the row that still needs more, helping keep things balanced. After walking through every column, the code checks one last time to make sure that the exact number of ones required for each row was used.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality