Burst Balloons
Problem Statement
You are given n balloons, indexed from 0 to n - 1. Each balloon has a number on it. When you burst balloon i, you earn nums[left] * nums[i] * nums[right] coins, where left and right are the nearest still-unburst balloons on each side. If there is no balloon on one side, treat that boundary value as 1. Return the maximum coins you can collect by bursting all balloons.
Input
An integer array nums, where nums[i] is the value written on the i-th balloon.
Output
An integer: the maximum number of coins obtainable after bursting every balloon.
Constraints
- •
1 <= nums.length <= 300 - •
0 <= nums[i] <= 100
Examples
Example 1
nums = [3,1,5,8]
167Example 2
nums = [1,5]
10Example 3
nums = [9]
9Learning Objectives
- Recognise why choosing the first balloon is hard but choosing the last balloon creates independent subproblems.
- Model an interval DP with fixed outside boundaries and open intervals inside them.
- Fill interval states by increasing width so every smaller subinterval is already solved.
- Use padding with boundary value 1 to remove edge-case logic from the recurrence.
Intuition
The trap is thinking forward. If you decide which balloon to burst first, its neighbours change immediately, and the value of every later choice depends on a shifting array. That makes the subproblems feel tangled.
Turn the timeline around. For any interval, ask which balloon is burst last inside that interval. At that exact moment, every balloon between the two interval boundaries is already gone, so the last balloon sees the same two fixed neighbours: the left boundary and the right boundary. That means its final gain is known: values[left] * values[last] * values[right].
Now the work on the left side and the work on the right side are independent. Bursting balloons strictly between left and last can never affect balloons strictly between last and right, because last remains in place until the end and acts as a wall between them. This is the non-obvious modelling move that makes the DP possible.
Common mistakes
- ×Choosing the first balloon in the recurrence, which leaves changing neighbours and does not split cleanly.
- ×Defining closed intervals over original indices and then struggling with missing boundary values.
- ×Forgetting that **dp[left][right]** covers balloons strictly between the boundaries, not including the boundaries themselves.
- ×Filling intervals in the wrong order before smaller left and right intervals are available.
- ×Multiplying by original adjacent indices instead of the fixed interval boundaries after padding.
State Definition
Pad the input into values by adding 1 at the beginning and end. Let dp[left][right] be the maximum coins obtainable by bursting every balloon strictly between boundary indices left and right in values. The boundaries themselves are not burst inside this subproblem. The final answer is dp[0][n + 1].
State Transition
Choose the balloon last that will be the final burst inside (left, right). Everything left of last and right of last has already been burst, so the gain from this final burst is fixed by the two boundaries:
dp[left][right] = max over left < last < right of dp[left][last] + values[left] * values[last] * values[right] + dp[last][right]
Base case: if there is no balloon strictly between left and right, then dp[left][right] = 0. Fill states by increasing gap right - left, starting from gap 2.
Solutions
Solution: Bottom-up interval DP
Use this when the score of an action depends on its current neighbours. Reframing around the last action often freezes those neighbours and turns the problem into interval DP.
Pad the array with virtual boundary value 1, then solve every open interval. For each interval, try every possible last balloon and combine the best result from the left subinterval, the final burst gain, and the best result from the right subinterval.
Step-by-step
- Copy nums into values[1..n] and set values[0] and values[n + 1] to 1.
- Create a square DP table where empty intervals default to 0.
- Iterate gap from 2 through n + 1, because a gap smaller than 2 contains no real balloon.
- For each boundary pair left and right, try every last index strictly between them.
- Store the best combination of left interval, final burst, and right interval. Return dp[0][n + 1].
O(n^3)
O(n^2)
There are O(n^2) intervals and each interval tries O(n) choices for the last balloon.
Java implementation
Dry Run
Sample input
nums = [3,1,5,8], so values = [1,3,1,5,8,1]. The table stores open intervals between boundary indices.
| gap | subproblem | last choice | best formula | dp value |
|---|---|---|---|---|
| 2 | dp[0][2] | last = 1, value 3 | 0 + 1 * 3 * 1 + 0 | 3 |
| 2 | dp[2][4] | last = 3, value 5 | 0 + 1 * 5 * 8 + 0 | 40 |
| 3 | dp[1][4] | last = 3, value 5 | 15 + 3 * 5 * 8 + 0 | 135 |
| 3 | dp[2][5] | last = 4, value 8 | 40 + 1 * 8 * 1 + 0 | 48 |
| 4 | dp[0][4] | last = 1, value 3 | 0 + 1 * 3 * 8 + 135 | 159 |
| 5 | dp[0][5] | last = 4, value 8 | 159 + 1 * 8 * 1 + 0 | 167 |
The final row represents the whole padded interval. Choosing value 8 as the last real balloon combines the best way to clear everything before it with the final boundary gain, giving 167.
Complexity Analysis
The O(n^3) interval DP is the expected optimal approach for the given constraints. The important optimisation is conceptual: pick the last balloon so the subintervals become independent.
Bottom-up interval DP
O(n^3)
O(n^2)
There are O(n^2) intervals and each interval tries O(n) choices for the last balloon.
Interview Tips
Say explicitly that a forward order is hard because neighbours mutate. Then present the reverse-time insight: in a fixed interval, the last balloon sees fixed boundaries, so the left and right intervals no longer interact. That sentence is usually what the interviewer is testing for.
Likely follow-ups
- Can you reconstruct one optimal burst order, not just the maximum score?
- How would the recurrence change if boundary balloons had custom values instead of 1?
- What other interval problems become easier when you choose the last action rather than the first?
- Can the O(n^3) time be reduced for this recurrence, and why is that difficult here?
Similar Problems
Key Takeaways
- When neighbours change after each operation, consider defining the recurrence by the last operation.
- Open intervals with fixed outside boundaries make the left and right subproblems independent.
- Padding with sentinel boundaries often removes special cases from interval DP.
- Interval DP tables are usually filled from small gaps to large gaps.