Tallest Billboard - Solution & Explanation
Problem Statement
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 <= 201 <= rods[i] <= 1000sum(rods[i]) <= 5000
Approach Overview
Problem Overview: You are given an array of rods where each value represents a rod length. The goal is to build two billboards with equal height using any subset of rods. Each rod can be used on the left support, right support, or skipped. The task is to maximize the common height of the two supports.
Approach 1: Recursive Backtracking with Memoization (Time: O(3^n) worst-case, Space: O(n * sum))
The most direct idea is to explore every choice for each rod: place it on the left support, place it on the right support, or ignore it. This forms a ternary decision tree. The state can be represented by the current rod index and the height difference between the two supports. Memoization stores results for previously computed states so repeated subproblems are avoided. Instead of tracking both heights, store only the difference left - right. This drastically reduces state size and turns the brute force recursion into a manageable dynamic programming style search. This approach is useful for understanding the decision structure before optimizing further.
Approach 2: Dynamic Programming using Difference Array (Time: O(n * sum), Space: O(sum))
The optimal solution tracks the difference between the two billboard heights using a DP map or array. Let dp[diff] represent the maximum possible height of the shorter support when the height difference between supports is diff. For each rod, iterate through existing states and create three transitions: skip the rod, add it to the taller side (increase difference), or add it to the shorter side (reduce difference). When a rod is added to the shorter side, the shorter support height increases. This clever representation avoids tracking both heights separately and keeps the state space bounded by the total rod length. The method relies heavily on state transitions typical in array-based DP problems.
Approach 3: Dynamic Programming with HashMap State Compression (Time: O(n * sum), Space: O(sum))
This variation stores DP states in a hash map instead of a fixed array. The key represents the height difference and the value stores the best achievable shorter height. For each rod, iterate over a snapshot of existing states and update new differences accordingly. Hash maps avoid allocating large arrays when the sum of rods is large but the reachable states are sparse. The transitions mirror the difference-based DP but provide more flexibility. The technique is closely related to memoized state storage used in dynamic programming and memoization problems.
Recommended for interviews: The difference-based dynamic programming solution is what most interviewers expect. It reduces the problem to tracking height differences instead of absolute heights, which keeps the state space small and the runtime manageable. Showing the recursive formulation first demonstrates understanding of the search space, but implementing the optimized DP approach proves you can convert exponential recursion into efficient dynamic programming.
Approach 1: Dynamic Programming Approach
This approach involves using dynamic programming to calculate the maximum possible height of two equal steel supports from given rods. By defining a state that represents the difference of two potential support heights, we can get the maximum height efficiently. The key is to keep track of possible height differences between the two supports as we iterate over each rod.
We use a dictionary dp to store the maximum possible height of the smaller support for each possible height difference. For each rod, we have two choices: add the rod to one support or to the other. We update the dp table accordingly by creating a copy and updating from it to avoid overwriting during iteration.
Complexity
Time Complexity: O(n * sum), where n is the number of rods and sum is the total length of rods.
Space Complexity: O(sum), where sum is the total length of rods.
Approach 2: Approach 1: Dynamic Programming using Difference Array
This approach involves using dynamic programming with a difference array to explore the possible configurations of rods. We maintain a difference map where the key is the difference in height between two groups, and the value is the maximum sum achievable for that difference.
The idea here is to update the difference map as we iterate through each rod, considering it can contribute to either group or be omitted.
A dictionary dp is maintained where each key denotes a possible difference between the height of two supports, and the value denotes the maximum height obtained for this difference. The new height differences are updated for each rod considered, creating new states for the DP table.
Code
Python
C++
Java
JavaScript
C#
Complexity
Time Complexity: O(N * S)
Space Complexity: O(S)
where N is the number of rods and S is the sum of all rods.
Approach 3: Approach 2: Recursive Backtracking with Memoization
This approach uses recursive backtracking along with memoization to explore all possible combinations of placing rods into two groups while aiming to minimize the difference between their sum. An auxiliary function is used to recursively try each rod in either of the sets or ignoring it, memoizing results to prevent redundant calculations.
The recursive function dfs explores all possible assignments of rods into the two groups, with memoization applied using lru_cache to store intermediate result computations. This function seeks to balance the groups while maximizing the sum.
Code
Python
C++
Java
JavaScript
C#
Complexity
Time Complexity: O(N * S)
Space Complexity: O(N * S) for the memoization cache.
Approach 4: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n * sum), where n is the number of rods and sum is the total length of rods. |
| Approach 1: Dynamic Programming using Difference Array | Time Complexity: O(N * S) where N is the number of rods and S is the sum of all rods. |
| Approach 2: Recursive Backtracking with Memoization | Time Complexity: O(N * S) |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking with Memoization | O(3^n) worst-case | O(n * sum) | When first reasoning about the decision tree and exploring all rod placements |
| Dynamic Programming using Difference Array | O(n * sum) | O(sum) | Best general solution when rod lengths are moderate and deterministic DP is preferred |
| DP with HashMap State Compression | O(n * sum) | O(sum) | When reachable states are sparse and using a map avoids allocating large arrays |
Video Solution
Tallest Billboard II DP II Reducing DP States II Hashing II 0/1 Knapsack II Leetcode 956 • Aryan Mittal • 8,634 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Tallest Billboard easy or hard?
Tallest Billboard Python/Java solution
How to solve Tallest Billboard in O(n * sum)?
What is the best approach for Tallest Billboard?
Is Tallest Billboard asked at Google/Amazon/Meta?
What data structure is used in Tallest Billboard?
What is the time complexity of Tallest Billboard?
Ready to solve this problem?
Practice Tallest Billboard with our built-in code editor and test cases.
Practice on FleetCode