Tallest Billboard: DP on Difference Between Two Subsets

LeetCode 956, Tallest Billboard, is a hard problem that asks you to split a collection of steel rods into two groups of equal total height, maximizing that height. You can also leave some rods unused. Think of it as building two billboard supports that must be the same height, and you want them as tall as possible.

The problem

You have a collection of rods with given lengths. You want to build two supports using a subset of these rods such that both supports have the same height. Maximize this height. If you cannot make any two supports of equal height, return 0.

Input:  rods = [1, 2, 3, 6]
Output: 6

Place rod 6 on one support and rods 1, 2, 3 on the other. Both have height 6.

Why this problem matters

This problem belongs to a family of subset-sum and partition problems, but it adds a twist: you are not just asking whether a partition exists, you are optimizing the height of the equal partition. Classic partition problems like "Partition Equal Subset Sum" (LeetCode 416) use a boolean DP over possible sums. That approach does not work here because the rods can be left unused, and you need the maximum equal sum, not just any equal sum.

The "difference" state trick is the key technique that unlocks this problem. Instead of tracking both support heights (which would create a state space of O(S^2) where S is the total sum), you track only the difference between them. This reduces the state space to O(S) and lets you solve the problem efficiently. The same trick shows up whenever you need to partition items into two groups and care about how close their totals are, or when you want to maximize a shared value while keeping two running totals in sync.

Understanding this technique also builds your fluency with DP state design in general. Many hard DP problems become tractable once you find the right state representation. Here, the insight is that absolute heights of both supports carry redundant information when you already know their difference and the height of the taller one.

The brute force approach

Each rod can go to support A, support B, or be skipped entirely. That gives 3^n possible assignments for n rods. For each assignment, check whether the two supports have equal height and track the maximum.

def tallestBillboard_brute(rods):
    best = 0
    n = len(rods)
    for mask in range(3 ** n):
        a, b = 0, 0
        temp = mask
        for i in range(n):
            choice = temp % 3
            if choice == 1:
                a += rods[i]
            elif choice == 2:
                b += rods[i]
            temp //= 3
        if a == b:
            best = max(best, a)
    return best

This runs in O(3^n) time, which is far too slow for the constraint of up to 20 rods (3^20 is about 3.5 billion). We need something much better.

The key insight

Instead of tracking both support heights independently (which would be a huge state space), track only the difference between them. The DP state is dp[diff] = max height of the taller support when the difference between supports is diff.

For each rod, you have three choices: skip it, add it to the taller support (increasing the difference), or add it to the shorter support (decreasing the difference, possibly flipping which is taller).

At the end, dp[0] gives the maximum height where both supports are equal.

Walking through it step by step

Let's trace the DP on rods = [1, 2, 3, 6]. The dictionary dp maps each difference to the maximum height of the taller support achievable with that difference.

The solution

def tallestBillboard(rods):
    dp = {0: 0}
    for rod in rods:
        new_dp = dict(dp)
        for diff, taller in dp.items():
            shorter = taller - diff

            # Choice 1: skip rod (already in new_dp from copy)

            # Choice 2: add rod to the taller support
            new_dp[diff + rod] = max(new_dp.get(diff + rod, 0), taller + rod)

            # Choice 3: add rod to the shorter support
            new_diff = abs(shorter + rod - taller)
            new_taller = max(shorter + rod, taller)
            new_dp[new_diff] = max(new_dp.get(new_diff, 0), new_taller)
        dp = new_dp
    return dp.get(0, 0)

Here is how each piece works:

1. Initialize dp = {0: 0}. Before placing any rods, the only state is difference 0 with taller height 0.

2. For each rod, copy dp into new_dp. The copy handles the "skip" choice since all existing states carry forward unchanged.

3. For each existing state (diff, taller), compute shorter = taller - diff. The shorter support has height taller - diff by definition.

4. Add rod to taller support. The new difference is diff + rod and the new taller height is taller + rod. The shorter support is untouched.

5. Add rod to shorter support. The shorter support becomes shorter + rod. If shorter + rod exceeds taller, it becomes the new taller support, and the difference flips. We use abs() for the new difference and max() for the new taller height.

6. After processing all rods, dp[0] is the answer. A difference of 0 means both supports are equal, and the stored value is their shared height.

Complexity analysis

The difference can range from 0 to S (the sum of all rod lengths), so the dictionary has at most S + 1 keys at any point. For each of the n rods, we iterate over all current keys and perform constant work per key. This gives O(n * S) total time. The space is O(S) for the dictionary. With the constraint that the sum of rods is at most 5000, this is very efficient.

Building blocks

1. DP keyed on subset-sum difference

The core pattern is using the difference between two running totals as the DP key instead of tracking both totals independently.

# Generic pattern: partition items into two groups,
# track difference -> max value of taller group
dp = {0: 0}
for item in items:
    new_dp = dict(dp)
    for diff, taller in dp.items():
        shorter = taller - diff
        # Add item to taller group
        new_dp[diff + item] = max(new_dp.get(diff + item, 0), taller + item)
        # Add item to shorter group
        new_diff = abs(shorter + item - taller)
        new_taller = max(shorter + item, taller)
        new_dp[new_diff] = max(new_dp.get(new_diff, 0), new_taller)
    dp = new_dp

This pattern works for any problem where you split items into two groups and want to maximize (or minimize) a value subject to the groups being equal or close in sum.

2. Three-way rod assignment

Each item has three choices: group A, group B, or skip. The "skip" choice is handled implicitly by copying the old DP before processing updates.

# The copy handles "skip" for free
new_dp = dict(dp)
# Then only two explicit branches per state:
#   add to taller, add to shorter

This three-way branching is what distinguishes the problem from a simple two-partition where every item must be used. The ability to skip items means you cannot just check whether sum / 2 is achievable.

Edge cases

• All rods the same length: [5, 5, 5, 5]. Put two on each side. Answer = 10.
• Single rod: [7]. Cannot make two equal supports. Answer = 0.
• Two equal rods: [3, 3]. One on each side. Answer = 3.
• No valid partition: [1, 2, 4]. No way to split into two groups with equal sum (possible sums: 0, 1, 2, 3, 4, 5, 6, 7; no two disjoint subsets share the same sum except the empty set). Answer = 0.
• Large total with hidden equal split: [1, 2, 3, 100]. The subset {1, 2, 3} sums to 6. Best equal split from that is {3} vs {1, 2}, both summing to 3. Rod 100 cannot pair with anything. Answer = 3.

Common mistakes

1. Tracking both heights independently. Using dp[a][b] where a and b are the two support heights leads to O(S^2) space, which is too large. The difference trick collapses this to O(S).

2. Forgetting to copy dp before updating. If you update dp in place, a rod processed in one state might feed into another state during the same iteration, effectively using the rod more than once.

3. Not handling the shorter-becomes-taller flip. When you add a rod to the shorter support and it exceeds the taller support, the roles switch. Using abs() for the new difference and max() for the new taller handles this automatically.

4. Using a boolean DP instead of tracking heights. A boolean DP can tell you whether difference 0 is reachable, but it cannot tell you the maximum height at that difference. You need to store the taller height, not just True/False.

5. Assuming all rods must be used. Unlike the equal partition problem (LeetCode 416), rods can be skipped here. The "skip" choice is essential and handled by copying the DP dictionary before processing each rod.

From understanding to recall

You now know that the key to this problem is representing DP state as the difference between two support heights rather than tracking both heights. The three choices (skip, add to taller, add to shorter) give you the transition, and dp[0] at the end gives the answer. But recognizing this pattern under interview pressure requires practice.

The "difference DP" pattern is subtle because it does not look like a standard knapsack or partition problem at first glance. You have to see past the surface framing (billboard supports, steel rods) and recognize the underlying structure: partition items into two groups to maximize a shared sum. Once you have drilled this pattern a few times, the state design becomes second nature.

This is one of roughly 60 reusable building blocks in the CodeBricks system. By practicing each block with spaced repetition until the solution flows naturally, you build the kind of pattern recognition that turns hard problems into routine exercises.

Related posts

• Partition Equal Subset Sum - The classic equal-partition DP that forms the foundation for this problem
• Target Sum - Another problem where you assign items to two groups and track the difference with DP
• Ones and Zeroes - Multi-dimensional subset DP with resource constraints

The best way to cement this pattern is to practice it alongside its cousins. Once you can write the difference DP, the equal-partition boolean DP, and the target-sum counting DP without looking anything up, you own the entire subset-partition family.