Repository navigation
150 — Burst Balloons
LeetCode 312 · Hard. You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons. If you burst balloon i, you get nums[left] * nums[i] * nums[right] coins, where left and right are the adjacent indices of i after the balloons already burst. If left or right is out of bounds of the array, treat it as if there is a balloon with a value of 1. Return the maximum coins you can collect by bursting all the balloons wisely.
The trap here is trying to decide "which balloon do I burst first" — but bursting a balloon changes who its neighbors are, so the first choice tangles up every later one. The trick that untangles it: think backward, about which balloon you burst last within a range. If balloon k is the last one burst between two boundary balloons left and right (which are never burst themselves — they stay put as the boundary), then when k finally goes, its neighbors are still exactly left and right, no matter what happened to everything in between. That reframes the problem as: for every sub-range (left, right), try every possible "last balloon standing" k, and combine the best answers for the two independent sub-ranges (left, k) and (k, right) it splits into. Two boundary indices describing a range is, again, a two-index state — just indexing an interval's endpoints instead of two separate strings.
"Burst balloons for max coins, where a burst's value depends on its current neighbors" is the interval-DP tell: pick what happens last within a range (not first), so the chosen split point's neighbors are locked in as the range's boundaries, and the two halves of the range become independent sub-problems — a table indexed by (left boundary, right boundary) rather than by prefix lengths.
Recurse on (left, right) — a range of surviving boundary balloons — trying every possible "last balloon burst" within that range, with no memoization. Padding the array with a 1 on each end lets the very first and last real balloons be treated the same as any interior one.
func maxCoinsBruteForce(_ nums: [Int]) -> Int {
let balloons = [1] + nums + [1]
let n = balloons.count
func burst(_ left: Int, _ right: Int) -> Int {
if left + 1 == right { return 0 } // no balloons left between the boundaries
var best = 0
for k in (left + 1)..<right {
let coins = balloons[left] * balloons[k] * balloons[right]
+ burst(left, k) + burst(k, right)
best = max(best, coins)
}
return best
}
return burst(0, n - 1)
}
// smoke test
print(maxCoinsBruteForce([3, 1, 5, 8])) // 167
print(maxCoinsBruteForce([1, 5])) // 10
print(maxCoinsBruteForce([7])) // 7Big-O: exponential time — without memoization, the same (left, right) sub-ranges get re-solved once for every different split point in every enclosing range that reaches them (there's no polynomial bound; it revisits sub-ranges roughly as many times as there are ways to nest splits above them). O(n) space for the recursion stack.
Fill an n x n table (n = the padded balloon count) by increasing range length, where dp[left][right] is the max coins obtainable from bursting every balloon strictly between left and right, leaving left and right themselves as the un-burst boundary.
func maxCoins(_ nums: [Int]) -> Int {
let balloons = [1] + nums + [1]
let n = balloons.count
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
for length in 2..<n { // gap between left and right boundaries
for left in 0..<(n - length) {
let right = left + length
for k in (left + 1)..<right { // k = the last balloon burst in this range
let coins = balloons[left] * balloons[k] * balloons[right]
+ dp[left][k] + dp[k][right]
dp[left][right] = max(dp[left][right], coins)
}
}
}
return dp[0][n - 1]
}
// smoke test — same cases as the brute force
print(maxCoins([3, 1, 5, 8])) // 167
print(maxCoins([1, 5])) // 10
print(maxCoins([7])) // 7Big-O: O(n^3) time — O(n^2) ranges (left, right), each trying up to O(n) split points k. O(n^2) space for the dp table.
Both versions make the same choice for every range — pick which balloon k is burst last, and combine the best answers for the two sub-ranges it creates — but the brute force treats every (left, right) range as fresh no matter how many enclosing ranges reach it, so small ranges get re-solved over and over. The optimal version fills the table by increasing range length, so dp[left][k] and dp[k][right] (both strictly shorter ranges) are always already-finished answers by the time dp[left][right] needs them. The deeper insight making this work at all is choosing "last burst" instead of "first burst" as the decision point: it's the only choice where the balloon's payout neighbors (left and right) are guaranteed fixed, which is what lets the range split into two truly independent sub-problems.
- 2D Dynamic Programming — interval DP is still fundamentally a two-index table, just indexed by a single sequence's two boundary positions rather than two separate sequences.
-
Arrays and Strings —
numsis padded into a new array with sentinel1s at both ends, anddpis a plain 2-D array filled by increasing sub-range length.
Burst Balloons is solved backward — pick which balloon dies last in a range, since that's the only choice whose neighbors are guaranteed to be the range's fixed boundaries, splitting the range into two independent sub-ranges.
- Why does choosing the balloon burst first in a range fail to produce independent sub-problems, while choosing the balloon burst last does?
- Why is
numspadded with a1on each end before buildingballoons, instead of special-casing "no left neighbor" / "no right neighbor" in the coin formula? - Trace
dp[0][2]formaxCoins([3, 1, 5, 8])(recallballoons = [1, 3, 1, 5, 8, 1]). Only one split pointkexists between boundaries0and2— which one, and what coin value does it produce?
⬅️ Previous: Edit Distance · Next: Regular Expression Matching ➡️