LeetCode Problem 956

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

LeetCode 956, Tallest Billboard

Problem Understanding

This problem asks us to split a collection of steel rods into two groups such that both groups have exactly the same total height. Among all possible equal-height pairs, we want the maximum achievable height.

Each rod can be used in one of three ways:

1. Put it in the left support
2. Put it in the right support
3. Ignore it completely

The important restriction is that a rod cannot be reused. Every rod belongs to at most one support.

The input is an array rods, where each element represents the length of a steel rod. The output is a single integer representing the tallest possible equal height for the two supports.

For example, if we have:

[1,2,3,6]

we can build:

Left  = 1 + 2 + 3 = 6
Right = 6

Both sides have equal height 6, so the answer is 6.

The constraints are very important for determining the correct algorithmic strategy:

• At most 20 rods
• Each rod length is at most 1000
• Total sum of rods is at most 5000

The small number of rods suggests exponential-style reasoning may be possible, but a pure brute-force solution would still be too large. The bounded total sum of 5000 strongly hints that dynamic programming based on sums or differences is likely the intended solution.

Several edge cases are important:

• It may be impossible to form two equal supports, in which case we return 0
• Some rods may need to be ignored entirely
• Multiple different subsets can produce the same difference between supports
• The optimal answer is not necessarily obtained by using all rods
• Very large rods can dominate the search space if handled inefficiently

The key challenge is efficiently exploring all ways to distribute rods while tracking enough information to know whether equal supports can eventually be formed.

Approaches

Brute Force Approach

The brute-force solution considers every possible assignment of every rod.

For each rod, we have three choices:

1. Put it on the left support
2. Put it on the right support
3. Ignore it

With n rods, this creates 3^n possible states.

For every configuration, we compute:

left_sum
right_sum

If the two sums are equal, we update the maximum answer.

This approach is correct because it exhaustively checks every possible distribution of rods, guaranteeing that the optimal equal-height pair will eventually be found.

However, the complexity becomes too large:

3^20 ≈ 3.4 billion

That is far beyond feasible limits.

Optimal Dynamic Programming Approach

The key insight is that we do not need to remember the exact composition of both supports. Instead, we only need to track:

difference = abs(left_sum - right_sum)

and the maximum possible smaller support height associated with that difference.

This dramatically compresses the state space.

Suppose we currently have:

difference = d
smaller_side = s

Then the taller side must be:

s + d

When processing a new rod, we have three options:

1. Ignore the rod
2. Add it to the taller side
3. Add it to the smaller side

Using this representation, many different configurations collapse into the same DP state.

Because the total rod sum is at most 5000, the number of possible differences is bounded, making dynamic programming feasible.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^n)	O(n)	Tries every possible rod assignment
Optimal Dynamic Programming	O(n × sum(rods))	O(sum(rods))	Tracks height differences instead of exact subsets

Algorithm Walkthrough

Dynamic Programming State

We maintain a hash map:

dp[diff] = maximum smaller-side height

Meaning:

• diff is the height difference between the two supports
• The value is the largest achievable height of the smaller support for that difference

For example:

dp[3] = 7

means we can create:

smaller side = 7
larger side  = 10
difference   = 3

Step-by-Step Algorithm

1. Initialize the DP map with:

dp[0] = 0

This means both supports have height 0 initially.

1. Process each rod one at a time.
2. For every existing state (diff, smaller_height) in the current DP map, consider three possibilities.
3. First possibility, ignore the rod.

The existing state already remains valid, so no update is needed.

1. Second possibility, add the rod to the taller support.

If the current difference is diff and we add rod r to the taller side, the new difference becomes:

new_diff = diff + r

The smaller support height does not change.

1. Third possibility, add the rod to the smaller support.

This is the more subtle transition.

Suppose:

larger = smaller + diff

After adding rod r to the smaller side:

new_smaller = smaller + min(diff, r)
new_diff = abs(diff - r)

Why?

If r <= diff, the previously smaller side remains smaller.

If r > diff, the smaller side becomes the new taller side.

The smaller support gains exactly:

min(diff, r)

1. Update the DP map carefully using a copy of the current states.

We cannot modify the map while iterating over it, otherwise new states could incorrectly affect the same iteration.

1. After processing all rods, return:

dp[0]

Difference 0 means both supports are equal.

Why it works

The DP invariant is:

dp[diff] stores the maximum achievable smaller support height
for that exact height difference.

Every rod assignment is represented through the transitions:

• ignore
• add to taller side
• add to smaller side

Thus every valid configuration is explored.

For each difference, we only keep the configuration with the largest smaller support height because any smaller value is strictly worse and can never lead to a better final answer.

When we finally reach:

diff = 0

both supports are equal, and the stored value is the tallest achievable billboard height.

Python Solution

from typing import List

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        dp = {0: 0}

        for rod in rods:
            current = dp.copy()

            for diff, smaller_height in current.items():
                # Add rod to taller side
                new_diff = diff + rod
                dp[new_diff] = max(
                    dp.get(new_diff, 0),
                    smaller_height
                )

                # Add rod to smaller side
                new_diff = abs(diff - rod)
                new_smaller = smaller_height + min(diff, rod)

                dp[new_diff] = max(
                    dp.get(new_diff, 0),
                    new_smaller
                )

        return dp[0]

The implementation begins by initializing the DP map with a single state:

{0: 0}

This represents two supports of equal height zero.

For every rod, we create a snapshot of the current DP states using:

current = dp.copy()

This is crucial because we must only transition from states that existed before processing the current rod.

The first transition adds the rod to the taller support. The difference increases, but the smaller support height stays unchanged.

The second transition adds the rod to the smaller support. The difference changes to:

abs(diff - rod)

and the smaller support height increases by:

min(diff, rod)

For every resulting difference, we keep only the best possible smaller-side height using max.

At the end, dp[0] contains the maximum equal support height.

Go Solution

func tallestBillboard(rods []int) int {
	dp := map[int]int{
		0: 0,
	}

	for _, rod := range rods {
		current := make(map[int]int)

		for k, v := range dp {
			current[k] = v
		}

		for diff, smallerHeight := range current {
			// Add rod to taller side
			newDiff := diff + rod

			if val, exists := dp[newDiff]; !exists || smallerHeight > val {
				dp[newDiff] = smallerHeight
			}

			// Add rod to smaller side
			newDiff = abs(diff - rod)
			newSmaller := smallerHeight + min(diff, rod)

			if val, exists := dp[newDiff]; !exists || newSmaller > val {
				dp[newDiff] = newSmaller
			}
		}
	}

	return dp[0]
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python version.

Since Go maps are reference types, we explicitly create a copied map before iterating. This avoids mutating the DP state during iteration.

Go does not provide built-in abs or min for integers, so helper functions are implemented manually.

Integer overflow is not a concern because the total rod sum is bounded by 5000.

Worked Examples

Example 1

rods = [1,2,3,6]

Initial state:

Difference	Smaller Height
0	0

After rod = 1

Difference	Smaller Height
0	0
1	0

After rod = 2

Difference	Smaller Height
0	0
1	1
2	0
3	0

Explanation:

• Difference 1 with smaller height 1 comes from:

• Left = 2

• Right = 1

After rod = 3

Difference	Smaller Height
0	3
1	2
2	2
3	0
4	1
5	0
6	0

Now we have:

difference = 0
height = 3

using:

1 + 2 = 3

After rod = 6

Difference	Smaller Height
0	6

We achieve:

Left  = 1 + 2 + 3 = 6
Right = 6

Answer:

6

Example 2

rods = [1,2,3,4,5,6]

The algorithm gradually builds states representing all achievable differences.

A critical state eventually becomes:

Difference	Smaller Height
0	10

Corresponding to:

2 + 3 + 5 = 10
4 + 6 = 10

Answer:

10

Example 3

rods = [1,2]

Possible support pairs:

1 vs 2
1 vs 0
2 vs 0

No equal nonzero supports exist.

Final DP state:

Difference	Smaller Height
0	0

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × sum(rods))	Each rod processes all possible differences
Space	O(sum(rods))	DP map stores states for possible differences

The maximum possible difference is bounded by the total rod sum, which is at most 5000.

For each rod, we iterate through all currently reachable differences. Therefore the total complexity is approximately:

O(n × total_sum)

which is efficient for the given constraints.

Test Cases

sol = Solution()

assert sol.tallestBillboard([1,2,3,6]) == 6  # basic example
assert sol.tallestBillboard([1,2,3,4,5,6]) == 10  # larger balanced subsets
assert sol.tallestBillboard([1,2]) == 0  # impossible case

assert sol.tallestBillboard([5,5]) == 5  # simplest valid equal pair
assert sol.tallestBillboard([1000,1000]) == 1000  # large equal rods
assert sol.tallestBillboard([1]) == 0  # single rod cannot form two supports

assert sol.tallestBillboard([1,1,1,1]) == 2  # multiple duplicate rods
assert sol.tallestBillboard([2,3,5]) == 5  # direct equal partition
assert sol.tallestBillboard([1,2,3,4,5,6,7,8]) == 18  # many combinations

assert sol.tallestBillboard([7,7,7,7,7,7]) == 21  # repeated large values
assert sol.tallestBillboard([1,2,4,8,16]) == 0  # no equal partition possible
assert sol.tallestBillboard([3,4,3,3,2]) == 6  # requires skipping rods

Test	Why
[1,2,3,6]	Validates the main example
[1,2,3,4,5,6]	Tests larger optimal grouping
[1,2]	Ensures impossible cases return 0
[5,5]	Smallest nontrivial equal partition
[1000,1000]	Tests upper rod values
[1]	Single-element edge case
[1,1,1,1]	Tests duplicate handling
[2,3,5]	Exact partition match
[1,2,3,4,5,6,7,8]	Many overlapping DP states
[7,7,7,7,7,7]	Large repeated values
[1,2,4,8,16]	No equal partition despite many rods
[3,4,3,3,2]	Verifies skipping rods is handled correctly

Edge Cases

Impossible Construction

Inputs like:

[1,2]

cannot form two equal supports.

A naive implementation might incorrectly return the largest single rod or accidentally allow reusing rods. The DP solution avoids this because only states with difference = 0 contribute to the final answer.

Duplicate Rod Lengths

Inputs such as:

[1,1,1,1]

contain repeated values.

Some implementations accidentally overwrite states incorrectly when duplicates appear. Using a copied snapshot of the DP map ensures each rod is processed exactly once per iteration.

Rods That Must Be Ignored

Consider:

[3,4,3,3,2]

The optimal solution does not necessarily use every rod.

A greedy approach that always uses all rods may fail. The DP formulation naturally supports ignoring rods because every state can simply persist unchanged during an iteration.

Large Difference Transitions

When adding a rod to the smaller side, the smaller side may become the larger side.

For example:

difference = 2
rod = 5

The new difference becomes:

abs(2 - 5) = 3

Incorrect implementations often mishandle this reversal. Using:

abs(diff - rod)

correctly handles both scenarios.