956. Tallest Billboard

Problem Description

In this problem, you are given a collection of rods of different lengths, and your goal is to use these rods to create two steel supports for a billboard. The challenge is to make the two supports of equal height. As the supports must be of equal height, you have the flexibility to weld multiple rods together to achieve that. However, you can't cut rods into pieces; you must use the whole rods.

You need to calculate the maximum height that both supports can reach while ensuring they are of the same height. If it's not possible to create two supports of equal height with the given rods, you should return 0.

For instance, if you are provided with rods of lengths 1, 2, 3, one of the ways to create two equal supports is to use the rods 1 and 2 to make one support with a height of 3, and the 3 rod as the other support, also with a height of 3.

Intuition

The intuition behind the solution to this problem lies in dynamic programming, which is a strategy used to solve optimization problems such as this by breaking it down into simpler subproblems. The key to dynamic programming is caching the results of the subproblems to avoid redundant calculations that would otherwise occur in a naive recursive approach.

In this case, we want to keep track of ways to combine rods in such a fashion that the difference in height between the two supports (left and right) can be maintained, or potentially reduced to zero. The approach involves considering each rod and deciding what to do with it for each possible difference in supports' heights: either add it to the taller support, add it to the shorter support, or do not use it at all.

To this end, we create a table f with the first dimension representing the rods considered so far and the second dimension representing the possible differences in height between the two supports. The value in f[i][j] is the tallest height of the shorter support where i rods are considered and the difference in height between the two supports is j.

At every rod i, and for each possible height difference j, we consider three scenarios:

Not using the rod at all and keeping the current height difference.
Adding the rod to the shorter support, which increases its height and decreases the difference j.
Adding the rod to the taller support, which increases the height difference j.

We aim to maximize the height of the shorter support since the two supports must be of equal height.

Iteration continues, building upon previous calculated states, until all rods are considered. The result will be the maximum height of the shorter support with a height difference of 0, meaning both supports are of equal height.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming to iteratively build up a table that represents the maximum height of the shorter support for all combinations of rods considered up to that point and all possible differences in height between the two supports.

Here's how the implementation breaks down:

Initialization: The solution creates a 2D list f where f[i][j] = -inf for all j. This list will be filled during the iterations. f[i][j] will hold the maximum height of the shorter tower when considering the first i rods, and the difference in height between two towers is j. We initialize f[0][0] = 0 because with zero rods considered, the maximum height of the shorter tower with zero height difference is zero.
Outer Loop: The algorithm iterates over each rod in rods. The variable t is used to keep track of the total length of all rods considered so far, which determines the range of j (the difference in height) we need to consider in the inner loop.
Inner Loop: The inner loop iterates through all possible differences in height j from 0 to t. It computes the maximum height f[i][j] of the shorter support for this difference using the following logic:
1. Case 1: Do not use the current rod. The maximum height for the current rod and difference j will be the same as the previous rod for the same difference j, which is f[i - 1][j].
2. Case 2: Use the current rod on the shorter support. If the current difference j is greater than or equal to the current rod length x, we compare the current value with f[i - 1][j - x] + x and take the maximum. This is because we can add the current rod to the shorter support, increasing its height by x, and thus reducing the difference by x.
3. Case 3: Use the current rod on the taller support. If the sum of j and the current rod length x does not exceed t, we compare the current value with f[i - 1][j + x] + x and take the maximum. This effectively adds the rod length to the difference j.
4. Case 4: If j is less than the current rod length x, we can still add the current rod to the shorter support. In this case, the shorter support would become the taller one, and the difference in height would be x - j. So we compare the current value with f[i - 1][x - j] + x - j and take the maximum, since in this case we would transfer the excess length (x - j) to the previously taller support.
Finalization: After considering all rods and all potential height differences, the maximum height of the billboard will be f[n][0], where n is the number of rods. This cell represents the maximum height of the shorter tower with zero height difference between the two towers, which means they are of equal height.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach using rods of lengths 1, 2, 4. We need to create two supports of equal height using these rods.

Initialization:
We initialize an empty table f such that f[i][j] = -inf for all j.
f[0][0] is set to 0 since no rods means no height, and also no height difference.
Outer Loop (Iteration over rods):
- First rod: 1
  - Total length t so far: 1
  - Possible differences j: 0 to 1
  - For j = 0:
    1. Do not use the rod: f[1][0] remains 0 (Case 1)
    2. Use the rod on the shorter support: f[1][1] is updated to 1 (Case 2)
  - For j = 1:
    (This represents the case where there's already a difference of 1 which isn't possible with only one rod.)
- Second rod: 2
  - Total length t so far: 3
  - Possible differences j: 0 to 3
  - For j = 0:
    1. Do not use the rod: f[2][0] remains 0 (Case 1)
    2. Use the rod on the shorter support: f[2][2] is updated to 2 since now both supports can have a height of 1 (Case 4)
  - For j = 1:
    (This would represent the scenario where one support is taller by 1.)
  - For j = 2:
    1. Use the rod on the taller support: f[2][2] becomes 2, as we can have two supports of height 1 (Case 3)
  - For j = 3:
    (This scenario isn't viable with the rods we have so far.)
- Third rod: 4
  - Total length t so far: 7
  - Possible differences j: 0 to 7
  - For j = 0:
    (We already have f[2][2] = 2, suggesting two supports at 1)
    1. Do not use the rod: f[3][0] remains 0 (Case 1)
    2. Use the rod on the shorter support: f[3][4] is updated to 4 (Case 2)
    3. We would not use this rod on the taller support, as it would make the supports unequal.
  - For j = 2:
    (The current best at f[2][2] = 2)
    1. Use the current rod on the shorter support: f[3][2] becomes 4 (Case 4)
  - For j = 4:
    1. Use the rod on the taller support: f[3][4] is already 4, but this scenario is also valid for creating two supports of equal height of 2.
Finalization:
After iterating over all the rods, we look at f[3][0] to find the maximum height of the shorter support with zero height difference. In our case, f[3][0] is 0, but looking at the populated table reveals that we can make two supports of height 2 using the rods 2 and 4, hence the maximum height for the billboard supports is 2.

Solution Implementation

1from typing import List
2
3class Solution:
4    def tallestBillboard(self, rods: List[int]) -> int:
5        # Number of rods
6        num_rods = len(rods)
7        # Sum of all rod lengths
8        total_length = sum(rods)
9        # Initialize a DP table filled with negative infinity to track the highest score
10        # Shape: (num_rods + 1) x (total_length + 1)
11        dp_table = [[float('-inf')] * (total_length + 1) for _ in range(num_rods + 1)]
12        # Base case: When there are no rods, the height difference of 0 is achievable with height 0
13        dp_table[0][0] = 0
14
15        # Running sum of rod lengths
16        current_sum = 0
17        # Iterate over rods
18        for i, length in enumerate(rods, 1):
19            current_sum += length
20            # Try possible heights between 0 and the running sum of rod lengths
21            for j in range(current_sum + 1):
22                # Case 1: Do not add the current rod
23                dp_table[i][j] = dp_table[i - 1][j]
24                # Case 2: Add the current rod to one side
25                if j >= length:
26                    dp_table[i][j] = max(dp_table[i][j], dp_table[i - 1][j - length])
27                # Case 3: Add the current rod to the other side
28                if j + length <= current_sum:
29                    dp_table[i][j] = max(dp_table[i][j], dp_table[i - 1][j + length] + length)
30                # Case 4: Add the current rod to the taller side to make sides more equal
31                if j < length:
32                    dp_table[i][j] = max(dp_table[i][j], dp_table[i - 1][length - j] + length - j)
33      
34        # The goal is to achieve the maximum equal height with height difference 0
35        return dp_table[num_rods][0]
36

1import java.util.Arrays; // Import Arrays utility class
2
3class Solution {
4    public int tallestBillboard(int[] rods) {
5        int numRods = rods.length;
6        int sumRods = 0;
7        // Calculate the sum of all elements in the array rods
8        for (int rod : rods) {
9            sumRods += rod;
10        }
11
12        // Initialize the dp (Dynamic Programming) array with a very small negative value
13        int[][] dp = new int[numRods + 1][sumRods + 1];
14        for (int[] row : dp) {
15            Arrays.fill(row, Integer.MIN_VALUE / 2);
16        }
17      
18        // The base case - a pair of empty billboards has a height difference of 0
19        dp[0][0] = 0;
20      
21        // Iterate over the rods
22        for (int i = 1, totalHeight = 0; i <= numRods; ++i) {
23            int currentRod = rods[i - 1];
24            totalHeight += currentRod;
25          
26            // Update dp array for all possible height differences
27            for (int heightDiff = 0; heightDiff <= totalHeight; ++heightDiff) {
28                // Case 1: Do not use the current rod
29                dp[i][heightDiff] = dp[i - 1][heightDiff];
30              
31                // Case 2: Use the current rod in the taller billboard
32                if (heightDiff >= currentRod) {
33                    dp[i][heightDiff] = Math.max(dp[i][heightDiff], dp[i - 1][heightDiff - currentRod]);
34                }
35              
36                // Case 3: Use the current rod in the shorter billboard
37                if (heightDiff + currentRod <= totalHeight) {
38                    dp[i][heightDiff] = Math.max(dp[i][heightDiff], dp[i - 1][heightDiff + currentRod] + currentRod);
39                }
40              
41                // Case 4: Current rod makes up the difference in billboard heights
42                if (heightDiff < currentRod) {
43                    dp[i][heightDiff] = Math.max(dp[i][heightDiff], dp[i - 1][currentRod - heightDiff] + currentRod - heightDiff);
44                }
45            }
46        }
47      
48        // The maximum height of 2 billboards with the same height (height difference of 0)
49        return dp[numRods][0];
50    }
51}
52

1#include <vector>
2#include <numeric>
3#include <cstring>
4#include <algorithm>
5
6class Solution {
7public:
8    int tallestBillboard(std::vector<int>& rods) {
9        const int numRods = rods.size();
10        // Find the sum of all rod lengths to define the dimensions of dp array
11        const int sumRods = std::accumulate(rods.begin(), rods.end(), 0);
12
13        // dp[i][j] will store the maximum height of the taller tower 
14        // of the two we are trying to balance when considering the first i rods
15        // where the difference in height between the towers is j
16        std::vector<std::vector<int>> dp(numRods + 1, std::vector<int>(sumRods + 1));
17
18        // Initialize dp array with very negative numbers to represent unattainable states
19        for (auto &row : dp) {
20            std::fill(row.begin(), row.end(), INT_MIN/2);
21        }
22      
23        // Base case: the first 0 rods, with 0 height difference has 0 height
24        dp[0][0] = 0;
25
26        for (int i = 1, totalRodLength = 0; i <= numRods; ++i) {
27            int rodLength = rods[i - 1];
28            totalRodLength += rodLength;
29            for (int j = 0; j <= totalRodLength; ++j) {
30                // Don't use the current rod, inherit the value from the previous decision
31                dp[i][j] = dp[i - 1][j];
32
33                // If possible, add current rod to the shorter tower to try and balance the towers
34                if (j >= rodLength) {
35                    dp[i][j] = std::max(dp[i][j], dp[i - 1][j - rodLength]);
36                }
37                // If possible, add current rod to the taller tower
38                if (j + rodLength <= totalRodLength) {
39                    dp[i][j] = std::max(dp[i][j], dp[i - 1][j + rodLength] + rodLength);
40                }
41                // If current rod is longer than the difference j, then add the 
42                // difference to the shorter tower to balance the towers
43                if (rodLength >= j) {
44                    dp[i][j] = std::max(dp[i][j], dp[i - 1][rodLength - j] + j);
45                }
46            }
47        }
48
49        // The final state for balanced towers (difference = 0) is the answer
50        return dp[numRods][0];
51    }
52};
53

1function tallestBillboard(rods: number[]): number {
2    // Sum of all rod lengths
3    const totalLength = rods.reduce((acc, rod) => acc + rod, 0);
4    // The number of rods present
5    const numRods = rods.length;
6    // Initialize a DP table with default values of -1
7    const dpTable = new Array(numRods).fill(0).map(() => new Array(totalLength + 1).fill(-1));
8
9    // Define the depth-first search function for DP computation
10    const depthFirstSearch = (currentIndex: number, currentDifference: number): number => {
11        // Base case: if we have considered all rods, return 0 if no difference, else return negative infinity
12        if (currentIndex >= numRods) {
13            return currentDifference === 0 ? 0 : Number.MIN_SAFE_INTEGER;
14        }
15        // Return the cached result if already calculated for this state
16        if (dpTable[currentIndex][currentDifference] !== -1) {
17            return dpTable[currentIndex][currentDifference];
18        }
19      
20        // Compute max height by ignoring the current rod
21        let maxHeight = Math.max(depthFirstSearch(currentIndex + 1, currentDifference),
22                                 // Including the current rod in one of the sides
23                                 depthFirstSearch(currentIndex + 1, currentDifference + rods[currentIndex]));
24        // Including the current rod in the shorter side if it makes the billboard taller
25        maxHeight = Math.max(maxHeight,
26                             depthFirstSearch(currentIndex + 1, Math.abs(currentDifference - rods[currentIndex]))
27                             + Math.min(currentDifference, rods[currentIndex]));
28        // Cache the result in DP table
29        return (dpTable[currentIndex][currentDifference] = maxHeight);
30    };
31
32    // Call the dfs function to compute the maximum height of balanced billboard
33    return depthFirstSearch(0, 0);
34}
35

Time and Space Complexity

The time complexity of the function tallestBillboard is O(n * s^2), where n is the number of elements in rods and s is the sum of all elements in rods. This is because there is a nested loop structure within the function: one loop iterating over the rods with length n and two nested loops iterating up to s, resulting in a cubic time complexity with respect to s.

The space complexity of the function is O(n * s). This is due to the two-dimensional array f which has dimensions [n + 1] by [s + 1], resulting in space usage proportional to the product of n and s.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don’t know