Burst Balloons: A Dynamic Programming Interview Walkthrough
- 4 days ago
- 12 min read
Interviewers reach for the Burst Balloons dynamic programming problem because it tests a specific mental move: when forward reasoning fails, can you flip the question and reason backward? Candidates pass when they can make that flip and then define a clean interval state; candidates who can't do that tend to spiral.
In real life, interval DP - the technique this problem teaches - shows up in matrix chain multiplication (where to place parentheses to minimize multiplication cost), optimal binary search tree construction, RNA secondary structure prediction in bioinformatics, and any optimization problem where the order of combining adjacent subproblems determines the total cost. The key trick of this problem type - "pick the last action instead of the first" - is a tool you'll use again and again.
Problem Statement
You are given an array of integers nums representing balloons, where nums[i] is the number printed on the i-th balloon.
When you burst a balloon at index i, you gain nums[left] * nums[i] * nums[right] coins, where left and right are the nearest unburst balloons to the left and right of i. If there is no balloon on either side, treat it as having value 1.
Return the maximum number of coins you can collect by bursting all the balloons.
Example:
nums = [3, 1, 5, 8]
result = 167.
1. Clarify Requirements Before Jumping Into Code
Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would affect our approach.
Input: an integer array nums.
Output: an integer - the maximum coins collected after bursting every balloon.
Details to clarify:
Do we have to burst every balloon? Yes.
Does the order matter? Yes - that's the whole point. The same balloon yields different coins depending on which balloons are still adjacent when it bursts.
What happens at the boundaries? When a balloon at the edge bursts, treat the missing neighbor as having value 1.
Can the array be empty? Assume non-empty unless told otherwise. We'd handle empty as a return-0 case.
Can nums[i] be zero? Yes - and that creates an interesting case where bursting that balloon yields zero coins regardless of order.
The thing to flag is that the neighbors change as balloons disappear. That dynamic adjacency is what makes the problem hard, and it's the reason greedy heuristics ("burst the highest-value balloon first") don't work.
2. Identify the Category of the Question
A few signals jump out:
We're optimizing over an ordering of operations.
The cost of each operation depends on what's already happened.
The structure is one-dimensional (a line of balloons).
Subranges of the line are natural subproblems - once a subrange is "done," it doesn't interact with the rest.
That last point is the giveaway. When subranges form clean subproblems, we're in interval DP territory. The same family includes Matrix Chain Multiplication, Optimal BST, and Stone Game variants.
3. Brute Force Solution
As always, we start with the brute force. The most direct approach is to try every possible order of bursting balloons and track the maximum coins.
maxCoins(remaining):
if remaining is empty: return 0
best = 0
for each balloon i in remaining:
coins = compute coins from bursting i
best = max(best, coins + maxCoins(remaining without i))
return bestThat's O(n!) time since we would be checking every permutation of n balloons. Even with memoization, the number of potential states we would have to track is "subsets of remaining balloons," which is 2^n. Both are completely infeasible.
But we can learn something useful from the brute force solution: the final result depends on which balloons are still adjacent when we pop a particular ballon. That's the constraint we need to find a smarter way to optimize.
4. Brainstorm More Solutions
Step 1: Try the natural recursion - pick the first balloon to burst
Let's try solving this with recursion. The obvious approach is: at each step, pick which balloon to burst next, and then recurse on what remains.
To see how that might work in practice, let's try an example: [3, 1, 5, 8].
If I burst the 1 balloon first, I gain 3 * 1 * 5 = 15 coins, and I'm left with [3, 5, 8]. So then I'd want to recurse on [3, 5, 8].
But what if I burst the 5 ballon first instead? I gain 1* 5 * 8 = 40 coins, and I'm left with [3, 1, 8].
Those are different subproblems! That makes our recursion much more complicated because it means our recursion can't just care about "the remaining balloons", it has to care about "the remaining balloons in their original positions." The next time we burst a ballon, our coin value is going to depend on which neighbors got removed, and that means there are a lot of different subsets that we could end up with here - 2^n of them in total. That's way too many distinct states for a DP table to hold.
To make matters worse, even if we could enumerate all those states, knowing which balloons remain still isn't enough information. To compute the coins from the next burst, I need to know who each remaining balloon's neighbors are right now. And the current neighbors depend on the order I burst things in, not just what I've burst. Two different burst orders can leave me with the same set of remaining balloons but different neighbor relationships, which means the same "state" can produce different answers.
Both problems have the same root cause: the framing we chose here (choose a balloon to burst, then recurse) means that our answer depends on the history of bursts, not just the current configuration. DP only works when the subproblem is self-contained, i.e. when the answer to solve(X) is the same no matter how we got to X. That property is broken here.
What we need is a framing where each balloon's neighbors are determined by the subproblem itself, not by history. That's a strong constraint, but it points us in a specific direction.
Step 2: Flip the question - pick the last balloon to burst
A key piece of advice when you are tackling a recursion or DP style problem (or really any problem that involves processing a set): if you get stuck, try flipping the question you are asking. In this case, instead of asking "which balloon do I burst first?", let's ask "which balloon do I burst last?"
Why does that help? Because when we start with the last balloon, everything else has already been popped! And that means we know exactly what the neighbors are: they're the walls. The two virtual 1s padding the array.
Let's look at an example. Suppose I'm looking at the original array [3, 1, 5, 8], and I decide that the 5 will be the very last balloon I burst out of all of them. That means by the time I'm finally bursting the 5, all the other balloons - 3, 1, and 8 - are already gone.
So when the 5 finally pops, what are its neighbors? The only things left next to the 5 are whatever sits at the very edges of the original range. That means our coins from bursting the 5 last are 1 * 5 * 1 = 5 coins.
Let's formalize this logic. Let's say we have any range of balloons defined by two boundary positions left and right (where left and right are themselves not burst - they're just the "walls"). We'll call the last balloon inside this range k. By the time we burst k, every other balloon between left and right is already gone, which means k's neighbors at that moment must be left and right. So, the coins from bursting k last are exactly nums[left] * nums[k] * nums[right].
Now what about the recursion? Well, once we've decided k goes last, we can treat the balloons to the left and right of k as two completely independent subproblems. The balloons in (left, k) get burst in some order among themselves, and the balloons in (k, right) get burst in some order among themselves. We know they never interact because k is sitting between them like a wall, and k itself is the very last thing that gets popped, so we won't touch it.
And that's the recursion we needed: a range, a last balloon, and two smaller ranges that don't talk to each other.
Step 3: Define the state and transition
Let dp[left][right] be the maximum coins obtainable by bursting all balloons strictly between indices left and right (exclusive on both ends). The boundary indices left and right aren't burst as part of this subproblem, they're just the walls that define it.
For the transition, we try every k strictly between left and right as the last balloon to burst:
dp[left][right] = max over k in (left, right) of:
dp[left][k] + dp[k][right] + nums[left] * nums[k] * nums[right]The first term covers all the bursts that happen in the left subrange (with left and k as walls).
The second covers the right subrange (with k and right as walls).
The third is the coins from bursting k last, which we now know exactly because its neighbors are fixed at left and right.
Now let's make sure we understand the time and space complexity of our solution.
There are two indices in the state, left and right, each ranging across the padded array of size n + 2. That gives us O(n²) possible (left, right) pairs, which is both the number of subproblems we solve and the size of the memo table, giving us O(n²) space.
For each subproblem we try every k between left and right as the last balloon to burst, which is O(n) work per state, so the total time is O(n²) states × O(n) work per state = O(n³).
Step 4: Pad the array to handle boundaries
The problem says to treat missing neighbors as having value 1. There's one place where that's going to be an issue - at the ends of the array. But the original array doesn't have balloons at indices -1 or n. We could write special-case logic to handle the edges, but another way to address this is to pad the array with 1s on both ends:
arr = [1] + nums + [1]Now the entire DP runs over arr instead of nums, and the boundaries take care of themselves. The full answer is dp[0][n+1] - the maximum coins obtainable by bursting everything between the two padding 1s, which is everything in the original array.
This kind of padding trick is worth remembering. Whenever a problem has "imaginary" boundary values, padding the input is almost always cleaner than special-casing the edges.
Step 5: From recursion to memoization
As usual, the recursive solution can be optimized using memoization to save us from recalculating the same values. It doesn't change our space and time complexity, but is still an optimization worth talking through in an interview setting.
public int maxCoins(int[] nums) {
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1;
for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
Integer[][] memo = new Integer[n + 2][n + 2];
return solve(arr, 0, n + 1, memo);
}
private int solve(int[] arr, int left, int right, Integer[][] memo) {
if (right - left < 2) return 0; // no balloons between left and right
if (memo[left][right] != null) return memo[left][right];
int best = 0;
for (int k = left + 1; k < right; k++) {
int coins = arr[left] * arr[k] * arr[right]
+ solve(arr, left, k, memo)
+ solve(arr, k, right, memo);
best = Math.max(best, coins);
}
return memo[left][right] = best;
}Step 6: From memoization to bottom-up interval DP
Memoization works, but the recursion adds function-call overhead and a stack depth that scales with n. DP can alleviate that issue, but in this case, we need to be careful about which order we fill the table.
To figure out how to convert our recursion to a DP solution, we start by looking at the dependency structure. To compute dp[left][right], we need dp[left][k] and dp[k][right] for various k between them. Both of those subproblems span a smaller interval than (left, right). So the rule is: every cell I compute has to come after every smaller-interval cell that feeds it.
This tells us that we need an outer loop of increasing interval size. If I iterate by interval length, starting from the smallest possible interval and growing outward, then every dependency is guaranteed to be filled before I need it. Length is what I'm growing, so length is the outer variable.
Once I've fixed an interval length, we can work compute the value of every cell of that length - that means sliding the interval across the array. So that gives us a second loop that iterates left from 0 to the rightmost valid starting position, and we can identify right as the last ballon in our current interval, right = left + length.
The innermost loop is just the recurrence itself. For the current (left, right), I try every k between them as the last balloon to burst and take the maximum.
public int maxCoins(int[] nums) {
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = arr[n + 1] = 1;
for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
int size = n + 2;
int[][] dp = new int[size][size];
// length is the distance between left and right boundaries
for (int length = 2; length < size; length++) {
for (int left = 0; left + length < size; left++) {
int right = left + length;
for (int k = left + 1; k < right; k++) {
dp[left][right] = Math.max(
dp[left][right],
dp[left][k] + dp[k][right] + arr[left] * arr[k] * arr[right]
);
}
}
}
return dp[0][size - 1];
}Same O(n³) time, same O(n²) space, but no recursion stack and the order of computation is explicit. This is the version you should strive to reach at the whiteboard.
Tip 1: The "length-first" iteration pattern is the standard idiom for interval DP. Whenever you see a problem where dp[left][right] depends on smaller intervals inside (left, right), that outer loop is what makes the bottom-up version work.
Tip 2: This progression - brute force → recursion + memoization → bottom-up interval DP - is the same pattern we keep seeing in DP problems. Each step removes a specific inefficiency. The thing that's unique to this problem is the conceptual flip in Step 2: the recursion only became tractable once we reframed the choice as "which balloon goes last." Without that flip, no amount of caching saves us.
5. Discuss Trade-Offs Between Solutions
Approach | Time | Space | When I'd use it |
Brute force (try every order) | O(n!) | O(n) stack | Never — but worth mentioning to frame the problem |
Recursion + memoization | O(n³) | O(n²) | Easiest to write if I'm short on time and the recurrence is fresh |
Bottom-up interval DP | O(n³) | O(n²) | My default interview answer — clean and easy to walk through |
Unlike some other DP problems, there's no obvious O(n) space optimization here. The dependencies aren't confined to a single previous row - dp[left][right] can read any cell with smaller interval length, which can come from anywhere in the table.
6. Pseudocode
arr = [1] + nums + [1]
size = length of arr
dp = 2D array of size x size, all zeros
for length from 2 to size - 1:
for left from 0 to size - 1 - length:
right = left + length
for k from left + 1 to right - 1:
dp[left][right] = max(
dp[left][right],
dp[left][k] + dp[k][right] + arr[left] * arr[k] * arr[right]
)
return dp[0][size - 1]7. Edge Cases
Things to verify before claiming we're done:
Empty array → return 0.
Single balloon → padding makes the array [1, nums[0], 1]. The only choice is to burst nums[0], yielding 1 * nums[0] * 1 = nums[0]. ✓
Two balloons → small interval, three choices of k, recurrence handles it.
Balloons with value 0 → bursting a 0 yields 0 coins regardless of neighbors, but the surrounding balloons still get their full contribution from their other neighbors. The recurrence handles this naturally.
Identical balloon values → no special behavior needed.
The padding trick eliminates almost all the boundary bugs that plague unpadded versions of this problem.
8. Full Code
public class BurstBalloons {
public static int maxCoins(int[] nums) {
int n = nums.length;
int[] arr = new int[n + 2];
arr[0] = 1;
arr[n + 1] = 1;
for (int i = 0; i < n; i++) {
arr[i + 1] = nums[i];
}
int size = n + 2;
int[][] dp = new int[size][size];
for (int length = 2; length < size; length++) {
for (int left = 0; left + length < size; left++) {
int right = left + length;
for (int k = left + 1; k < right; k++) {
dp[left][right] = Math.max(
dp[left][right],
dp[left][k] + dp[k][right] + arr[left] * arr[k] * arr[right]
);
}
}
}
return dp[0][size - 1];
}
}9. Test the Code
System.out.println(maxCoins(new int[]{3, 1, 5, 8})); // 167
System.out.println(maxCoins(new int[]{1, 5})); // 10
System.out.println(maxCoins(new int[]{7})); // 7
System.out.println(maxCoins(new int[]{0, 1})); // 1
System.out.println(maxCoins(new int[]{9, 76, 64, 21})); // larger caseThese hit the meaningful cases: the canonical example, small inputs, single balloons, and balloons with zeros.
10. Key Lessons
DP only works when the subproblem is self-contained, i.e. when the answer to solve(X) is the same no matter how we got to X.
When the natural framing of a problem ("which choice do I make first?") leads to an unbounded state, try flipping it ("which choice do I make last?"). Sometimes the reversed framing has a clean recursive structure that the forward one lacks.
Interval DP is the right tool whenever subranges of a sequence form clean subproblems. The state is dp[left][right], and the transition almost always involves choosing a pivot inside the range.
Bottom-up interval DP is filled in order of increasing interval length. That's the iteration order that guarantees every subproblem's dependencies are already computed.
Padding the input with sentinel values (here, the boundary 1s) is almost always cleaner than special-casing the edges of the table. Whenever a problem has imaginary or default boundary values, reach for padding first.
Greedy approaches fail on this problem because the value of a burst depends on what's already happened. Whenever the cost of an action depends on prior actions, be skeptical of greedy and look for a DP state that captures the relevant history.
The thing that makes Burst Balloons click isn't the recurrence, it's the willingness to abandon the natural "what do I do first" framing and ask "what do I do last" instead. Once you make that flip, every other interval DP problem starts to look familiar.
Good Luck and Happy Coding!
Comments