In this guide, you will get 956. Tallest Billboard LeetCode Solution with the best time and space complexity. The solution to Tallest Billboard problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
const int n = rods.size();
const int sum = accumulate(rods.begin(), rods.end(), 0);
// dp[i][j] := the maximum min-height of using rods[0..i) to pile two piles
// that have height difference j
vector<vector<int>> dp(n + 1, vector<int>(sum + 1, -1));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
const int h = rods[i - 1];
for (int j = 0; j <= sum - h; ++j) {
if (dp[i - 1][j] < 0)
continue;
// Don't use rods[i - 1].
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
// Put on the taller pile.
dp[i][j + h] = max(dp[i][j + h], dp[i - 1][j]);
// Put on the shorter pile.
dp[i][abs(j - h)] = max(dp[i][abs(j - h)], dp[i - 1][j] + min(j, h));
}
}
return dp[n][0];
}
}; /* code provided by PROGIEZ */
956. Tallest Billboard LeetCode Solution in Java
class Solution {
public int tallestBillboard(int[] rods) {
final int n = rods.length;
final int sum = Arrays.stream(rods).sum();
// dp[i][j] := the maximum min-height of using rods[0..i) to pile two piles
// that have height difference j
int[][] dp = new int[n + 1][sum + 1];
Arrays.stream(dp).forEach(A -> Arrays.fill(A, -1));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
final int h = rods[i - 1];
for (int j = 0; j <= sum - h; ++j) {
if (dp[i - 1][j] < 0)
continue;
// Don't use rods[i - 1].
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
// Put on the taller pile.
dp[i][j + h] = Math.max(dp[i][j + h], dp[i - 1][j]);
// Put on the shorter pile.
dp[i][Math.abs(j - h)] = Math.max(dp[i][Math.abs(j - h)], dp[i - 1][j] + Math.min(j, h));
}
}
return dp[n][0];
}
} // code provided by PROGIEZ
956. Tallest Billboard LeetCode Solution in Python
class Solution {
public:
int tallestBillboard(vector<int>& rods) {
const int sum = accumulate(rods.begin(), rods.end(), 0);
// dp[i] := the maximum min-height of using rods so far to pile two piles
// that have height difference i
vector<int> dp(sum + 1, -1);
dp[0] = 0;
for (const int h : rods) {
vector<int> prev(dp);
for (int i = 0; i <= sum - h; ++i) {
if (prev[i] < 0)
continue;
// Don't use this rod.
dp[i] = max(dp[i], prev[i]);
// Put on the taller pile.
dp[i + h] = max(dp[i + h], prev[i]);
// Put on the shorter pile.
dp[abs(i - h)] = max(dp[abs(i - h)], prev[i] + min(i, h));
}
}
return dp[0];
}
}; # code by PROGIEZ
