Jobs

Interviews

Discussions

Tallest Billboard

Hard

Asked by:

5 views

Topics:

Dynamic Programming

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

Try coding it in LeetCode

Tallest Billboard

Hard

Asked by:

5 views

Topics:

Dynamic Programming

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the `rods` array, and the range of values within the array?
Can the values in the `rods` array be zero or negative?
If it's impossible to build a billboard with equal height towers, what value should I return?
Are duplicate rod lengths allowed in the input array, and how should they be handled?
If multiple billboard heights are possible, should I return the maximum one, or is any valid height acceptable?

Brute Force Solution

Approach

The tallest billboard problem asks us to find the maximum height of two billboards we can create using a given set of rods. The brute force solution involves trying every possible combination of rods to build the two billboards, exploring all possible arrangements.

Here's how the algorithm would work step-by-step:

Consider each rod one at a time.
For each rod, we have three choices: add it to the first billboard, add it to the second billboard, or discard it entirely.
Imagine we are building a decision tree where each branch represents one of these choices for each rod.
We explore every possible path through this tree until we've made a choice for every rod.
For each path (combination of choices), calculate the heights of the two billboards.
If the heights are equal, record that height (which will be the height of each individual billboard).
After exploring all possible paths, find the maximum recorded height. That will be our answer.

Code Implementation

def tallest_billboard_brute_force(rods):
    maximum_height = 0

    def find_max_height(index, sum_billboard_one, sum_billboard_two):
        nonlocal maximum_height

        # Base case: If we've considered all rods
        if index == len(rods):

            # If the billboard heights are equal, update the maximum height
            if sum_billboard_one == sum_billboard_two:
                maximum_height = max(maximum_height, sum_billboard_one)
            return

        # Recursive step: Try all three choices for the current rod
        # Choice 1: Add the rod to the first billboard
        find_max_height(index + 1, sum_billboard_one + rods[index], sum_billboard_two)

        # Choice 2: Add the rod to the second billboard
        find_max_height(index + 1, sum_billboard_one, sum_billboard_two + rods[index])

        # Choice 3: Discard the rod
        find_max_height(index + 1, sum_billboard_one, sum_billboard_two)

    #Initiate the recursive function to explore all possible combinations.
    find_max_height(0, 0, 0)

    return maximum_height

Big(O) Analysis

Time Complexity

O(3^n) – The given brute force solution considers each of the n rods one by one. For each rod, there are three possible choices: add it to the first billboard, add it to the second billboard, or discard it. This creates a decision tree where each node branches into three possibilities. Therefore, the total number of possible combinations explored grows exponentially with the number of rods, resulting in approximately 3^n operations. This exponential growth dominates the runtime, making the time complexity O(3^n).

Space Complexity

O(3^N) – The described brute force solution uses a decision tree where each rod has 3 choices (add to billboard 1, add to billboard 2, or discard). This leads to a recursion tree. The depth of the tree is N, where N is the number of rods, and at each level, there are 3 possible branches. This results in a maximum of 3^N nodes in the implicit recursion call stack. Hence, the space complexity of the recursive call stack is O(3^N).

Optimal Solution

Approach

The core idea is to think about the problem dynamically. Instead of trying every possible combination of bars, we'll build the billboard height step-by-step, always keeping track of the possible height differences we can achieve between the two supporting structures.

Here's how the algorithm would work step-by-step:

Imagine you have a blank slate, a way to remember all the possible differences in height you can create between two supporting structures by using some of the bars so far. Initially, you can only have a height difference of zero because you haven't used any bars.
Consider each bar one at a time. For each bar, you have three choices: put it on the left support, put it on the right support, or don't use it at all.
For each height difference you've tracked, explore what happens if you add the current bar to the left support. This will change the height difference. Update your memory to record the new height difference and the corresponding maximum height of the supports in this situation.
Similarly, explore what happens if you add the current bar to the right support. This will also change the height difference. Update your memory accordingly.
Also, don't forget the option of not using the current bar at all. If you don't use the bar, the height difference remains the same, but you might be able to achieve a greater combined height than you previously had for that difference.
After processing each bar, you'll have a record of the best possible combined height for each achievable height difference.
In the end, you're looking for the maximum possible height when the height difference is zero (meaning the supports are the same height). This represents the tallest possible billboard.

Code Implementation

def tallest_billboard(rods): 
    possible_heights = {0: 0}

    for rod_length in rods: 
        new_heights = possible_heights.copy()

        for height_difference, combined_height in possible_heights.items():

            #Consider adding to the left support.
            new_difference_left = height_difference + rod_length
            new_heights[new_difference_left] = max(new_heights.get(new_difference_left, 0), combined_height)

            #Consider adding to the right support.
            new_difference_right = abs(height_difference - rod_length)
            new_height_right = combined_height + min(height_difference, rod_length)
            new_heights[new_difference_right] = max(new_heights.get(new_difference_right, 0), new_height_right)

        possible_heights = new_heights

    # We want the maximum height when the difference is zero.
    return possible_heights.get(0, 0)

Big(O) Analysis

Time Complexity

O(n * sum) – The algorithm iterates through each of the n bars. For each bar, it considers all possible height differences achievable so far. The range of these differences can be up to the sum of all the bars, which we can denote as 'sum'. Therefore, for each of the n bars, we potentially iterate through all possible height differences up to 'sum'. This leads to a time complexity of O(n * sum).

Space Complexity

O(S) – The algorithm uses a dictionary (or hash map) to store the maximum combined height achievable for each possible height difference. The maximum height difference between the two supports can be at most the sum of all the bar lengths. Let S be the sum of all the elements in the input array `rods`. Therefore, the dictionary can potentially store key-value pairs for height differences ranging from -S to S. Consequently, the auxiliary space used by the dictionary is proportional to S, the sum of the input array elements. This results in a space complexity of O(S).

Edge Cases

Case	How to Handle
Empty input array	Return 0, as no billboard can be built with no rods.
Array with only one rod	Return 0, as one rod cannot form two equal-height towers.
Array with all rods of length 0	Return 0, as the maximum height is 0 when all rods have length 0.
Array with large rod lengths causing integer overflow during summation	Use long data type to prevent integer overflow when calculating sums or differences of rod lengths.
All rods have the same length	If the number of rods is even, the billboard height is sum/2; otherwise, it's impossible and the height is still 0 using dynamic programming approach.
No possible equal-height towers can be built.	The dynamic programming approach correctly returns 0 when no combination results in equal tower heights.
Maximum array size to consider time complexity.	Dynamic programming is suitable up to a certain size but a heuristic approach may be needed for larger arrays.
Negative Rod Lengths.	Throw an error, as rod lengths cannot be negative.

Empty input array

How to Handle:

Return 0, as no billboard can be built with no rods.

Array with only one rod

How to Handle:

Return 0, as one rod cannot form two equal-height towers.

Array with all rods of length 0

How to Handle:

Return 0, as the maximum height is 0 when all rods have length 0.

Array with large rod lengths causing integer overflow during summation

How to Handle:

Use long data type to prevent integer overflow when calculating sums or differences of rod lengths.

All rods have the same length

How to Handle:

If the number of rods is even, the billboard height is sum/2; otherwise, it's impossible and the height is still 0 using dynamic programming approach.

No possible equal-height towers can be built.

How to Handle:

The dynamic programming approach correctly returns 0 when no combination results in equal tower heights.

Maximum array size to consider time complexity.

How to Handle:

Dynamic programming is suitable up to a certain size but a heuristic approach may be needed for larger arrays.

Negative Rod Lengths.

How to Handle:

Throw an error, as rod lengths cannot be negative.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the `rods` array, and the range of values within the array?
Can the values in the `rods` array be zero or negative?
If it's impossible to build a billboard with equal height towers, what value should I return?
Are duplicate rod lengths allowed in the input array, and how should they be handled?
If multiple billboard heights are possible, should I return the maximum one, or is any valid height acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider each rod one at a time.
For each rod, we have three choices: add it to the first billboard, add it to the second billboard, or discard it entirely.
Imagine we are building a decision tree where each branch represents one of these choices for each rod.
We explore every possible path through this tree until we've made a choice for every rod.
For each path (combination of choices), calculate the heights of the two billboards.
If the heights are equal, record that height (which will be the height of each individual billboard).
After exploring all possible paths, find the maximum recorded height. That will be our answer.

Code Implementation

def tallest_billboard_brute_force(rods):
    maximum_height = 0

    def find_max_height(index, sum_billboard_one, sum_billboard_two):
        nonlocal maximum_height

        # Base case: If we've considered all rods
        if index == len(rods):

            # If the billboard heights are equal, update the maximum height
            if sum_billboard_one == sum_billboard_two:
                maximum_height = max(maximum_height, sum_billboard_one)
            return

        # Recursive step: Try all three choices for the current rod
        # Choice 1: Add the rod to the first billboard
        find_max_height(index + 1, sum_billboard_one + rods[index], sum_billboard_two)

        # Choice 2: Add the rod to the second billboard
        find_max_height(index + 1, sum_billboard_one, sum_billboard_two + rods[index])

        # Choice 3: Discard the rod
        find_max_height(index + 1, sum_billboard_one, sum_billboard_two)

    #Initiate the recursive function to explore all possible combinations.
    find_max_height(0, 0, 0)

    return maximum_height

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a blank slate, a way to remember all the possible differences in height you can create between two supporting structures by using some of the bars so far. Initially, you can only have a height difference of zero because you haven't used any bars.
Consider each bar one at a time. For each bar, you have three choices: put it on the left support, put it on the right support, or don't use it at all.
For each height difference you've tracked, explore what happens if you add the current bar to the left support. This will change the height difference. Update your memory to record the new height difference and the corresponding maximum height of the supports in this situation.
Similarly, explore what happens if you add the current bar to the right support. This will also change the height difference. Update your memory accordingly.
Also, don't forget the option of not using the current bar at all. If you don't use the bar, the height difference remains the same, but you might be able to achieve a greater combined height than you previously had for that difference.
After processing each bar, you'll have a record of the best possible combined height for each achievable height difference.
In the end, you're looking for the maximum possible height when the height difference is zero (meaning the supports are the same height). This represents the tallest possible billboard.

Code Implementation

def tallest_billboard(rods): 
    possible_heights = {0: 0}

    for rod_length in rods: 
        new_heights = possible_heights.copy()

        for height_difference, combined_height in possible_heights.items():

            #Consider adding to the left support.
            new_difference_left = height_difference + rod_length
            new_heights[new_difference_left] = max(new_heights.get(new_difference_left, 0), combined_height)

            #Consider adding to the right support.
            new_difference_right = abs(height_difference - rod_length)
            new_height_right = combined_height + min(height_difference, rod_length)
            new_heights[new_difference_right] = max(new_heights.get(new_difference_right, 0), new_height_right)

        possible_heights = new_heights

    # We want the maximum height when the difference is zero.
    return possible_heights.get(0, 0)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0, as no billboard can be built with no rods.
Array with only one rod	Return 0, as one rod cannot form two equal-height towers.
Array with all rods of length 0	Return 0, as the maximum height is 0 when all rods have length 0.
Array with large rod lengths causing integer overflow during summation	Use long data type to prevent integer overflow when calculating sums or differences of rod lengths.
All rods have the same length	If the number of rods is even, the billboard height is sum/2; otherwise, it's impossible and the height is still 0 using dynamic programming approach.
No possible equal-height towers can be built.	The dynamic programming approach correctly returns 0 when no combination results in equal tower heights.
Maximum array size to consider time complexity.	Dynamic programming is suitable up to a certain size but a heuristic approach may be needed for larger arrays.
Negative Rod Lengths.	Throw an error, as rod lengths cannot be negative.

Empty input array

How to Handle:

Return 0, as no billboard can be built with no rods.

Array with only one rod

How to Handle:

Return 0, as one rod cannot form two equal-height towers.

Array with all rods of length 0

How to Handle:

Return 0, as the maximum height is 0 when all rods have length 0.

Array with large rod lengths causing integer overflow during summation

How to Handle:

Use long data type to prevent integer overflow when calculating sums or differences of rod lengths.

All rods have the same length

How to Handle:

If the number of rods is even, the billboard height is sum/2; otherwise, it's impossible and the height is still 0 using dynamic programming approach.

No possible equal-height towers can be built.

How to Handle:

The dynamic programming approach correctly returns 0 when no combination results in equal tower heights.

Maximum array size to consider time complexity.

How to Handle:

Dynamic programming is suitable up to a certain size but a heuristic approach may be needed for larger arrays.

Negative Rod Lengths.

How to Handle:

Throw an error, as rod lengths cannot be negative.