Burst Balloons (LeetCode 312)
Collect as many coins as you can by bursting every balloon in a row, one at a time, in an order you choose. The row holds n balloons, and nums[i] is the number written on balloon i (counting from 0).
A burst pays the product of three numbers: the burst balloon's own number and the numbers of its current left and right neighbours, meaning the closest balloons on each side that are still in the row. A side with no balloon left counts as 1.
Return the largest total any bursting order can reach.
Worked Examples
nums = [3,1,5,8]1671, then the 5, then the 3, then the 8: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167. The 8 goes last, so at that moment both of its neighbours are the phantom 1s.nums = [1,5]101 first for 1*1*5 = 5, then the 5 alone for 1*5*1 = 5: 10 in total.⚖️Formal Constraints & Bounds
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
Core Insight
Pick the balloon that bursts LAST in a range, not the first: its neighbours are then the range's two walls, so the two sides never touch and each is a smaller range of its own.
Real-World Scenario & Production Applications
Any job where removing, cutting or merging one item changes the cost of the next: ordering a chain of matrix multiplications, parsing a sentence into nested phrases, or cutting a long part into pieces when each cut costs the length of the piece.
Subproblems & Recurrence Decomposition3 Phases
Pad both ends with a phantom balloon worth 1, so every balloon always has two neighbours and the whole row is one range, (0, n - 1).
vals = [1] + nums + [1]Step-by-Step Execution Trace Table
Trace of Example 1: vals = [1, 3, 1, 5, 8, 1], n = 6. Each row is one range (i, j); coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j] for every k tried as the last balloon.
length | Range (i, j) | Each k tried last: coins | dp[i][j] |
|---|---|---|---|
| 2 | (0, 2) | k=1: 0 + 1*3*1 + 0 = 3 | 3 |
| 2 | (1, 3) | k=2: 0 + 3*1*5 + 0 = 15 | 15 |
| 2 | (2, 4) | k=3: 0 + 1*5*8 + 0 = 40 | 40 |
| 2 | (3, 5) | k=4: 0 + 5*8*1 + 0 = 40 | 40 |
| 3 | (0, 3) | k=1: 0 + 1*3*5 + 15 = 30; k=2: 3 + 1*1*5 + 0 = 8 | 30 |
| 3 | (1, 4) | k=2: 0 + 3*1*8 + 40 = 64; k=3: 15 + 3*5*8 + 0 = 135 | 135 |
| 3 | (2, 5) | k=3: 0 + 1*5*1 + 40 = 45; k=4: 40 + 1*8*1 + 0 = 48 | 48 |
| 4 | (0, 4) | k=1: 0 + 1*3*8 + 135 = 159; k=2: 3 + 1*1*8 + 40 = 51; k=3: 30 + 1*5*8 + 0 = 70 | 159 |
| 4 | (1, 5) | k=2: 0 + 3*1*1 + 48 = 51; k=3: 15 + 3*5*1 + 40 = 70; k=4: 135 + 3*8*1 + 0 = 159 | 159 |
| 5 | (0, 5) | k=1: 0 + 1*3*1 + 159 = 162; k=2: 3 + 1*1*1 + 48 = 52; k=3: 30 + 1*5*1 + 40 = 75; k=4: 159 + 1*8*1 + 0 = 167 | 167 |
The best range (0, 5) bursts the 8 (k = 4) last. Reading dp[1][3] = 15 in row (0, 3) only works because the length loop filled it one pass earlier.
| 1 | `dp[i][j]` is the most coins from bursting every balloon strictly between the walls `i` and `j`; `vals = [1] + nums + [1]` adds the outer walls. |
| 2 | Try every `k` in `range(i + 1, j)` as the LAST balloon to burst: it earns `vals[i] * vals[k] * vals[j]`, and the two sides `dp[i][k]` and `dp[k][j]` add. |
| 3 | Fill by `length` from `2` up, so every shorter range is final before it is read, and return `dp[0][n - 1]`. |
| 4 | The trap: filling row by row from `i = 0` reads `dp[k][j]` while it is still `0`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Bursting a balloon changes who stands next to whom, so asking "which balloon first?" drags the whole history along: after the first burst its two neighbours touch, and every later coin depends on that. Interval DP asks the opposite question, one range at a time: inside the range between the walls i and j, which balloon k bursts last? When k finally bursts, everything else between i and j is gone, so its neighbours are exactly vals[i] and vals[j]. And while k stands, the balloons on its left and on its right never meet, so the two sides are two smaller ranges, each solved on its own.
🧱 The Analogy: A Pillar Between Two Walls
Picture the range as a corridor between two walls, with balloon k as a pillar that stays up until the very end. Nothing you do on the left of the pillar can affect the right: the pillar is in the way. Clear both sides in their best way, then knock the pillar down last, when only the two walls are left beside it. Trying every balloon as the pillar and keeping the best total gives the best plan for the corridor.
🔑 The Key Idea in the Code
dp[i][k] and dp[k][j] are shorter ranges, so the length loop has already made them final before dp[i][j] reads them. The phantom 1s in vals = [1] + nums + [1] make the whole row the range (0, n - 1).
Filling row by row from
i = 0:dp[i][j]readsdp[k][j]for everyk > i, a row further down the table. Fill bylength, short ranges first; a plainfor i in range(n)loop reads those cells while they are still0, and on[3,1,5,8]it returns63instead of167.Choosing the first balloon to burst: charging
kwithvals[k - 1] * vals[k] * vals[k + 1], its neighbours in the original row, is wrong, because those balloons may burst before it does (98instead of167on[3,1,5,8]). Only the LAST balloon in(i, j)has fixed neighbours: the wallsvals[i]andvals[j].Padding with
0, or not padding:vals = [1] + nums + [1], because a missing neighbour counts as1. A0wall makes the last balloon of the row worth nothing.Off-by-one in the open range:
kruns overrange(i + 1, j), both walls excluded, and the answer isdp[0][n - 1].range(i + 1, j - 1)never tries the balloon next tojas the last one.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Bursting every balloon in a row" and a payout from "its current left and right neighbours": every burst changes who is next to whom, so the order matters and no greedy choice is safe. A row of items removed one at a time, with a cost that depends on the neighbours at that moment, is the signal for Interval DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
dp[i][j] is the most coins from bursting every balloon strictly between i and j while vals[i] and vals[j] still stand. Trying each k in range(i + 1, j) as the LAST to burst gives coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j], and dp[i][j] keeps the best.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Interval DP. First I add a phantom balloon worth one at each end, so every balloon always has two neighbours. Then dp of i, j is the most coins from bursting everything strictly between i and j. The key move is choosing which balloon k bursts last in that range. When k finally bursts, everything else between i and j is gone, so its neighbours are exactly the walls i and j, and it earns vals of i times vals of k times vals of j. While k stands, its left side and its right side never touch, so they are two smaller ranges and their best totals just add. Choosing the first balloon instead fails, because its neighbours then meet. The trap is the fill order: dp of i, j reads ranges that start further right, so I fill by length, shortest first. That's N squared ranges times N choices: O(N cubed) time and O(N squared) space.
Complexity & Mathematical Proof
O(N^3)
Look at the three loops. With n = N + 2, length runs from 2 to n - 1; for each length, i takes n - length values; and for each range (i, j), k takes length - 1 values. The body reads two finished cells, multiplies three numbers and takes one max: O(1). Every triple i < k < j of indices is visited exactly once, and there are C(N + 2, 3), about N^3 / 6, of them. Total: O(N^3).
O(N^2)
vals holds N + 2 numbers and dp is an (N + 2) x (N + 2) table: O(N^2). The loops keep only a few integers (length, i, j, k, coins) and there is no recursion, so the table dominates. The answer is one integer.
Derivation Progression
for length and for i visit every range (i, j) with at least one balloon inside exactly once.
for k in range(i + 1, j) tries every balloon inside the range as the last one to burst.
O(1)
coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j] and the max read two cells that are already final: no loop inside.
Each triple i < k < j is visited once, so the three loops together do cubic work.
Variable Definitions
Number of balloons, len(nums)
len(vals) = N + 2: the balloons plus the two phantom walls
j - i, the distance between the two walls of a range
Memory Architecture & Bounds
O(1): three nested loops, no recursion
O(N^2): the table dp with (N + 2) x (N + 2) cells, plus vals
O(1): one integer
Boundary Best / Worst Cases
: the loops never stop early, so every input of length N does the same C(N + 2, 3) steps.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "burst every balloon", "its current left and right neighbours". Each burst changes who is next to whom, so the order matters and no greedy choice is safe. Interval DP: choose the balloon k that bursts LAST in the range (i, j).
balloons, values . The loops visit triples: about a second in CPython, well within budget. The answer is at most , so it fits a 32-bit integer. The table needs cells.
At scale, the table is the memory cost; if many independent rows are solved in parallel, each worker needs its own table, since cells of one run must never be read by another.
Burst Balloons (LeetCode 312)
Collect as many coins as you can by bursting every balloon in a row, one at a time, in an order you choose. The row holds n balloons, and nums[i] is the number written on balloon i (counting from 0).
A burst pays the product of three numbers: the burst balloon's own number and the numbers of its current left and right neighbours, meaning the closest balloons on each side that are still in the row. A side with no balloon left counts as 1.
Return the largest total any bursting order can reach.
Worked Examples
nums = [3,1,5,8]1671, then the 5, then the 3, then the 8: 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167. The 8 goes last, so at that moment both of its neighbours are the phantom 1s.nums = [1,5]101 first for 1*1*5 = 5, then the 5 alone for 1*5*1 = 5: 10 in total.⚖️Formal Constraints & Bounds
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
Core Insight
Pick the balloon that bursts LAST in a range, not the first: its neighbours are then the range's two walls, so the two sides never touch and each is a smaller range of its own.
Real-World Scenario & Production Applications
Any job where removing, cutting or merging one item changes the cost of the next: ordering a chain of matrix multiplications, parsing a sentence into nested phrases, or cutting a long part into pieces when each cut costs the length of the piece.
Subproblems & Recurrence Decomposition3 Phases
Pad both ends with a phantom balloon worth 1, so every balloon always has two neighbours and the whole row is one range, (0, n - 1).
vals = [1] + nums + [1]Step-by-Step Execution Trace Table
Trace of Example 1: vals = [1, 3, 1, 5, 8, 1], n = 6. Each row is one range (i, j); coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j] for every k tried as the last balloon.
length | Range (i, j) | Each k tried last: coins | dp[i][j] |
|---|---|---|---|
| 2 | (0, 2) | k=1: 0 + 1*3*1 + 0 = 3 | 3 |
| 2 | (1, 3) | k=2: 0 + 3*1*5 + 0 = 15 | 15 |
| 2 | (2, 4) | k=3: 0 + 1*5*8 + 0 = 40 | 40 |
| 2 | (3, 5) | k=4: 0 + 5*8*1 + 0 = 40 | 40 |
| 3 | (0, 3) | k=1: 0 + 1*3*5 + 15 = 30; k=2: 3 + 1*1*5 + 0 = 8 | 30 |
| 3 | (1, 4) | k=2: 0 + 3*1*8 + 40 = 64; k=3: 15 + 3*5*8 + 0 = 135 | 135 |
| 3 | (2, 5) | k=3: 0 + 1*5*1 + 40 = 45; k=4: 40 + 1*8*1 + 0 = 48 | 48 |
| 4 | (0, 4) | k=1: 0 + 1*3*8 + 135 = 159; k=2: 3 + 1*1*8 + 40 = 51; k=3: 30 + 1*5*8 + 0 = 70 | 159 |
| 4 | (1, 5) | k=2: 0 + 3*1*1 + 48 = 51; k=3: 15 + 3*5*1 + 40 = 70; k=4: 135 + 3*8*1 + 0 = 159 | 159 |
| 5 | (0, 5) | k=1: 0 + 1*3*1 + 159 = 162; k=2: 3 + 1*1*1 + 48 = 52; k=3: 30 + 1*5*1 + 40 = 75; k=4: 159 + 1*8*1 + 0 = 167 | 167 |
The best range (0, 5) bursts the 8 (k = 4) last. Reading dp[1][3] = 15 in row (0, 3) only works because the length loop filled it one pass earlier.
| 1 | `dp[i][j]` is the most coins from bursting every balloon strictly between the walls `i` and `j`; `vals = [1] + nums + [1]` adds the outer walls. |
| 2 | Try every `k` in `range(i + 1, j)` as the LAST balloon to burst: it earns `vals[i] * vals[k] * vals[j]`, and the two sides `dp[i][k]` and `dp[k][j]` add. |
| 3 | Fill by `length` from `2` up, so every shorter range is final before it is read, and return `dp[0][n - 1]`. |
| 4 | The trap: filling row by row from `i = 0` reads `dp[k][j]` while it is still `0`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Bursting a balloon changes who stands next to whom, so asking "which balloon first?" drags the whole history along: after the first burst its two neighbours touch, and every later coin depends on that. Interval DP asks the opposite question, one range at a time: inside the range between the walls i and j, which balloon k bursts last? When k finally bursts, everything else between i and j is gone, so its neighbours are exactly vals[i] and vals[j]. And while k stands, the balloons on its left and on its right never meet, so the two sides are two smaller ranges, each solved on its own.
🧱 The Analogy: A Pillar Between Two Walls
Picture the range as a corridor between two walls, with balloon k as a pillar that stays up until the very end. Nothing you do on the left of the pillar can affect the right: the pillar is in the way. Clear both sides in their best way, then knock the pillar down last, when only the two walls are left beside it. Trying every balloon as the pillar and keeping the best total gives the best plan for the corridor.
🔑 The Key Idea in the Code
dp[i][k] and dp[k][j] are shorter ranges, so the length loop has already made them final before dp[i][j] reads them. The phantom 1s in vals = [1] + nums + [1] make the whole row the range (0, n - 1).
Filling row by row from
i = 0:dp[i][j]readsdp[k][j]for everyk > i, a row further down the table. Fill bylength, short ranges first; a plainfor i in range(n)loop reads those cells while they are still0, and on[3,1,5,8]it returns63instead of167.Choosing the first balloon to burst: charging
kwithvals[k - 1] * vals[k] * vals[k + 1], its neighbours in the original row, is wrong, because those balloons may burst before it does (98instead of167on[3,1,5,8]). Only the LAST balloon in(i, j)has fixed neighbours: the wallsvals[i]andvals[j].Padding with
0, or not padding:vals = [1] + nums + [1], because a missing neighbour counts as1. A0wall makes the last balloon of the row worth nothing.Off-by-one in the open range:
kruns overrange(i + 1, j), both walls excluded, and the answer isdp[0][n - 1].range(i + 1, j - 1)never tries the balloon next tojas the last one.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Bursting every balloon in a row" and a payout from "its current left and right neighbours": every burst changes who is next to whom, so the order matters and no greedy choice is safe. A row of items removed one at a time, with a cost that depends on the neighbours at that moment, is the signal for Interval DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
dp[i][j] is the most coins from bursting every balloon strictly between i and j while vals[i] and vals[j] still stand. Trying each k in range(i + 1, j) as the LAST to burst gives coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j], and dp[i][j] keeps the best.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd solve this with Interval DP. First I add a phantom balloon worth one at each end, so every balloon always has two neighbours. Then dp of i, j is the most coins from bursting everything strictly between i and j. The key move is choosing which balloon k bursts last in that range. When k finally bursts, everything else between i and j is gone, so its neighbours are exactly the walls i and j, and it earns vals of i times vals of k times vals of j. While k stands, its left side and its right side never touch, so they are two smaller ranges and their best totals just add. Choosing the first balloon instead fails, because its neighbours then meet. The trap is the fill order: dp of i, j reads ranges that start further right, so I fill by length, shortest first. That's N squared ranges times N choices: O(N cubed) time and O(N squared) space.
Complexity & Mathematical Proof
O(N^3)
Look at the three loops. With n = N + 2, length runs from 2 to n - 1; for each length, i takes n - length values; and for each range (i, j), k takes length - 1 values. The body reads two finished cells, multiplies three numbers and takes one max: O(1). Every triple i < k < j of indices is visited exactly once, and there are C(N + 2, 3), about N^3 / 6, of them. Total: O(N^3).
O(N^2)
vals holds N + 2 numbers and dp is an (N + 2) x (N + 2) table: O(N^2). The loops keep only a few integers (length, i, j, k, coins) and there is no recursion, so the table dominates. The answer is one integer.
Derivation Progression
for length and for i visit every range (i, j) with at least one balloon inside exactly once.
for k in range(i + 1, j) tries every balloon inside the range as the last one to burst.
O(1)
coins = dp[i][k] + vals[i] * vals[k] * vals[j] + dp[k][j] and the max read two cells that are already final: no loop inside.
Each triple i < k < j is visited once, so the three loops together do cubic work.
Variable Definitions
Number of balloons, len(nums)
len(vals) = N + 2: the balloons plus the two phantom walls
j - i, the distance between the two walls of a range
Memory Architecture & Bounds
O(1): three nested loops, no recursion
O(N^2): the table dp with (N + 2) x (N + 2) cells, plus vals
O(1): one integer
Boundary Best / Worst Cases
: the loops never stop early, so every input of length N does the same C(N + 2, 3) steps.
.
: the same count.
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "burst every balloon", "its current left and right neighbours". Each burst changes who is next to whom, so the order matters and no greedy choice is safe. Interval DP: choose the balloon k that bursts LAST in the range (i, j).
balloons, values . The loops visit triples: about a second in CPython, well within budget. The answer is at most , so it fits a 32-bit integer. The table needs cells.
At scale, the table is the memory cost; if many independent rows are solved in parallel, each worker needs its own table, since cells of one run must never be read by another.