Tallest Billboard

Hard
886.

Tallest Billboard

Tallest Billboard is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Databricks interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} rods
 * @return {number}
 */
var tallestBillboard = function(rods) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Tallest Billboard — Solution in Python, Java & C++

Tallest Billboard solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Tallest Billboard is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Databricks interviews.

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.

Hints for Tallest Billboard

  1. Hint 1

    Enumerating all 3^n assignments is too slow at n = 20.

  2. Hint 2

    Only the difference between the two supports matters, plus the height of the shorter one.

  3. Hint 3

    dp[d] is the tallest shorter-support height achievable with a difference of d.

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

  1. Start with dp[0] = 0 — no rods used, no gap, zero height.
  2. 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)).
  3. 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]

Java

public static int tallestBillboard(int[] rods) {
    int total = 0;
    for (int r : rods) total += r;
    int[] dp = new int[total + 1];
    Arrays.fill(dp, -1);
    dp[0] = 0;
    for (int r : rods) {
        int[] cur = dp.clone();
        for (int d = 0; d <= total; d++) {
            if (dp[d] < 0) continue;
            int v = dp[d];
            int a = d + r;
            if (a <= total && cur[a] < v) cur[a] = v;
            int b = Math.abs(d - r);
            int nv = v + Math.min(d, r);
            if (cur[b] < nv) cur[b] = nv;
        }
        dp = cur;
    }
    return dp[0];
}

C++

int tallestBillboard(vector<int>& rods) {
    int total = 0;
    for (int r : rods) total += r;
    vector<int> dp(total + 1, -1);
    dp[0] = 0;
    for (int r : rods) {
        vector<int> cur = dp;
        for (int d = 0; d <= total; d++) {
            if (dp[d] < 0) continue;
            int v = dp[d];
            int a = d + r;
            if (a <= total && cur[a] < v) cur[a] = v;
            int b = abs(d - r);
            int nv = v + min(d, r);
            if (cur[b] < 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming