Scale Engineer

Tallest Billboard

Hard
#0910Time: O(N * S), where N is the number of rods and S is the total sum. Each state `(index, diff)` is computed once.Space: O(N * S), where N is the number of rods and S is the total sum of rod lengths. This is for the memoization table.1 company
Patterns
Dynamic Programming
Data structures
Array
Companies
Atlassian

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses recursion to explore all possibilities of assigning each rod to one of two supports or discarding it. This is a 3-way choice for each rod. A naive recursion would be O(3^N), which is too slow. We can significantly optimize it by using memoization to store and reuse the results of subproblems, identified by the current rod index and the difference in height between the two supports.

Algorithm

  • Create a memoization table memo[n][2*totalSum + 1], initialized with a sentinel value to store results of subproblems.
  • Implement a recursive function solve(rods, index, diff).
  • Base Case: If index reaches the end of the rods array (index == rods.length), return 0 if diff == 0 (indicating balanced supports), otherwise return a very large negative number to signify an invalid path.
  • Memoization Check: Before computing, check if memo[index][diff + offset] already has a computed value. If so, return it.
  • Recursive Step: Explore the three choices for rods[index]:
    1. Discard: solve(index + 1, diff).
    2. Add to support 2: solve(index + 1, diff - rods[index]).
    3. Add to support 1: rods[index] + solve(index + 1, diff + rods[index]).
  • Store the maximum of these three results in the memoization table and return it.
  • The initial call to start the process is solve(rods, 0, 0).

Walkthrough

The core idea is to build the two supports recursively. We define a function, say solve(index, diff), which returns the maximum possible height of the first support we can form using rods from index to the end, given that the current difference in heights (support1 - support2) is diff.

The goal is to find the maximum height where the final difference is 0. The value returned by solve(0, 0) will be the answer.

To avoid recomputing results for the same state (index, diff), we use a 2D array memo for memoization. The difference diff can be negative, so we use an offset (equal to the total sum of all rods) to map it to a non-negative array index. The maximum possible sum is 5000, so the difference can range from -5000 to 5000.

The base case for the recursion is when index reaches the end of the rods array. If diff is 0, it means we have successfully formed two supports of equal height, and we return 0. If diff is not 0, this path is invalid, so we return a very small number to indicate failure.

In the recursive step, we explore the three choices and take the maximum value returned from the recursive calls.

class Solution {    Integer[][] memo;    int n;    int[] rods;    int totalSum;     public int tallestBillboard(int[] rods) {        this.n = rods.length;        this.rods = rods;        this.totalSum = 0;        for (int rod : rods) {            totalSum += rod;        }        // memo[index][diff + totalSum]        memo = new Integer[n][2 * totalSum + 1];        return solve(0, 0);    }     private int solve(int index, int diff) {        if (index == n) {            return diff == 0 ? 0 : -5001; // A value smaller than any possible valid height        }        // Use totalSum as offset for diff        if (memo[index][diff + totalSum] != null) {            return memo[index][diff + totalSum];        }         // Option 1: Discard rods[index]        int res = solve(index + 1, diff);         // Option 2: Add rods[index] to the second support        res = Math.max(res, solve(index + 1, diff - rods[index]));         // Option 3: Add rods[index] to the first support        res = Math.max(res, rods[index] + solve(index + 1, diff + rods[index]));         return memo[index][diff + totalSum] = res;    }}

Complexity

Time

O(N * S), where N is the number of rods and S is the total sum. Each state `(index, diff)` is computed once.

Space

O(N * S), where N is the number of rods and S is the total sum of rod lengths. This is for the memoization table.

Trade-offs

Pros

  • Conceptually straightforward, as it directly models the decision process.

  • Guaranteed to find the optimal solution.

Cons

  • The space complexity of O(N * S) can be large if the total sum of rods is high.

  • For deep recursion stacks (large N), it might lead to a StackOverflowError, although N is small here.

Solutions

class Solution {public  int tallestBillboard(int[] rods) {    int n = rods.length;    int s = 0;    for (int x : rods) {      s += x;    }    int[][] f = new int[n + 1][s + 1];    for (var e : f) {      Arrays.fill(e, -(1 << 30));    }    f[0][0] = 0;    for (int i = 1, t = 0; i <= n; ++i) {      int x = rods[i - 1];      t += x;      for (int j = 0; j <= t; ++j) {        f[i][j] = f[i - 1][j];        if (j >= x) {          f[i][j] = Math.max(f[i][j], f[i - 1][j - x]);        }        if (j + x <= t) {          f[i][j] = Math.max(f[i][j], f[i - 1][j + x] + x);        }        if (j < x) {          f[i][j] = Math.max(f[i][j], f[i - 1][x - j] + x - j);        }      }    }    return f[n][0];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem