Log inSign up
hardLeetCodeNot Started

Burst Balloons

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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 the i-th balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

### Example 1 - Input: nums = [3, 1, 5, 8] - Output: 167 - Explanation: - Burst 1: coins = 3 * 1 * 5 = 15, remaining = [3, 5, 8] - Burst 5: coins = 3 * 5 * 8 = 120, remaining = [3, 8] - Burst 3: coins = 1 * 3 * 8 = 24, remaining = [8] - Burst 8: coins = 1 * 8 * 1 = 8, remaining = [] - Total coins = 15 + 120 + 24 + 8 = 167.

### Example 2 - Input: nums = [1, 5] - Output: 10

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • 0 <= nums[i] <= 100

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 'Reverse Thinking' principle in interval dynamic programming.
  • Understand why choosing the last balloon decouples the subproblems.
  • Implement the classic 3-nested loop interval DP pattern.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Bursting/removing elements from an array where adjacent elements change.
  • Cost function involves adjacent elements: nums[i-1] * nums[i] * nums[i+1].
  • Classic MCM interval dynamic programming signature.

Algorithmic Decision Tree:

  • When element removal breaks subproblem independence, consider the LAST element removed instead of the first.
  • Pad bounds with boundary values.

Connected Patterns:

Matrix Chain MultiplicationMinimum Cost to Merge StonesRemove Boxes

1. Recursive Exhaustive Simulation

Intuition

At each step, choose one remaining balloon to burst first, collect coins, remove it from the list, and recurse.

Algorithm

  1. Define dfs(balloons).
  2. If balloons is empty, return 0.
  3. For each balloon i in balloons:
  4. Calculate coins = (i > 0 ? balloons[i-1] : 1) * balloons[i] * (i < len - 1 ? balloons[i+1] : 1).
  5. Recurse on list without balloon i: coins + dfs(remaining).
  6. Return maximum coins over all choices.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int dfsPermutations(vector<int> b) {
8 if (b.empty()) return 0;
9 int maxCoins = 0;
10 for (size_t i = 0; i < b.size(); i++) {
11 int left = (i > 0) ? b[i - 1] : 1;
12 int right = (i + 1 < b.size()) ? b[i + 1] : 1;
13 int coins = left * b[i] * right;
14
15 vector<int> nextB = b;
16 nextB.erase(nextB.begin() + i);
17 maxCoins = max(maxCoins, coins + dfsPermutations(nextB));
18 }
19 return maxCoins;
20}
21
22int main() {
23 vector<int> nums = {3, 1, 5, 8};
24 cout << "Max Coins (Permutation DFS): " << dfsPermutations(nums) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(n!)
  • Space complexity: O(n) recursion call stack

2. Memoized Top-Down Interval DP

Intuition

Pad array to size n + 2 with boundaries 1. Compute solve(left, right) returning max coins between left and right boundary indices.

Algorithm

  1. Create padded array arr = [1, ...nums, 1].
  2. Define solve(left, right) with 2D memo table initialized to -1.
  3. Base Case: If left + 1 == right, return 0 (no balloons between them).
  4. For each index k from left + 1 to right - 1:
  5. coins = arr[left] * arr[k] * arr[right] + solve(left, k) + solve(k, right).
  6. Save and return memo[left][right] = max(coins).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <cstring>
5
6using namespace std;
7
8int memo[305][305];
9
10int solve(int left, int right, const vector<int>& arr) {
11 if (left + 1 == right) return 0;
12 if (memo[left][right] != -1) return memo[left][right];
13
14 int maxCoins = 0;
15 for (int k = left + 1; k < right; k++) {
16 int coins = arr[left] * arr[k] * arr[right] + solve(left, k, arr) + solve(k, right, arr);
17 maxCoins = max(maxCoins, coins);
18 }
19 return memo[left][right] = maxCoins;
20}
21
22int maxCoinsMemo(vector<int>& nums) {
23 int n = nums.size();
24 vector<int> arr(n + 2, 1);
25 for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
26
27 memset(memo, -1, sizeof(memo));
28 return solve(0, n + 1, arr);
29}
30
31int main() {
32 vector<int> nums = {3, 1, 5, 8};
33 cout << "Max Coins (Memoized DP): " << maxCoinsMemo(nums) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(n^3)
  • Space complexity: O(n^2) memoization table and O(n) call stack

3. Bottom-Up Interval Tabulation DP

Intuition

Fill 2D table dp[left][right] by iterating over interval length len from 1 to n.

Algorithm

  1. Create arr of size n + 2 with arr[0] = arr[n + 1] = 1.
  2. Initialize dp[n + 2][n + 2] with 0.
  3. For length = 1 to n:
  4. For left = 0 to n - length:
  5. right = left + length + 1
  6. For k = left + 1 to right - 1:
  7. dp[left][right] = max(dp[left][right], arr[left] * arr[k] * arr[right] + dp[left][k] + dp[k][right])
  8. Return dp[0][n + 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxCoinsOptimal(vector<int>& nums) {
8 int n = nums.size();
9 vector<int> arr(n + 2, 1);
10 for (int i = 0; i < n; i++) arr[i + 1] = nums[i];
11
12 vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
13
14 for (int len = 1; len <= n; len++) {
15 for (int left = 0; left <= n - len; left++) {
16 int right = left + len + 1;
17 for (int k = left + 1; k < right; k++) {
18 int coins = arr[left] * arr[k] * arr[right] + dp[left][k] + dp[k][right];
19 dp[left][right] = max(dp[left][right], coins);
20 }
21 }
22 }
23 return dp[0][n + 1];
24}
25
26int main() {
27 vector<int> nums = {3, 1, 5, 8};
28 cout << "Max Coins (Optimal Tabulation): " << maxCoinsOptimal(nums) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(n^3)
  • Space complexity: O(n^2) 2D array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Permutation SimulationO(n!)O(n)Choose first balloon to burst and recurse.Re-evaluates permutations
2.Memoized Interval DPO(n^3)O(n^2)Choose last balloon to burst in (left, right) with memo table.Top-down memoization
3.Bottom-Up Interval DPOptimalO(n^3)O(n^2)Iterate interval lengths from 1 to n.Triple nested loop

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Trying to divide the array based on which balloon is burst first (creates dependent boundaries).

Pitfall 2:

Forgetting to pad the left and right boundaries with 1.

Pitfall 3:

Iterating loop variables incorrectly (length must increase so sub-intervals are computed first).

Crucial Edge Cases to Validate:

  • n = 1: Single balloon. Coins = 1 * nums[0] * 1 = nums[0].
  • All balloon values 0: Output is 0.
  • Identical numbers: Algorithm still executes in O(n3).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Emphasize the 'Burst Last' insight immediately! It is the defining paradigm shift that turns an unsolvable problem into textbook Matrix Chain Multiplication.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does choosing the LAST balloon to burst make the subproblems independent, whereas choosing the FIRST balloon fails?

Back to DSA Sheet