Skip to main content

956. Tallest Billboard

hard

Two side-stacks must reach the same height — maximize that common height. A subset-sum knapsack indexed by the DIFFERENCE between stacks rather than the total.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height. You are given a collection of rods that can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6. Return the largest possible height of your billboard installation. If you cannot support the billboard, return 0.

Constraints

  • 1 <= rods.length <= 20
  • 1 <= rods[i] <= 1000
  • sum(rods[i]) <= 5000

Examples

Example 1

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

Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.

Example 2

Input
rods = [1,2,3,4,5,6]
Output
10

Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.

Example 3

Input
rods = [1,2]
Output
0

Explanation: The billboard cannot be supported, so we return 0.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Each rod can go into the left stack, the right stack, or neither.

Hint 2

Track dp[d] = the tallest left stack achievable when (left - right) = d. The difference can range over a small window of sum.

Hint 3

For each rod with length r, update three transitions per current state: skip, add to left (d += r), add to right (d -= r).

Solution approach

Reveal approach

Key insight: instead of tracking both stacks, track the difference d = left - right and store the tallest left stack reaching that difference. Hash map dp where dp[d] = max left-stack height with left - right = d. Initialize dp[0] = 0 (both stacks empty). For each rod r build a new map next from dp. For each state (d, left): next[d] = max(next[d], left) (skip the rod); next[d + r] = max(next[d + r], left + r) (add to left); next[d - r] = max(next[d - r], left) (add to right — left stays, right grows so d decreases by r). Replace dp with next. Return dp.get(0, 0). O(L * D) where L is the number of rods and D is the achievable difference span — fits the sum <= 5000 budget.

Complexity

Time
O(L * sum)
Space
O(sum)

Related patterns

  • dynamic-programming
  • knapsack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Tallest Billboard and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →