p71 — Burst Balloons

Source: LeetCode 312 · Hard · Topics: DP, Interval DP, Divide and Conquer Companies (2024–2025): Google (very high), Amazon (high), Meta (medium), Microsoft (medium) Loop position: The canonical “split on the LAST action” interval DP. If you split on the first balloon to burst, the subproblems depend on each other and DP fails. Splitting on the LAST balloon to burst in a range makes the two halves independent. This counterintuitive flip is the entire trick.

1. Quick Context

n balloons, each with a value. Bursting balloon i gives you nums[left] * nums[i] * nums[right] coins (where left/right are the currently adjacent unburst balloons). After bursting i, its left and right become adjacent. Out-of-bounds neighbors count as value 1. Maximize total coins.

Strategy: Pad nums with 1 on each end. Define dp[i][j] = max coins from bursting all balloons strictly between i and j. Recurrence: enumerate k (the LAST balloon to burst in (i,j)); when k bursts, its neighbors are exactly i and j (because everything else between them is already gone). Sum nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j].

O(n³) time, O(n²) space.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/burst-balloons/

STOP. 45-min timer. This is HARD; almost no one gets it without the “last balloon” insight.

3. Prerequisite Concepts

  • Interval DP (filling dp[i][j] by increasing interval length).
  • Divide and conquer with the split point as the choice variable.
  • Why splitting on FIRST action fails for some problems (subproblems coupled).
  • Sentinel padding (1s on each end) to unify boundary cases.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Order n balloons for bursting; each burst earns left*self*right based on CURRENT neighbors; maximize.

2. Clarify: Are values positive? (Constraint says 0 ≤ nums[i] ≤ 100.) Range size? (n ≤ 500 → O(n³)=1.25×10⁸ borderline OK.)

3. Examples: [3,1,5,8] → 167. Optimal burst order: 1, 5, 3, 8 yielding 3·1·5 + 3·5·8 + 1·3·8 + 1·8·1 = 15+120+24+8 = 167.

5. Brute force: Try all permutations of burst orders. O(n!).

6. Target: O(n³) interval DP.

7. Pattern: Interval DP, split on LAST burst.

8. Develop: see solution.py.

9. Test: [1], [3,1,5,8] (canonical), [1,5], all zeros.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why splitting on FIRST balloon fails

If dp[i][j] = max coins from bursting balloons in (i,j) and you split on “first balloon k to burst”:

  • Earn nums[i] * nums[k] * nums[j]? No — when k bursts FIRST, its neighbors are whatever balloons are still in (i,j), not i and j directly. The remaining problem on (i,k) and (k,j) is not independent of past choices.

Splitting on LAST balloon to burst:

  • When k is the last balloon remaining in (i,j) before bursting, ALL OTHERS in (i,j) are already gone. So k’s neighbors at the time it bursts are exactly i and j. Recurrence becomes clean: nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j].

This insight — “structure your DP around the last action, not the first” — recurs in matrix-chain multiplication, optimal BST construction, polygon triangulation, and any problem where actions affect the cost of subsequent actions.

6.2 The sentinel pad

Padding nums with 1 on each end unifies the boundary case. Without it, the first/last balloon burst would have only one neighbor. With it, every balloon always has two neighbors and the formula is uniform.

6.3 Interval DP filling order

Fill by increasing interval length len = j - i. Inner loops iterate over i (interval start), compute j = i + len, then iterate k from i+1 to j-1.

for length in range(2, n+1):           # length of (i,j), exclusive endpoints
    for i in range(n - length):
        j = i + length
        for k in range(i+1, j):
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])

6.4 Memoized recursion variant

@lru_cache on (i, j) recursing on choice of last k. Equivalent O(n³). Often easier to write under interview pressure.

6.5 Connection to Matrix Chain Multiplication

Both problems share the structure: pick a split point k in [i+1, j-1]; combine costs of (i,k) and (k,j) plus an interaction cost. MCM’s interaction is matrix multiplication cost p[i]*p[k]*p[j]; BB’s is nums[i]*nums[k]*nums[j]. Same recurrence shape. If you’ve seen MCM, BB is a small leap.

6.6 Optimal BST construction

Knuth-Yao speedup brings the O(n³) of optimal BST construction down to O(n²) under certain monotonicity conditions. Burst Balloons does NOT satisfy those conditions (no Knuth-Yao speedup), so O(n³) is the best known.

6.7 Polygon triangulation

LC 1039 Minimum Score Triangulation of Polygon is essentially the same problem: pick a “third vertex” k for the triangle formed with edge (i,j); cost v[i]*v[k]*v[j] plus recursive subdivision. Identical to BB.

7. Anti-Pattern Analysis

  1. Split on FIRST balloon — subproblems are not independent; recurrence wrong.
  2. Forget sentinel padding — boundary cases multiply by 1 explicitly; ugly and bug-prone.
  3. Fill the DP table in wrong order (e.g., by row) — dp[i][j] depends on smaller intervals; must fill by length.
  4. Recurse without memoization — exponential blowup.
  5. Use dp[i][j] to mean coins from bursting i through j INCLUSIVE — recurrence becomes messier than the exclusive-endpoint convention.
  6. Try greedy (burst smallest first, etc.) — provably wrong; classic DP problem precisely because greedy fails.

8. Skills & Takeaways

  • Interval DP filling by increasing length.
  • “Split on LAST action” insight for problems with coupled subproblems.
  • Sentinel padding to unify boundaries.
  • Connection to MCM, polygon triangulation, optimal BST.

9. When to Move On

  • Implement BB iteratively in 30 min with sentinel padding and correct fill order.
  • Articulate “last balloon” reasoning in 90 seconds.
  • Solve LC 1039 (Polygon Triangulation) by analogy.
  • Solve Matrix Chain Multiplication cold.

10. Company Context

  • Google: L5/L6; the canonical “hard DP” Google problem.
  • Amazon: L6; pricing/auction-flavor variants.
  • Meta: E5/E6; less common but high signal.
  • Microsoft: L65; OR/optimization context.

Scorecard for strong: “Recognized interval DP, articulated ‘last balloon’ reasoning unprompted, padded sentinels, filled by length, computed O(n³).”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
DecompositionTries first-balloon, fails“DP something” hand-waveNames “split on last” cold+ cites MCM analogy upfront
RecurrenceConfusedAfter hintClean exclusive-endpoint formulation+ proves subproblem independence
ImplementationRecursive no memoMemoizedIterative with length-major fill+ space optimization discussion
GeneralizationNoneNoneNotes BB ≡ MCM ≡ polygon triangulation+ Knuth-Yao speedup limits

12. Level Delta

  • Mid (L4): Memoized recursion with the correct recurrence after a hint.
  • Senior (L5): Cold, iterative, with sentinel padding + length-major fill + names “split on last” insight.
  • Staff (L6): + connects to MCM/polygon triangulation/optimal BST + discusses Knuth-Yao (and why it doesn’t apply here).
  • Principal (L7+): + LP relaxation framing for interval-scheduling DPs + production applications (sequence-of-decisions in pricing, recommendation reordering).

13. Follow-up Q&A

Q1: What if values can be negative? A1: Same recurrence; max still works. The “smallest first” greedy intuition definitely fails.

Q2: What if you can burst K balloons at once (group burst)? A2: State expands; possibly need bitmask DP. Out of standard interview scope.

Q3: What if neighbors are non-adjacent (e.g., k-nearest)? A3: Recurrence breaks; subproblems no longer independent. Different algorithm needed.

Q4: Space optimization? A4: Filling diagonal-by-diagonal — can in principle reduce to O(n) but requires careful index gymnastics; rarely worth it.

Q5: Why does memoized recursion work but recursive without memo doesn’t? A5: Same subproblem (i,j) recurs exponentially many times in naive recursion (different burst orderings reach the same (i,j) state). Memoization collapses to O(n²) distinct subproblems.

14. Solution Walkthrough

See solution.py:

  • max_coins_dp — iterative interval DP, length-major fill; canonical.
  • max_coins_memo — top-down with @lru_cache.
  • max_coins_brute — permutation enumeration (oracle).

15. Beyond the Problem

Principal code review: “Burst Balloons is the cleanest example of why DP-direction matters. The naive ‘first action’ decomposition fails because actions COUPLE — bursting balloon 3 first changes who balloon 5’s neighbors are when it bursts later. The ‘last action’ decomposition succeeds because, by the time k bursts, you’ve already decided everything else in (i,j) and the answer there is dp[i][k] + dp[k][j] plus the clean interaction nums[i]*nums[k]*nums[j]. This pattern — interval DP with split-on-last — is the engine behind Matrix Chain Multiplication, optimal BST construction, polygon triangulation, and a class of operations-research problems. In production, you’ll see it in compiler optimizer phase ordering, in scheduling sequential resource-allocation decisions, and in dynamic-pricing systems where bid order affects clearing prices. When you see ‘enumerate the last action,’ you’re in interval-DP land; the O(n³) is unavoidable in general but worth every cycle.”