We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Tallest Billboard

Number: 993

Difficulty: Hard

Paid? No

Companies: tcs, Microsoft

Problem Description

Given an array of rods, the goal is to choose a subset to form two supports of equal height. The supports are made by welding together rods, and you should return the maximum possible height of the billboard (i.e. the height of one support). If it's not possible to form two supports of equal height, return 0.

Key Insights

  • Use a dynamic programming (DP) approach to compute the possible differences between the sum of rods on two sides.
  • The DP state maps a difference of heights (left side - right side) to the maximum height of the shorter side (or one side) that can be achieved.
  • For each rod, consider three possibilities: add it to the left support, add it to the right support, or skip it.
  • The final answer is obtained when the difference is zero, meaning both sides are balanced.
  • Since the constraints allow sum(rods) to be up to 5000, a dictionary-based DP is ideal to track only the reachable difference states.

Space and Time Complexity

Time Complexity: O(n * sum(rods)), where n is the number of rods
Space Complexity: O(sum(rods)), due to the DP dictionary which in worst-case holds states for differences up to the total sum.

Solution

We solve this problem using dynamic programming with a dictionary to represent the current achievable differences and corresponding maximum support height. Initially, we set dp[0] = 0 indicating that a difference of 0 is achievable with height 0 for both supports. For each rod, we update possible states by simulating placing the rod on the left side, the right side, or skipping the rod.

  • Adding the rod to the left support: increases the difference by the rod's length.
  • Adding the rod to the right support: decreases the difference by the rod's length.
  • Skip: do nothing.

After processing all rods, the value stored in dp[0] (if available) indicates the maximum height for each support when they are balanced. This method smartly tracks only those differences that can be achieved, making it feasible given the constraint on the sum of rods.

Code Solutions

# Python solution using a dictionary for DP state tracking
class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = {0: 0}  # dp[difference] = maximum height of the lower support when difference (left - right) is "difference"
        for rod in rods:
            # Use a snapshot of dp keys to iterate without interference from modifications
            current_dp = dp.copy()
            for diff, height in current_dp.items():
                # Case 1: Add rod to left support => increases difference by rod
                new_diff = diff + rod
                dp[new_diff] = max(dp.get(new_diff, 0), height + rod)
                # Case 2: Add rod to right support => decreases difference by rod
                new_diff = diff - rod
                # Since height is for the larger side among the two, ensure we take max by keeping the best among them
                dp[new_diff] = max(dp.get(new_diff, 0), height)
        # dp[0] contains the maximum height when the supports are balanced (difference = 0)
        return dp.get(0, 0)
    
# Example usage:
# solution = Solution()
# print(solution.tallestBillboard([1,2,3,6]))
← Back to All Questions