312. Burst Balloons

Burst all balloons to maximize coins, where bursting balloon i scores nums[i-1] * nums[i] * nums[i+1]. The key: instead of reasoning about which balloon you burst first, fix which balloon you burst last in each sub-interval — it keeps the sub-problems independent and unlocks interval DP.

● HardInterval DPMemoizationDivide and ConquerTypeScript

PROBLEM What we're solving

Given nums = [3, 1, 5, 8], burst every balloon. When you burst balloon i you earn nums[i-1] * nums[i] * nums[i+1] coins (treat out-of-bounds as 1). Return the maximum total coins.

For [3, 1, 5, 8]: burst in order 1 → 5 → 3 → 8 earns 3×1×5 + 3×5×8 + 1×3×8 + 1×8×1 = 15 + 120 + 24 + 8 = 167. Expected output: 167.

KEY IDEA Think about the LAST balloon to burst, not the first

Insight → If you pick balloon k as the last to burst inside interval [l, r], then at the moment it pops its only living neighbors are the boundaries padded[l-1] and padded[r+1] — which are fixed! That makes the coins from bursting k last independent of what happened inside the two sub-intervals [l, k-1] and [k+1, r], so they can be solved separately. This is the only formulation that keeps sub-problems non-overlapping in a useful way.

RECURRENCE dp[l][r] = max coins from bursting padded[l..r]

0 · Pad the array. Prepend and append virtual balloon 1. Now padded[0] = padded[n+1] = 1. This avoids index-out-of-bounds and keeps the boundary formula uniform.
1 · Define dp[l][r]. Maximum coins from bursting every balloon in padded[l..r] (1-based in padded). Base case: empty interval → 0 (already initialized).
2 · Enumerate the last balloon. For each candidate k in [l, r]:
coins(k) = padded[l-1] * padded[k] * padded[r+1] + dp[l][k-1] + dp[k+1][r]
The first term is the coins from popping k last; the other two are optimal sub-interval results.
3 · Fill bottom-up by length. Iterate len = 1, 2, …, n. For each length, sweep all starting positions. Shorter intervals are always ready before longer ones depend on them.
4 · Answer. dp[1][n] — the full range of real balloons (indices 1..n in the padded array).

Classic confusion → Trying to define sub-problems by which balloon you burst first doesn't work: after you pop balloon k first, its neighbors merge, so the left and right sub-problems share a boundary that depends on k's value — they're no longer independent. Flipping to "last burst" is the key inversion that makes everything decouple.

COST Complexity

Brute-force (all permutations)

O(n!)

Try every burst order; exponential blow-up.

Interval DP

O(n³)

O(n²) states × O(n) choices each; O(n²) space.

The table has O(n²) intervals; filling each takes O(n) work to scan all last-burst candidates → total O(n³). Space is O(n²) for the DP table. Top-down memoization gives the same asymptotic result with the same table.

Pattern transfer →"Last burst in interval" is the same inversion trick used in Strange Printer (last character printed in a range), Remove Boxes (merge groupings), Minimum Cost to Merge Stones, and Matrix Chain Multiplication. Whenever bursting/merging changes neighbors, think interval DP and ask "what's done last?"

RUN IT Choose the LAST balloon to burst in each interval

nums =

step 0 / 41

STARTBurst Balloons: nums = [3,1,5,8]. Pad with sentinel 1s: [1, 3, 1, 5, 8, 1]. Fill dp bottom-up by interval length.

1function maxCoins(nums: number[]): number {
2▶  const n = nums.length;
3  // Pad with virtual boundary balloons of value 1
4▶  const padded: number[] = [1, ...nums, 1];
5 
6  // dp[l][r] = max coins from bursting all balloons in padded[l..r]
7▶  const dp: number[][] = Array.from({ length: n + 2 }, () =>
8▶    new Array(n + 2).fill(0)
9▶  );
10 
11  // Fill by increasing interval length
12  for (let len = 1; len <= n; len++) {
13    for (let l = 1; l <= n - len + 1; l++) {
14      const r = l + len - 1;
15      // Try every k as the LAST balloon burst in [l, r]
16      for (let k = l; k <= r; k++) {
17        const coins =
18          padded[l - 1] * padded[k] * padded[r + 1] +
19          dp[l][k - 1] +
20          dp[k + 1][r];
21        dp[l][r] = Math.max(dp[l][r], coins);
22      }
23    }
24  }
25 
26  return dp[1][n];
27}

30115283

State

—

len

—

coins

—

dp[l][r]

—

dp[l][k-1]

—

dp[k+1][r]

current interval [l,r]candidate last balloon krecorded dp valuediscarded / suboptimal

slowfast

TYPESCRIPT The solution, annotated

burstBalloons.ts
function maxCoins(nums: number[]): number {
  const n = nums.length;
  // Pad with virtual boundary balloons of value 1
  const padded: number[] = [1, ...nums, 1];

  // dp[l][r] = max coins from bursting all balloons in padded[l..r]
  const dp: number[][] = Array.from({ length: n + 2 }, () =>
    new Array(n + 2).fill(0)
  );

  // Fill by increasing interval length
  for (let len = 1; len <= n; len++) {
    for (let l = 1; l <= n - len + 1; l++) {
      const r = l + len - 1;
      // Try every k as the LAST balloon burst in [l, r]
      for (let k = l; k <= r; k++) {
        const coins =
          padded[l - 1] * padded[k] * padded[r + 1] +
          dp[l][k - 1] +
          dp[k + 1][r];
        dp[l][r] = Math.max(dp[l][r], coins);
      }
    }
  }

  return dp[1][n];
}

Reading it block by block

Lines 4–5 — padding. Wrap nums with sentinel 1s to avoid boundary checks. Every burst formula padded[l-1] * padded[k] * padded[r+1] is safe because index 0 and index n+1 always exist and always equal 1.

Lines 7–9 — DP table. dp[l][r] is the max coins from bursting everything in padded[l..r]. Initialized to 0, which is the correct base case for empty intervals (when l > r).

Lines 11–13 — outer loops (interval length, then left endpoint). By iterating length from 1 to n, every sub-interval dp[l][k-1] and dp[k+1][r] is already computed by the time we need it — shorter intervals before longer ones.

Lines 14–19 — choose the last balloon k. For each candidate k ∈ [l, r], k is the last balloon standing inside [l, r]. Its neighbors at burst time are the fixed boundaries padded[l-1] and padded[r+1], making the coin formula exact. We take the max over all k.

Line 23 — return the answer. dp[1][n] covers the full padded range of real balloons (1-indexed). The sentinel values at indices 0 and n+1 are never themselves burst.

Complexity → O(n³) time: O(n²) sub-intervals each taking O(n) to fill. O(n²) space for the DP table. Top-down memoization has the same asymptotics but with function-call overhead; bottom-up iteration is usually faster in practice.

INTERVIEWFollow-ups they'll ask

"Can you do top-down instead?" Yes — add a memo table and recurse on dp(l, r). Same complexity; the iteration order handles itself. Bottom-up is more cache-friendly.
"Return the actual burst order, not just the max coins?" Maintain a choice[l][r] table recording which k was optimal for each interval, then reconstruct by traversal: choice[1][n] gives the last balloon, recurse on the two halves.
"What if balloon values can be negative?" The algorithm still works — the recurrence is unchanged because it maximizes over all burst orders regardless of sign. Negative values make it optimal to burst those balloons early (surrounded by small neighbors).
"Why does 'first burst' fail as a sub-problem definition?" After bursting k first, the sub-intervals [l, k-1] and [k+1, r]share a new boundary — each other's endpoints — so they're not independent. Sub-problems overlap in a way that breaks the DP decomposition.
"Matrix Chain Multiplication connection?"It's the same interval-DP shape: choose where to split the interval last (the last matrix multiplication / the last balloon burst) and combine independent halves. The recurrence differs but the table-fill pattern is identical.

OPTIMAL Interval DP

burstBalloons.ts
function maxCoins(nums: number[]): number {
  const n = nums.length;
  // Pad with virtual boundary balloons of value 1
  const padded: number[] = [1, ...nums, 1];

  // dp[l][r] = max coins from bursting all balloons in padded[l..r]
  const dp: number[][] = Array.from({ length: n + 2 }, () =>
    new Array(n + 2).fill(0)
  );

  // Fill by increasing interval length
  for (let len = 1; len <= n; len++) {
    for (let l = 1; l <= n - len + 1; l++) {
      const r = l + len - 1;
      // Try every k as the LAST balloon burst in [l, r]
      for (let k = l; k <= r; k++) {
        const coins =
          padded[l - 1] * padded[k] * padded[r + 1] +
          dp[l][k - 1] +
          dp[k + 1][r];
        dp[l][r] = Math.max(dp[l][r], coins);
      }
    }
  }

  return dp[1][n];
}

ALT 1 Top-down memoized interval recursion

O(n³) time · O(n²) space

Recurse on the open interval (left, right), pick the last balloon to burst as k, and cache each (left, right)in a memo so it's computed once.

approach-2.ts
function maxCoins(nums: number[]): number {
  // Pad with virtual boundary balloons of value 1.
  const padded: number[] = [1, ...nums, 1];
  const n = padded.length;

  // memo[left][right] = best coins from bursting every balloon
  // STRICTLY between indices left and right (the OPEN interval).
  // -1 marks "not yet computed".
  const memo: number[][] = Array.from({ length: n }, () =>
    new Array<number>(n).fill(-1)
  );

  const solve = (left: number, right: number): number => {
    // No balloons strictly between the two walls -> nothing to burst.
    if (left + 1 === right) return 0;
    if (memo[left][right] !== -1) return memo[left][right];

    let best = 0;
    // Choose k as the LAST balloon burst inside (left, right).
    // When k pops last, its living neighbors are exactly the walls
    // padded[left] and padded[right], so the score is fixed.
    for (let k = left + 1; k < right; k++) {
      const coins =
        padded[left] * padded[k] * padded[right] +
        solve(left, k) +
        solve(k, right);
      best = Math.max(best, coins);
    }

    memo[left][right] = best;
    return best;
  };

  return solve(0, n - 1);
}

Note → The "last to burst" framing is what makes this work: it pins k's neighbors to the fixed interval walls padded[left] and padded[right], so the two recursive halves (left, k) and (k, right) never overlap. Same O(n³) work as bottom-up — the memo turns the exponential recursion tree into O(n²) distinct states — but recursion fills only the intervals it actually needs.

ALT 2 Naive recursion (no memo)

O(n · 2ⁿ)-ish time · O(n) stack — TLEs

Same "last balloon" recurrence over the open interval, but with no caching — the same sub-intervals are recomputed over and over, so the call tree explodes.

approach-3.ts
function maxCoins(nums: number[]): number {
  // Pad with virtual boundary balloons of value 1.
  const padded: number[] = [1, ...nums, 1];

  // Best coins from bursting every balloon strictly between
  // indices left and right (the OPEN interval). No memo: every
  // call re-explores its sub-intervals from scratch.
  const solve = (left: number, right: number): number => {
    if (left + 1 === right) return 0;

    let best = 0;
    // Try each k as the last balloon burst inside (left, right).
    for (let k = left + 1; k < right; k++) {
      const coins =
        padded[left] * padded[k] * padded[right] +
        solve(left, k) +
        solve(k, right);
      best = Math.max(best, coins);
    }
    return best;
  };

  return solve(0, padded.length - 1);
}

Note → Correct but impractical: overlapping sub-intervals like (left, k) get recomputed an exponential number of times, so this times out for all but tiny inputs. It exists purely for contrast — adding a single memo[left][right] table (the approach above) collapses it to O(n³) with no change to the recurrence.

MNEMONIC The one-liner

"Freeze the last survivor in the interval — its neighbors are fixed walls, so the coins are exact."

TRIGGERS When you see _ → reach for _

burst/pop/merge changes neighbors	interval DP, ask "what goes last?"
maximize/minimize over all orderings of an array	O(n³) interval DP table
boundary values used in a product formula	pad with sentinels of value 1
"matrix chain multiplication" or "merge stones"	same interval DP skeleton

SKELETON The reusable shape

skeleton.ts
function maxCoins(nums: number[]): number {
  const n = nums.length;
  const padded = [1, ...nums, 1];
  const dp: number[][] = Array.from({ length: n + 2 }, () =>
    new Array(n + 2).fill(0)
  );
  for (let len = 1; len <= n; len++) {
    for (let l = 1; l <= n - len + 1; l++) {
      const r = l + len - 1;
      for (let k = l; k <= r; k++) {
        const coins =
          padded[l - 1] * padded[k] * padded[r + 1] +
          dp[l][k - 1] + dp[k + 1][r];
        dp[l][r] = Math.max(dp[l][r], coins);
      }
    }
  }
  return dp[1][n];
}

FLASHCARDS Tap to flip

What does dp[l][r] represent?

The maximum coins from bursting all balloons in padded[l..r] (real balloons, 1-based in the padded array).

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For nums = [3, 1, 5, 8], what is the maximum coins (the correct answer)?

QUESTION 02

Why does the "last balloon to burst" formulation work when "first balloon" does not?

QUESTION 03

What is the time complexity of the interval DP solution?

QUESTION 04

Why are sentinel values of 1 (not 0) appended/prepended?

QUESTION 05

What is the base case for the DP table?

QUESTION 06

Why must the outer loop iterate by interval length rather than by left endpoint l?

QUESTION 07

Trace nums = [2, 4]: what is the maximum coins?

QUESTION 08

#312 · Burst BalloonsInterval DP that chooses the LAST balloon to burst in each range: dp[l][r] = max over k of (nums[l−1]×nums[k]×nums[r+1] + dp[l][k−1] + dp[k+1][r]). Pad the array with virtual 1-balloons at both ends.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Think about the LAST balloon to burst, not the first

RECURRENCE dp[l][r] = max coins from bursting padded[l..r]

COST Complexity

RUN IT Choose the LAST balloon to burst in each interval

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Interval DP

ALT 1 Top-down memoized interval recursion

ALT 2 Naive recursion (no memo)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _