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
wheref[i][j] = -inf
for allj
. This list will be filled during the iterations.f[i][j]
will hold the maximum height of the shorter tower when considering the firsti
rods, and the difference in height between two towers isj
. We initializef[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 variablet
is used to keep track of the total length of all rods considered so far, which determines the range ofj
(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
from0
tot
. It computes the maximum heightf[i][j]
of the shorter support for this difference using the following logic:-
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 differencej
, which isf[i - 1][j]
. -
Case 2: Use the current rod on the shorter support. If the current difference
j
is greater than or equal to the current rod lengthx
, we compare the current value withf[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 byx
, and thus reducing the difference byx
. -
Case 3: Use the current rod on the taller support. If the sum of
j
and the current rod lengthx
does not exceedt
, we compare the current value withf[i - 1][j + x] + x
and take the maximum. This effectively adds the rod length to the differencej
. -
Case 4: If
j
is less than the current rod lengthx
, 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 bex - j
. So we compare the current value withf[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]
, wheren
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 EvaluatorExample 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 tablef
such thatf[i][j] = -inf
for allj
.
f[0][0]
is set to0
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
to1
- For
j = 0
:- Do not use the rod: f[1][0] remains
0
(Case 1) - Use the rod on the shorter support: f[1][1] is updated to
1
(Case 2)
- Do not use the rod: f[1][0] remains
- For
j = 1
:
(This represents the case where there's already a difference of1
which isn't possible with only one rod.)
- Total length
- Second rod:
2
- Total length
t
so far:3
- Possible differences
j
:0
to3
- For
j = 0
:- Do not use the rod: f[2][0] remains
0
(Case 1) - Use the rod on the shorter support: f[2][2] is updated to
2
since now both supports can have a height of1
(Case 4)
- Do not use the rod: f[2][0] remains
- For
j = 1
:
(This would represent the scenario where one support is taller by1
.) - For
j = 2
:- Use the rod on the taller support: f[2][2] becomes
2
, as we can have two supports of height1
(Case 3)
- Use the rod on the taller support: f[2][2] becomes
- For
j = 3
:
(This scenario isn't viable with the rods we have so far.)
- Total length
- Third rod:
4
- Total length
t
so far:7
- Possible differences
j
:0
to7
- For
j = 0
:
(We already have f[2][2] =2
, suggesting two supports at1
)- Do not use the rod: f[3][0] remains
0
(Case 1) - Use the rod on the shorter support: f[3][4] is updated to
4
(Case 2) - We would not use this rod on the taller support, as it would make the supports unequal.
- Do not use the rod: f[3][0] remains
- For
j = 2
:
(The current best at f[2][2] =2
)- Use the current rod on the shorter support: f[3][2] becomes
4
(Case 4)
- Use the current rod on the shorter support: f[3][2] becomes
- For
j = 4
:- 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 of2
.
- Use the rod on the taller support: f[3][4] is already
- Total length
- First rod:
-
Finalization:
After iterating over all the rods, we look atf[3][0]
to find the maximum height of the shorter support with zero height difference. In our case,f[3][0]
is0
, but looking at the populated table reveals that we can make two supports of height2
using the rods2
and4
, hence the maximum height for the billboard supports is2
.
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.
Which of the following problems can be solved with backtracking (select multiple)
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.