Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Burst Balloons
• Main tags: Array, Dynamic Programming

What the problem is really asking

This problem looks like a simulation question, but the hard part is not the simulation itself. The hard part is that every burst changes the future.

When balloon i is burst, the coins earned are:

left_neighbor * nums[i] * right_neighbor

The trouble is that the left and right neighbors are not fixed. They depend on which balloons were already removed earlier. So the value of bursting a balloon is not a property of that balloon alone. It depends on the entire order.

That is why simple greedy ideas are unreliable here. Bursting the largest number first, or taking the biggest immediate score, can destroy a much better setup later.

The real problem is:

find a bursting order that maximizes total coins when each choice changes the boundaries for future choices.

Why the forward view feels messy

If a person tries to solve this from the beginning of the sequence forward, every decision seems to create branching chaos:

• bursting one balloon changes two future neighbor relationships
• that changes the value of later bursts
• the same balloon can be worth very different amounts depending on when it is removed

Brute force tries every order, which is essentially factorial time and far too slow.

The interview breakthrough is to stop asking:

“Which balloon should be burst first?”

and start asking:

“Which balloon is burst last inside a subproblem?”

That reversal turns a hard dependency problem into a clean interval DP.

The key insight: choose the last balloon in an interval

Suppose the current interval is bounded by two balloons that are still present at positions left and right. Focus only on the balloons strictly between them.

If balloon mid is the last balloon burst in that open interval, then something very nice happens:

• every balloon between left and mid has already been removed
• every balloon between mid and right has already been removed
• when mid is finally burst, its neighbors are guaranteed to be exactly left and right

So the last burst inside that interval always contributes:

values[left] * values[mid] * values[right]

That is the part that becomes predictable.

Even better, once mid is chosen as the last balloon in (left, right), the work on the left side and right side becomes independent:

• best coins from bursting (left, mid)
• best coins from bursting (mid, right)
• coins from bursting mid last

That is exactly the structure dynamic programming needs.

How to derive the interval DP

The standard setup is:

1. Add a virtual balloon with value 1 to both ends of the array.
2. Let dp[left][right] mean the maximum coins obtainable by bursting all balloons strictly between left and right.
3. Try every possible mid in that interval as the last balloon to burst.

With that definition, the recurrence is:

dp[left][right] =
    max(
        dp[left][mid]
        + dp[mid][right]
        + values[left] * values[mid] * values[right]
    )

for every mid where left < mid < right.

The reason the recurrence works is simple:

• dp[left][mid] already represents the best way to clear the left subinterval
• dp[mid][right] already represents the best way to clear the right subinterval
• after both sides are empty, bursting mid last produces a fixed score because its neighbors are now known

That fixed-boundary property is the entire trick.

Why the sentinel 1s matter

The first and last real balloons do not naturally have two real neighbors. Adding 1 on both ends removes all edge-case handling.

After that transformation:

• every real balloon eventually gets multiplied by two boundary values
• the full problem becomes “burst everything inside the open interval (0, n - 1)”
• the recurrence works uniformly for every interval

This is a standard DP move: change the representation until the recurrence becomes clean.

Order of computation

Because dp[left][right] depends on smaller intervals inside it, the table must be filled by increasing interval width.

That means:

• shortest open intervals first
• wider intervals later
• final answer at dp[0][last_index]

For n real balloons, there are O(n^2) interval states. Each state tries O(n) choices for the last balloon, so the total complexity is:

• Time: O(n^3)
• Space: O(n^2)

That is the standard optimal interview answer for this problem.

How to explain this in an interview

A strong explanation usually sounds like this:

First, acknowledge that greedy is not trustworthy because bursting changes future neighbors. Then reframe the problem around the last balloon burst in an interval, because the last balloon sees fixed boundaries. Once that happens, the interval splits into two independent subproblems, which gives a natural recurrence. Add sentinel 1s so boundary handling disappears, define dp[left][right] over open intervals, and fill the table from short intervals to long ones.

If that reasoning is explained clearly, the code feels much less magical.

Python solution

The implementation below uses bottom-up interval DP. The helper functions keep the LeetCode entry point small while making the recurrence easy to inspect.

from typing import List


def build_augmented_values(balloon_values: List[int]) -> List[int]:
    """
    Add the virtual boundary balloons so every real balloon always has
    a left and right multiplier inside the DP recurrence.
    """
    return [1, *balloon_values, 1]


def compute_max_coins_by_interval(augmented_values: List[int]) -> List[List[int]]:
    """
    Build a DP table where dp[left][right] is the maximum number of coins
    obtainable by bursting every balloon strictly between left and right.
    """
    total_positions = len(augmented_values)
    max_coins_by_interval = [[0] * total_positions for _ in range(total_positions)]

    # Grow open intervals from small to large so all dependent subproblems
    # are already solved when the current interval is evaluated.
    for interval_width in range(2, total_positions):
        for left_boundary in range(total_positions - interval_width):
            right_boundary = left_boundary + interval_width
            best_coins_for_interval = 0

            for last_balloon_index in range(left_boundary + 1, right_boundary):
                coins_from_last_burst = (
                    augmented_values[left_boundary]
                    * augmented_values[last_balloon_index]
                    * augmented_values[right_boundary]
                )
                total_coins_if_last_burst_is_here = (
                    max_coins_by_interval[left_boundary][last_balloon_index]
                    + max_coins_by_interval[last_balloon_index][right_boundary]
                    + coins_from_last_burst
                )
                best_coins_for_interval = max(
                    best_coins_for_interval,
                    total_coins_if_last_burst_is_here,
                )

            max_coins_by_interval[left_boundary][right_boundary] = best_coins_for_interval

    return max_coins_by_interval


def max_coins_from_balloons(balloon_values: List[int]) -> int:
    """Return the maximum coins obtainable for the full balloon array."""
    augmented_values = build_augmented_values(balloon_values)
    max_coins_by_interval = compute_max_coins_by_interval(augmented_values)
    return max_coins_by_interval[0][-1]


class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        """LeetCode entry point."""
        return max_coins_from_balloons(nums)

Interview follow-ups

Can this be written as top-down memoization instead of bottom-up DP?

Yes. The same state definition works perfectly in a recursive solution: define a function like solve(left, right) that returns the best score from bursting everything strictly inside that interval, and memoize the result. The recurrence is identical, because the core logic is still “try every possible last balloon in the interval.” This version is often easier to derive because it mirrors the mathematical idea directly. The tradeoff is that the bottom-up version makes the computation order explicit and avoids recursion-depth concerns, while the top-down version can feel more natural during discovery. In both cases, the complexity remains O(n^3) time and O(n^2) space because the state space and transitions are unchanged.

How would you return one optimal bursting order, not just the maximum score?

Store one extra piece of information for each interval: which mid produced the best value for dp[left][right]. After the DP table is complete, recursively reconstruct the answer by following those saved choices. If mid is the last balloon in (left, right), then the final order for that interval is: first reconstruct the optimal order for (left, mid), then reconstruct the optimal order for (mid, right), and finally place mid at the end. This works because the recurrence already decomposes the optimal solution into independent left and right subproblems plus the final burst. The asymptotic time to compute the score does not change, and the extra space is still O(n^2) because the saved choice table is the same size as the DP table.

Can the algorithm be improved below O(n^3) time?

For interview purposes, O(n^3) is the expected optimal answer. There are O(n^2) interval states, and each state must consider which balloon is burst last, which creates the extra factor of n. There is no standard interview optimization that reliably removes that factor while preserving correctness for the full problem. A person can sometimes reduce constant factors in practice, such as by skipping obviously empty work or trimming some preprocessing cases, but the worst-case complexity remains cubic. The important point in an interview is to recognize the interval-DP structure quickly and deliver the correct O(n^3) solution, not to chase a nonexistent simple sub-cubic trick.

Why is “last balloon in the interval” the right viewpoint, but “first balloon in the interval” is not?

If a balloon is chosen as the first one to burst, its future neighbors are unknown because the rest of the interval has not been resolved yet. That means the remaining subproblems are still entangled, which makes the recurrence messy. If a balloon is chosen as the last one to burst, the interval boundaries are fixed at that moment, so its score contribution becomes deterministic. That determinism is exactly what allows the left and right sides to separate into independent subproblems. In other words, the DP works not because “last” is somehow magical, but because “last” is the moment when the neighbor relationship becomes stable. That is the conceptual reason this problem is a classic interval-DP question.