Burst Balloons
Problem
Given an array of integers nums representing balloons, return the maximum coins you can collect by bursting all the balloons wisely, where bursting balloon i yields coins equal to nums[left] * nums[i] * nums[right], with left and right being adjacent balloons after previous bursts.
- 1 ≤ nums.length ≤ 300
- 0 ≤ nums[i] ≤ 100
Example
nums = [3,1,5,8]167A brute-force approach would try all permutations of bursting balloons, which is O(n!) and infeasible. Instead, the algorithm pads nums with 1s at both ends to handle boundaries uniformly. It then uses a recursive DP function dp(l, r) that computes the maximum coins obtainable by bursting all balloons in the range [l, r]. The key insight is to consider which balloon i in [l, r] to burst last. Bursting balloon i last means its neighbors are fixed as nums[l-1] and nums[r+1], so the coins gained are nums[l-1] * nums[i] * nums[r+1]. The problem then splits into two independent subproblems: bursting balloons in [l, i-1] and [i+1, r]. The algorithm tries all i in [l, r], memoizes results, and returns the maximum total coins.
Approach
Straightforward Solution
A brute-force approach tries all permutations of bursting balloons, resulting in O(n!) time complexity, which is computationally impossible for even moderate n.
Core Observation
The coins gained from bursting a balloon depend on its neighbors, which change dynamically as balloons are burst. This dependency makes naive approaches fail because subproblems are not independent if we pick the first balloon to burst. However, if we pick the last balloon to burst in a range, its neighbors are fixed, making subproblems independent and solvable via DP.
Path to Optimal
PreviewThe key recognition signals are 'maximum coins' and 'dependent neighbors' which indicate Dynamic Programming with interval partitioning. The breakthrough is reversing the problem: instead of choosing the first balloon to burst, choose the last balloon to burst in a given range…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a top-down recursive DP function dp(l, r) that returns the maximum coins from bursting all balloons in the range [l, r]. For each i in [l, r], consider bursting balloon i last, gaining coins nums[l-1] * nums[i] * nums[r+1] plus the results of dp(l, i-1) and dp(i+1, r)…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n^3)
There are O(n^2) subproblems defined by intervals (l, r). For each subproblem, the algorithm tries up to O(n) choices for the last balloon to burst, resulting in O(n^3) total time.
Space
O(n^2)
The memoization dictionary stores results for each of the O(n^2) intervals. The recursion stack depth is O(n), but the dominant space is the memo cache.
Pattern Spotlight
Dynamic Programming (Interval DP)
When subproblems depend on dynamic neighbors, reverse the perspective to pick the last action in a range, fixing boundaries and creating independent subproblems suitable for DP.
Solution
| 1 | class Solution:
|
| 2 | def maxCoins(self, nums: list[int]) -> int:
|
| 3 | nums = [1] + nums + [1]
|
| 4 | memo = {}
|
| 5 |
|
| 6 | def dp(l, r):
|
| 7 | if l > r:
|
| 8 | return 0
|
| 9 | if (l, r) in memo:
|
| 10 | return memo[(l, r)]
|
| 11 |
|
| 12 | max_coins = 0
|
| 13 | for i in range(l, r + 1):
|
| 14 | coins = nums[l - 1] * nums[i] * nums[r + 1]
|
| 15 | coins += dp(l, i - 1) + dp(i + 1, r)
|
| 16 | max_coins = max(max_coins, coins)
|
| 17 |
|
| 18 | memo[(l, r)] = max_coins
|
| 19 | return max_coins
|
| 20 |
|
| 21 | return dp(1, len(nums) - 2) |
Step-by-Step Solution
Pad Input and Initialize Memoization Cache
| 3 | nums = [1] + nums + [1]
|
| 4 | memo = {}
|
Objective
To simplify boundary handling by padding the input array with virtual balloons and prepare a cache for memoization.
Key Insight
Padding nums with 1 at both ends ensures that every balloon has fixed neighbors during the DP calculation, eliminating edge-case checks. The memo dictionary caches results for intervals to avoid redundant computations, transforming exponential recursion into polynomial DP.
Interview Quick-Check
Core Logic
Padding with 1s creates fixed boundaries that simplify the DP recurrence by ensuring neighbors are always defined.
Common Pitfalls & Bugs
Forgetting to pad the array leads to complicated boundary checks and potential off-by-one errors.
Recursively Compute Maximum Coins for Subranges
To recursively compute and memoize the maximum coins obtainable by bursting all balloons in the interval [l, r].
Return Final Maximum Coins for Full Range
To initiate the DP recursion on the full range of original balloons and return the maximum coins achievable.
2 more steps with full analysis available on Pro.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
return 0Check if the result for interval (l, r) is already memoized.
This lookup avoids recomputing subproblems, ensuring each interval is solved once and results are reused, critical for efficiency.
coins = nums[l - 1] * nums[i] * nums[r + 1]Calculate coins gained by bursting balloon i last, using fixed neighbors nums[l-1] and nums[r+1].
Because balloon i is last in [l, r], its neighbors are fixed as nums[l-1] and nums[r+1], allowing a direct calculation of coins gained without ambiguity.
memo = {}Initialize a memoization dictionary to cache results of subproblems.
Memoization prevents redundant computations by storing the maximum coins for each interval, transforming an exponential recursion into polynomial time.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why does choosing the last balloon to burst in a range create independent subproblems, whereas choosing the first does not?
See the answer with Pro.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Burst Balloons from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Burst Balloons drill