Skip to main content

956. Tallest Billboard

hard

Given rods of various lengths, pick a subset to split into two equal-height stacks; return the maximum stack height. 2D DP keyed on (rod index, height difference) — height difference shrinks the state space dramatically.

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

Brute force 3^n is too slow at n = 20. Use the height-difference state.

Hint 2

dp[diff] = the maximum height of the TALLER stack across all subsets of processed rods whose two stacks differ by diff. (Equivalently, dp[diff] = max stack sum where left - right == diff with left >= right.)

Hint 3

For each rod r, update three transitions: skip it; add it to the taller stack (diff += r, tall += r); add it to the shorter stack (diff -= r if r <= diff, else diff = r - diff, tall stays or grows).

Hint 4

Final answer is dp[0] — the maximum equal height of two stacks.

Solution approach

Reveal approach

DP on height difference. Maintain a dictionary dp where dp[d] = max height of the taller stack such that (taller - shorter) == d using a subset of processed rods. Initialize dp[0] = 0 (empty subset gives equal-height pair of 0). For each rod r, build a new dictionary newDp. For each (d, tall) in dp: option 1, skip the rod: newDp[d] = max(newDp.get(d, 0), tall). Option 2, add r to the taller stack: newDp[d + r] = max(..., tall + r). Option 3, add r to the shorter stack: let shorter = tall - d. If r <= d, newDp[d - r] = max(..., tall). If r > d, the shorter stack overtakes, newDp[r - d] = max(..., tall + r - d). Replace dp = newDp. Answer is dp[0] — both stacks equal height. The diff dimension is bounded by sum/2, so the table is O(n * sum) at most.

Complexity

Time
O(n * sum)
Space
O(sum)

Related patterns

  • dynamic-programming
  • knapsack
  • subset-sum

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 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →