Tallest Billboard — Hard Problem & Solution

You are installing a billboard held up by two steel supports of equal height.

Difficulty: Hard
Topics: Arrays, Dynamic Programming
Asked at: Amazon, Google, Databricks
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are installing a billboard held up by two steel supports of equal height. You may weld some of the rods together into each support (each rod used at most once, and some rods may be left out).

Return the tallest billboard you can install, or 0 if no two equal-height supports can be built.

Example 1

Input: rods = [1,2,3,6]
Output: 6
Explanation: 1 + 2 + 3 on one side, 6 on the other.

Example 2

Input: rods = [1,2,3,4,5,6]
Output: 10
Explanation: 2 + 3 + 5 against 4 + 6.

Example 3

Input: rods = [1,2]
Output: 0
Explanation: No equal split exists.

Constraints

1 <= rods.length <= 20
1 <= rods[i] <= 1000
The sum of rods is at most 5000.

How to solve Tallest Billboard

Track the state as the height gap between the two supports, keeping for each gap the tallest achievable shorter support. The absolute heights are recoverable from those two numbers, so nothing is lost.

Approach

Start with dp[0] = 0 — no rods used, no gap, zero height.
For each rod, consider three options: skip it, add it to the taller side (gap grows by r), or add it to the shorter side (gap becomes |d - r| and the shorter height grows by min(d, r)).
Keep the best shorter height per gap, and return dp[0] at the end.

Why it works

Adding a rod to the shorter side raises the shorter support by min(d, r): either the rod is shorter than the gap and the shorter side simply grows by r, or it overshoots and the old taller side becomes the new shorter one at height d above. Either way the formula is exact. Since the total is at most 5000, the gap ranges over a small set and the DP stays small.

Complexity

Time — O(n · S) where S is the total rod length
Space — O(S)

Pitfalls

Storing the taller height instead of the shorter one makes the transition messier and easy to get wrong.
The 'skip' option must be carried forward explicitly.
The answer is dp[0], the height when the two supports are level — not the maximum over all gaps.

Reference solution

Python

from typing import List

def tallestBillboard(rods: List[int]) -> int:
    dp = {0: 0}
    for r in rods:
        cur = dict(dp)
        for d, v in dp.items():
            a = d + r
            if cur.get(a, -1) < v:
                cur[a] = v
            b = abs(d - r)
            nv = v + min(d, r)
            if cur.get(b, -1) < nv:
                cur[b] = nv
        dp = cur
    return dp[0]

JavaScript

var tallestBillboard = function(rods) {
    var dp = {};
    dp[0] = 0;
    for (var i = 0; i < rods.length; i++) {
        var r = rods[i];
        var cur = {};
        var keys = Object.keys(dp), t;
        for (t = 0; t < keys.length; t++) cur[keys[t]] = dp[keys[t]];
        for (t = 0; t < keys.length; t++) {
            var d = Number(keys[t]);
            var v = dp[d];
            var a = d + r;
            if (cur[a] === undefined || cur[a] < v) cur[a] = v;
            var b = Math.abs(d - r);
            var nv = v + Math.min(d, r);
            if (cur[b] === undefined || cur[b] < nv) cur[b] = nv;
        }
        dp = cur;
    }
    return dp[0];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue