Tallest Billboard Problem

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.

Examples

Example 1:

1
2
3


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:

1
2
3


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:

1
2
3


Input: rods = [1,2]
Output: 0
Explanation: The billboard cannot be supported, so we return 0.

Solution

Method 1 – Dynamic Programming with Hash Map

Intuition

We want to split rods into two groups with equal height and maximize that height. We use dynamic programming with a hash map to track all possible differences between two groups and the maximum sum for each difference. For each rod, we can add it to either group or skip it.

Approach

Use a hash map dp where dp[diff] is the maximum sum for the difference diff between two groups.
For each rod, update the map by considering:
- Adding the rod to the left group (increase diff).
- Adding the rod to the right group (decrease diff).
- Skipping the rod (diff unchanged).
After processing all rods, dp[0] is the answer (maximum sum for equal height).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        unordered_map<int, int> dp;
        dp[0] = 0;
        for (int r : rods) {
            auto cur = dp;
            for (auto& [d, h] : cur) {
                dp[d + r] = max(dp[d + r], h);
                dp[d - r] = max(dp[d - r], h + r);
            }
        }
        return dp[0];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func tallestBillboard(rods []int) int {
    dp := map[int]int{0: 0}
    for _, r := range rods {
        cur := make(map[int]int)
        for k, v := range dp {
            cur[k] = v
        }
        for d, h := range cur {
            if dp[d+r] < h {
                dp[d+r] = h
            }
            if dp[d-r] < h+r {
                dp[d-r] = h+r
            }
        }
    }
    return dp[0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
    public int tallestBillboard(int[] rods) {
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(0, 0);
        for (int r : rods) {
            Map<Integer, Integer> cur = new HashMap<>(dp);
            for (Map.Entry<Integer, Integer> e : cur.entrySet()) {
                int d = e.getKey(), h = e.getValue();
                dp.put(d + r, Math.max(dp.getOrDefault(d + r, 0), h));
                dp.put(d - r, Math.max(dp.getOrDefault(d - r, 0), h + r));
            }
        }
        return dp.getOrDefault(0, 0);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    fun tallestBillboard(rods: IntArray): Int {
        val dp = mutableMapOf(0 to 0)
        for (r in rods) {
            val cur = dp.toMap()
            for ((d, h) in cur) {
                dp[d + r] = maxOf(dp.getOrDefault(d + r, 0), h)
                dp[d - r] = maxOf(dp.getOrDefault(d - r, 0), h + r)
            }
        }
        return dp[0] ?: 0
    }
}

1
2
3
4
5
6
7
8


def tallestBillboard(rods: list[int]) -> int:
    dp = {0: 0}
    for r in rods:
        cur = dp.copy()
        for d, h in cur.items():
            dp[d + r] = max(dp.get(d + r, 0), h)
            dp[d - r] = max(dp.get(d - r, 0), h + r)
    return dp.get(0, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


use std::collections::HashMap;
impl Solution {
    pub fn tallest_billboard(rods: Vec<i32>) -> i32 {
        let mut dp = HashMap::new();
        dp.insert(0, 0);
        for r in rods {
            let cur = dp.clone();
            for (&d, &h) in &cur {
                dp.insert(d + r, dp.get(&(d + r)).copied().unwrap_or(0).max(h));
                dp.insert(d - r, dp.get(&(d - r)).copied().unwrap_or(0).max(h + r));
            }
        }
        *dp.get(&0).unwrap_or(&0)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
    tallestBillboard(rods: number[]): number {
        let dp = new Map<number, number>();
        dp.set(0, 0);
        for (const r of rods) {
            const cur = new Map(dp);
            for (const [d, h] of cur.entries()) {
                dp.set(d + r, Math.max(dp.get(d + r) ?? 0, h));
                dp.set(d - r, Math.max(dp.get(d - r) ?? 0, h + r));
            }
        }
        return dp.get(0) ?? 0;
    }
}

Complexity

⏰ Time complexity: O(n*S), where n is the number of rods and S is the sum of rods (state space).
🧺 Space complexity: O(S), for the DP map.

Tallest Billboard Problem#

Problem#

Examples#

Solution#

Method 1 – Dynamic Programming with Hash Map#

Intuition#

Approach#

Code#

Complexity#