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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

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.

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

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

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

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

Not Sure What to Study? Take the 2-min Quiz：

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayMerge sort does not use divide and conquer

I don’t know

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which two pointer technique does Quick Sort use?

Fast-slow pointersTwo pointers moving in opposite directionSliding windowPrefix sum

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

956. Tallest Billboard

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings