Faangprep Logo
Log inStart free
Browse curriculum

Burst Balloons

Maximise the coins from bursting every balloon with interval DP: guess which balloon in a range bursts last, so its neighbours are the range's walls.

HardSolve on LeetCode

Problem Understanding

Burst Balloons: balloon i has the number nums[i]. Bursting it earns nums[left] · nums[i] · nums[right], where left and right are its current neighbours (a missing neighbour counts as 1), and then those neighbours become adjacent. Return the most coins you can collect by bursting them all.

Example: nums = [3, 1, 5, 8] returns 167: burst 1, 5, 3, 8 for 15 + 120 + 24 + 8.

The Intuition: Think About the Last Balloon

Choosing the first balloon to burst does not split the problem: its neighbours change, so the left and right parts keep interacting.

Choose the last one instead. Pad the array with a 1 at each end, and look at the open interval between walls l and r:

  1. If k is the last balloon burst inside it, everything else in (l, r) is already gone, so k's neighbours are exactly l and r. It earns vals[l] · vals[k] · vals[r].
  2. Before that, the balloons in (l, k) and in (k, r) were burst with k standing between them as a wall, so the two sides never touch: they are independent subproblems.
  3. Try every k and keep the best: dp[l][r] = max(dp[l][k] + vals[l] · vals[k] · vals[r] + dp[k][r]).

This is interval dynamic programming: the state is a range, and ranges are filled from short to long. The same "split at k" shape solves matrix-chain multiplication; compare it with the row-by-row tables of Edit Distance.

Interactive Walkthrough

The padded balloons sit on top with the walls l, r and the last balloon k marked. Below, the triangle holds dp[l][r] for every interval with something inside; the cell being solved is solid and the two sub-intervals it adds are tinted. Try Ones inside to see why the cheap balloons go first.

Dry Run Table

Input: nums = [3, 1, 5, 8], padded to vals = [1, 3, 1, 5, 8, 1] (indexes 0 to 5)

l \ r 2 3 4 5
0 3 30 159 167
1 15 135 159
2 40 48
3 40
  • dp[1][3] = 15: only balloon 1 (value 1) is inside, between 3 and 5.
  • dp[0][5] = 167: the best last balloon is 8 (index 4): dp[0][4] 159 + 1 · 8 · 1 + dp[4][5] 0.

Answer: 167.

The Solution Template

Bottom-up interval DP, filled by length. len is the distance between the two walls, so an interval with one balloon inside has len = 2.

Burst Balloons Code
1var maxCoins = function(nums) {
2    const vals = [1, ...nums, 1];
3    const n = vals.length;
4    const dp = Array.from({ length: n }, () => Array(n).fill(0));
5    for (let len = 2; len < n; len++) {
6        for (let l = 0; l + len < n; l++) {
7            const r = l + len;
8            for (let k = l + 1; k < r; k++) {
9                const coins = dp[l][k] + vals[l] * vals[k] * vals[r] + dp[k][r];
10                dp[l][r] = Math.max(dp[l][r], coins);
11            }
12        }
13    }
14    return dp[0][n - 1];
15};

Edge Cases & Common Mistakes

  • Choosing the first balloon: the subproblems are not independent; always reason about the last one.
  • Forgetting the padding: without the 1s at each end, the walls of the outermost interval do not exist.
  • Closed vs open intervals: dp[l][r] covers balloons strictly between l and r; the walls themselves are not burst in that interval.
  • Fill order: iterating l from 0 upward with r from l + 2 reads dp[k][r] before it is computed; fill by length, or run l downward.
  • One balloon: [7] gives 1 · 7 · 1 = 7.

Summary

Pad nums with 1 on both sides. For each interval by increasing length, try every balloon k inside as the last to burst: dp[l][k] + vals[l] · vals[k] · vals[r] + dp[k][r]. Return dp[0][n - 1]. O(n³) time, O(n²) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Wildcard Matching

Next

Best Time to Buy and Sell Stock with Cooldown

The approach, step by step

  1. Pad the array

    vals = [1] + nums + [1]. dp[l][r] is the best for bursting everything strictly between l and r; it is 0 when nothing is inside.

  2. Try every last balloon

    For each interval, by increasing length, dp[l][r] = max over l < k < r of dp[l][k] + vals[l] · vals[k] · vals[r] + dp[k][r].

  3. Read the answer

    Return dp[0][n - 1], the whole padded range.

Frequently asked questions

Why choose the last balloon to burst instead of the first?

If k bursts first, its neighbours change afterwards and the left and right parts are no longer independent. If k bursts last in the range (l, r), every other balloon in the range is already gone, so its neighbours are exactly l and r, and the two sides (l, k) and (k, r) can be solved separately.

Why pad the array with 1 at both ends?

The problem treats out-of-range neighbours as 1. Adding a 1 at each end makes that explicit, so every interval (l, r) has real walls and the last balloon in the whole array pays 1 · nums[k] · 1.

What order do you fill the DP table in?

By interval length, shortest first. dp[l][r] needs dp[l][k] and dp[k][r], which are strictly shorter intervals, so filling length 2, then 3, and so on guarantees they are ready.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description