{x}
blog image

Tallest Billboard

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.

 

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.

 

Constraints:

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

956. Tallest Billboard

This problem asks to find the largest possible height of a billboard given a collection of rods, where each side of the billboard must be of equal height. This can be solved using dynamic programming.

Approach 1: Top-Down DP with Memoization

This approach uses a recursive function with memoization to explore all possible combinations of rods.

Intuition:

We can think of this as a subset sum problem with a twist. We need to find two subsets of rods with equal sums. The sum of each subset represents the height of one side of the billboard.

Algorithm:

  1. dfs(i, j): This recursive function takes the index i of the current rod being considered and the difference j between the sums of the two subsets.
  2. Base Case: If i reaches the end of the rods array:
    • If j is 0, it means the two subsets have equal sums, and the height is the sum of one subset (which is sum(rods)/2).
    • Otherwise, it's an invalid combination, and we return a very small value (-inf in Python, -(1 << 30) in other languages) to indicate this.
  3. Recursive Steps: For each rod rods[i], we have three options:
    • Exclude it: We recursively call dfs(i + 1, j).
    • Add it to the first subset: We recursively call dfs(i + 1, j + rods[i]).
    • Add it to the second subset: We recursively call dfs(i + 1, abs(rods[i] - j)) + min(j, rods[i]). This is the tricky part. We add rods[i] to the subset with a smaller current sum to try and balance the sums. We also add the min(j, rods[i]) because this represents the additional height gained by balancing the sums.
  4. Memoization: We use a cache (f in Java, C++, Go, @cache decorator in Python) to store the results of subproblems to avoid redundant calculations.
  5. Return Value: The maximum height found among the three recursive calls.

Time Complexity: O(nsum(rods)), where n is the number of rods. In the worst case, we explore all possible combinations of subsets. Space Complexity: O(nsum(rods)) for the memoization table.

Approach 2: Bottom-Up DP with Tabulation

This approach iteratively builds a DP table to solve the problem.

Intuition:

Similar to Approach 1, but instead of recursion, we build a table where f[i][j] represents the maximum height achievable using the first i rods and a difference of j between the sums of the two subsets.

Algorithm:

  1. Initialization: Create a DP table f with dimensions (n+1) x (sum(rods)+1), initialized with a very small value (similar to Approach 1). f[0][0] = 0 because with no rods, the difference is 0 and the height is 0.
  2. Iteration: Iterate through the rods and the possible difference values.
  3. Transitions: For each rod x and difference j, update f[i][j] based on the following transitions (similar to the recursive cases in Approach 1):
    • f[i][j] = max(f[i][j], f[i - 1][j]) (exclude rod)
    • f[i][j] = max(f[i][j], f[i - 1][j - x]) (add to first subset)
    • f[i][j] = max(f[i][j], f[i - 1][j + x] + x) (add to second subset)
    • f[i][j] = max(f[i][j], f[i - 1][abs(x - j)] + min(j, x)) (add to smaller subset to balance)

Time Complexity: O(nsum(rods)) Space Complexity: O(nsum(rods)) for the DP table.

Both approaches have the same time and space complexity, but the bottom-up approach might be slightly more efficient in practice due to the absence of recursive function calls. The provided code examples demonstrate both approaches in various programming languages. Remember that -inf or a very small negative number is used to represent an invalid state. The final answer is f[n][0] (the maximum height achievable with all rods and a difference of 0).