Tallest Billboard

Tallest Billboard

What is this problem about?

The Tallest Billboard coding problem is a challenging variation of the "Subset Sum" or "Partition" problem. You are given an array of rods with different lengths. You want to construct two billboards (two sets of rods) of the same height. Each rod can be used in the left billboard, the right billboard, or not at all. Your goal is to find the maximum height these billboards can reach.

Why is this asked in interviews?

Microsoft and Atlassian ask this "Hard" problem to evaluate a candidate's mastery of dynamic programming. It requires a clever definition of the DP state. Instead of tracking the height of both billboards separately (which would be too large), you track the difference in height between them. This significantly reduces the state space and allows for an efficient solution. It tests your ability to perform complex optimization under constraints.

Algorithmic pattern used

The core pattern is Dynamic Programming.

• Define dp[diff] as the maximum height of the shorter billboard for a given height difference diff between the two billboards.
• For each rod of length L:
  1. Add it to the taller billboard: new diff = diff + L, shorter height remains the same.
  2. Add it to the shorter billboard:
     • If L < diff: new diff = diff - L, shorter height increases by L.
     • If L >= diff: new diff = L - diff, shorter height increases by the old diff.
  3. Don't use the rod: no change. At the end, dp[0] will give you the maximum height when the difference is zero.

Example explanation

Rods: [1, 2, 3]

• Start: dp[0] = 0, all others -infinity.
• Rod 1: dp[1] = 0 (add to taller), dp[1] = 0 (add to shorter, but it flips).
• Rod 2:
  • Add to 1: dp[3] = 0, dp[1] = 1 (added to shorter, 1+2=3, 1-2=-1, flip diff to 1).
• Rod 3:
  • Add to diff 3: dp[0] = 3 (added to shorter billboard of height 0, now both are 3). Final dp[0] = 3. The maximum height is 3 (using rod 3 on one side and rods 1, 2 on the other).

Common mistakes candidates make

A common mistake is using a 2D DP dp[height1][height2], which is O(total_sum²). Given the sum can be up to 5000, this is too much. Another mistake is failing to correctly handle the "flipping" logic when a rod added to the shorter billboard makes it taller than the previously taller one. Many candidates also forget to initialize the DP table with negative infinity (to represent unreachable states).

Interview preparation tip

For the Tallest Billboard interview question, focus on the Dynamic Programming interview pattern and how to optimize state space. Practice other "balance" problems where the difference between two groups is the key. Understanding how to transform a multi-variable state into a single-variable difference state is a hallmark of advanced DP problem solving.