LeetCode 956: Tallest Billboard

Problem Restatement

We are given an array rods.

Each rod has a positive length. We want to build two steel supports of equal height.

Each rod can be used in one of three ways:

1. Put it on the left support.
2. Put it on the right support.
3. Do not use it.

Return the largest possible equal height of the two supports.

If no positive equal-height supports can be built, return 0.

The official constraints are:

Source: LeetCode problem statement.

Input and Output

Example function shape:

def tallestBillboard(rods: list[int]) -> int:
    ...

Examples

Example 1:

rods = [1, 2, 3, 6]

Output:

6

Explanation:

We can build two supports:

left  = 1 + 2 + 3 = 6
right = 6

So the answer is 6.

Example 2:

rods = [1, 2, 3, 4, 5, 6]

Output:

10

Explanation:

One valid construction is:

left  = 2 + 3 + 5 = 10
right = 4 + 6 = 10

Example 3:

rods = [1, 2]

Output:

0

There is no way to build two equal positive supports.

First Thought: Try Every Assignment

For each rod, we have three choices:

left support
right support
unused

With n rods, that creates:

3^n

possible assignments.

Since n can be 20, this is too large.

We need to compress the state.

Key Insight

We do not need to know the exact left and right support heights separately.

We only need to know:

1. The difference between the two support heights.
2. The best shorter support height for that difference.

Define:

dp[diff] = best shorter support height

where diff is the absolute difference between the two support heights.

Example:

dp[3] = 7

means:

shorter support = 7
taller support  = 10
difference      = 3

If at the end diff == 0, both supports have the same height. The value dp[0] is the largest equal support height.

State Transitions

For each rod x, and for each existing state:

diff = taller - shorter
shorter = dp[diff]

There are three choices.

Choice 1: Skip the rod

The state stays the same.

new_diff = diff
new_shorter = shorter

Choice 2: Add rod to the taller side

The taller side becomes even taller.

new_diff = diff + x
new_shorter = shorter

Choice 3: Add rod to the shorter side

This is the important case.

Current state:

taller = shorter + diff

After adding x to the shorter side:

candidate = shorter + x

There are two possibilities.

If x <= diff, the shorter side remains shorter:

new_diff = diff - x
new_shorter = shorter + x

If x > diff, the old shorter side becomes taller:

new_diff = x - diff
new_shorter = taller

Both cases can be written as:

new_diff = abs(diff - x)
new_shorter = shorter + min(diff, x)

Why?

The shorter support increases by the amount that closes the gap. That amount is min(diff, x).

Algorithm

Start with:

dp = {0: 0}

This means both supports have height 0.

For each rod x:

1. Copy the current dp into next_dp.
2. For each (diff, shorter) in the old dp:
   • Add x to the taller side.
   • Add x to the shorter side.
   • Keep the best shorter height for each resulting difference.
3. Replace dp with next_dp.

At the end, return:

dp[0]

Correctness

We prove that dp[diff] stores the maximum possible shorter support height for each height difference after processing some prefix of rods.

Initially, before using any rods, the only possible state is two supports of height 0. The difference is 0, and the shorter height is 0, so dp[0] = 0 is correct.

Assume the map is correct before processing a rod x.

For every existing state, the rod has exactly three valid choices: skip it, place it on the taller support, or place it on the shorter support.

Skipping preserves the state.

Placing x on the taller support increases the difference by x and leaves the shorter height unchanged.

Placing x on the shorter support reduces the gap by up to x. If x is larger than the gap, the shorter side becomes the taller side. In both cases, the new difference is abs(diff - x), and the shorter height increases by min(diff, x).

These transitions cover every legal use of rod x, and no transition uses x more than once.

When multiple assignments produce the same difference, keeping only the largest shorter height is safe. A larger shorter height with the same difference is always at least as good for future rods, because it has the same gap and higher support heights.

By induction, after all rods are processed, dp[0] is the maximum shorter height among all assignments with equal supports. Since the difference is 0, that shorter height is also the common support height. Therefore, the algorithm returns the tallest possible billboard.

Complexity

Let:

S = sum(rods)

The constraints give S <= 5000, so this dynamic programming approach fits easily.

Implementation

class Solution:
    def tallestBillboard(self, rods: list[int]) -> int:
        dp = {0: 0}

        for x in rods:
            current = dict(dp)

            for diff, shorter in current.items():
                taller_diff = diff + x
                dp[taller_diff] = max(
                    dp.get(taller_diff, 0),
                    shorter,
                )

                shorter_diff = abs(diff - x)
                shorter_height = shorter + min(diff, x)

                dp[shorter_diff] = max(
                    dp.get(shorter_diff, 0),
                    shorter_height,
                )

        return dp[0]

Code Explanation

We start with one state:

dp = {0: 0}

Both supports have height 0.

For each rod:

for x in rods:

we copy the current map:

current = dict(dp)

This matters because each rod can be used only once. We must not let updates from the current rod create more updates using the same rod again.

For each previous state:

for diff, shorter in current.items():

we first try putting the rod on the taller side:

taller_diff = diff + x
dp[taller_diff] = max(dp.get(taller_diff, 0), shorter)

The difference grows. The shorter support height stays the same.

Then we try putting the rod on the shorter side:

shorter_diff = abs(diff - x)
shorter_height = shorter + min(diff, x)

The new difference is the remaining gap after adding the rod to the shorter side.

The shorter height increases only by the part that helps close the old gap:

min(diff, x)

Then we keep the best result for that difference:

dp[shorter_diff] = max(dp.get(shorter_diff, 0), shorter_height)

Finally:

return dp[0]

returns the largest height where both supports are equal.

Testing

def run_tests():
    s = Solution()

    assert s.tallestBillboard([1, 2, 3, 6]) == 6
    assert s.tallestBillboard([1, 2, 3, 4, 5, 6]) == 10
    assert s.tallestBillboard([1, 2]) == 0

    assert s.tallestBillboard([1, 2, 3, 4]) == 5
    assert s.tallestBillboard([5, 5]) == 5
    assert s.tallestBillboard([1]) == 0
    assert s.tallestBillboard([2, 2, 2, 2]) == 4
    assert s.tallestBillboard([10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) == 10

    print("all tests passed")

run_tests()

Test meaning: