Code Implementation

class Solution:
    def tallestBillboard(self, rods):
        dp = {0: 0}
        for rod in rods:
            cur = dp.copy()
            for diff, taller in cur.items():
                # Put rod on taller side
                dp[diff + rod] = max(dp.get(diff + rod, 0), taller)
                # Put rod on shorter side
                new_diff = abs(diff - rod)
                new_taller = taller + min(rod, diff)
                dp[new_diff] = max(dp.get(new_diff, 0), new_taller)
        return dp[0]
      

class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        unordered_map<int, int> dp;
        dp[0] = 0;
        for (int rod : rods) {
            auto cur = dp;
            for (auto [diff, taller] : cur) {
                dp[diff + rod] = max(dp[diff + rod], taller);
                int new_diff = abs(diff - rod);
                int new_taller = taller + min(rod, diff);
                dp[new_diff] = max(dp[new_diff], new_taller);
            }
        }
        return dp[0];
    }
};
      

class Solution {
    public int tallestBillboard(int[] rods) {
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0, 0);
        for (int rod : rods) {
            Map<Integer, Integer> cur = new HashMap<>(dp);
            for (Map.Entry<Integer, Integer> entry : cur.entrySet()) {
                int diff = entry.getKey(), taller = entry.getValue();
                dp.put(diff + rod, Math.max(dp.getOrDefault(diff + rod, 0), taller));
                int new_diff = Math.abs(diff - rod);
                int new_taller = taller + Math.min(rod, diff);
                dp.put(new_diff, Math.max(dp.getOrDefault(new_diff, 0), new_taller));
            }
        }
        return dp.getOrDefault(0, 0);
    }
}
      

var tallestBillboard = function(rods) {
    let dp = {0: 0};
    for (let rod of rods) {
        let cur = {...dp};
        for (let diff in cur) {
            diff = parseInt(diff);
            let taller = cur[diff];
            // Put rod on taller side
            dp[diff + rod] = Math.max(dp[diff + rod] || 0, taller);
            // Put rod on shorter side
            let new_diff = Math.abs(diff - rod);
            let new_taller = taller + Math.min(rod, diff);
            dp[new_diff] = Math.max(dp[new_diff] || 0, new_taller);
        }
    }
    return dp[0] || 0;
};
      

Problem Description

You are given an array of positive integers called rods, where each element represents the length of a rod. Your task is to build two supports (billboards) of equal height using some (possibly all) rods. Each rod can be used in only one support or not used at all. You must maximize the height of these two equal supports. If it is not possible to build two supports of the same height, return 0.

• Each rod can be used at most once (no reuse).
• The two supports must be of the same height.
• Return the maximum possible height of these two supports.
• If no solution exists, return 0.

Thought Process

At first glance, the problem looks similar to partitioning an array into two subsets of equal sum. However, here we are allowed to leave out some rods, not use all rods, and we want to maximize the equal sum. A brute-force approach would be to try all possible assignments of rods to the two supports or to none, but this is exponential and will not work for large inputs.

The key insight is that for each rod, we have three choices:

• Put it on the left support.
• Put it on the right support.
• Leave it unused.

Solution Approach

We use dynamic programming with a hash map to track the possible differences in heights between the two supports and the best achievable height for the shorter support for each difference.

1. State Representation: We use a map dp where dp[diff] is the maximum height of the shorter support when the height difference between the two supports is diff.
2. Initialization: We start with dp[0] = 0, meaning both supports have height 0.
3. Transition: For each rod, and for each current diff:
   • Add to taller support: The difference increases by rod (diff + rod).
   • Add to shorter support: The difference changes to abs(diff - rod). The new height of the shorter support increases by the minimum of rod and diff.
   • Ignore the rod: No change to dp (implicitly handled).
4. Result: After processing all rods, dp[0] holds the maximum possible height for two equal supports.

We use a hash map for dp to efficiently store and update only the relevant states, since the number of possible differences is much smaller than all possible subset combinations.

Example Walkthrough

Let's use the input rods = [1,2,3,6].

• Start: dp = {0: 0}
• Process 1:
  • Add to taller: dp[1] = 0
  • Add to shorter: dp[1] = 0
  dp = {0: 0, 1: 0}
• Process 2:
  • From diff=0, add to taller: dp[2] = 0
  • Add to shorter: dp[2] = 0
  • From diff=1, add to taller: dp[3] = 0
  • Add to shorter: dp[1] = 1
  dp = {0: 0, 1: 1, 2: 0, 3: 0}
• Process 3:
  • From diff=0, add to taller: dp[3] = 0
  • Add to shorter: dp[3] = 0
  • From diff=1, add to taller: dp[4] = 1
  • Add to shorter: dp[2] = 1
  • From diff=2, add to taller: dp[5] = 0
  • Add to shorter: dp[1] = 2
  • From diff=3, add to taller: dp[6] = 0
  • Add to shorter: dp[0] = 3
  dp = {0: 3, 1: 2, 2: 1, 3: 0, 4: 1, 5: 0, 6: 0}
• Process 6:
  • From diff=0, add to taller: dp[6] = 3
  • Add to shorter: dp[6] = 3
  • From diff=1, add to taller: dp[7] = 2
  • Add to shorter: dp[5] = 2
  • From diff=2, add to taller: dp[8] = 1
  • Add to shorter: dp[4] = 3
  • From diff=3, add to taller: dp[9] = 0
  • Add to shorter: dp[3] = 3
  • From diff=4, add to taller: dp[10] = 1
  • Add to shorter: dp[2] = 5
  • From diff=5, add to taller: dp[11] = 0
  • Add to shorter: dp[1] = 5
  • From diff=6, add to taller: dp[12] = 3
  • Add to shorter: dp[0] = 6
  dp = {0: 6, 1: 5, 2: 5, 3: 3, 4: 3, 5: 2, 6: 3, 7: 2, 8: 1, 9: 0, 10:1, 11:0, 12:3}

At the end, dp[0] = 6, meaning the tallest possible billboard has height 6.

Time and Space Complexity

Brute-force approach: Each rod has 3 choices (left, right, unused), so the total number of combinations is 3^n for n rods. This is exponential and infeasible for large n.

Optimized DP approach: For each rod, we iterate over the current states in the hash map. The number of possible differences is bounded by the sum of all rods (call it S). So, in the worst case, the time and space complexity are O(n*S), where n is the number of rods and S is the sum of their lengths. However, in practice, the number of states is much smaller due to pruning by the hash map.

Summary

The Tallest Billboard problem is a clever twist on subset partitioning. The main insight is to use dynamic programming to track the difference between two supports and the best achievable shorter height for each difference. By updating only the best states and using a hash map, we efficiently explore all combinations without explicit enumeration. This approach balances performance and clarity, making it a powerful technique for similar partitioning and subset problems.