Tallest Billboard - Practice Coding Problems

Tallest Billboard - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: rods = [1,2,3,6]

› Output: 6

💡 Note: We can build supports of equal height 6: Left support uses rods [1,2,3] with total length 6, Right support uses rod [6] with length 6

Example 2 — No Solution

$ Input: rods = [1,2,3,4]

› Output: 0

💡 Note: No way to split rods [1,2,3,4] into two equal-height supports. Total sum is 10, so we need each support to have height 5, but no subset sums to 5

Example 3 — Multiple Solutions

$ Input: rods = [1,2]

› Output: 0

💡 Note: Only one rod per support would give heights 1 and 2 (not equal). Cannot make equal heights with these rods

Constraints

1 ≤ rods.length ≤ 20
1 ≤ rods[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Collection of rods with different lengths [1,2,3,6]

Process

Split rods into two groups to form equal-height supports

Output

Maximum possible height when both supports are equal

Key Takeaway

🎯 Key Insight: Track height differences between supports, not absolute heights, to reduce the state space in dynamic programming.

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is to track the height difference between left and right supports rather than absolute heights. Best approach uses dynamic programming to build a table of all possible height differences we can achieve. Time: O(n × S), Space: O(S) where S is the sum of all rod lengths.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(3ⁿ)	O(n)	Try every possible assignment of rods to left support, right support, or unused
Memoization - Cache Results	O(n × S)	O(n × S)	Add memoization to brute force to avoid recalculating same subproblems
Dynamic Programming - Bottom Up	O(n × S)	O(n × S)	Use 2D DP table to track all possible height differences we can achieve

Brute Force - Try All Combinations — Algorithm Steps

Step 1: For each rod, recursively try 3 options: left support, right support, or unused
Step 2: Keep track of left height and right height at each step
Step 3: When all rods processed, return left height if left equals right, else 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Decision Tree

Each rod has 3 choices: left, right, or unused

Recursive Exploration

Explore all 3^n combinations

Check Balance

Return height if left equals right

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int backtrack(int* rods, int size, int index, int left, int right) {
    if (index == size) {
        return left == right ? left : 0;
    }
    
    int rod = rods[index];
    // Try not using this rod
    int result = backtrack(rods, size, index + 1, left, right);
    // Try adding to left support
    int temp = backtrack(rods, size, index + 1, left + rod, right);
    if (temp > result) result = temp;
    // Try adding to right support
    temp = backtrack(rods, size, index + 1, left, right + rod);
    if (temp > result) result = temp;
    
    return result;
}

int solution(int* rods, int size) {
    return backtrack(rods, size, 0, 0, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int rods[20];
    int size = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        rods[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(rods, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3ⁿ)

For each of n rods, we have 3 choices, leading to 3^n combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth is at most n levels deep

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~45 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler