Burst Balloons - Solution & Explanation
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 ith 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: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> [] coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
Example 2:
Input: nums = [1,5] Output: 10
Constraints:
n == nums.length1 <= n <= 3000 <= nums[i] <= 100
Approach Overview
Problem Overview: You are given an array where each element represents a balloon with a number on it. Bursting balloon i earns coins equal to nums[left] * nums[i] * nums[right], where left and right are the adjacent balloons still remaining. The goal is to determine the maximum coins you can collect by choosing the best order to burst all balloons.
Approach 1: Recursive with Memoization (Top‑Down DP) (Time: O(n^3), Space: O(n^2))
The key insight is to reverse the thinking: instead of deciding which balloon to burst first, decide which balloon will be burst last within a subarray. When balloon k is the last burst between indices left and right, the coins gained are nums[left] * nums[k] * nums[right]. The remaining work splits into two independent subproblems: bursting balloons in (left, k) and (k, right). Use recursion to try every possible last balloon and store results in a memo table to avoid recomputing overlapping subproblems. This is a classic Dynamic Programming pattern over intervals where each state represents a range of the array.
To simplify boundary cases, add virtual balloons with value 1 at both ends of the array. The recursive function solve(left, right) computes the best score obtainable between those boundaries. Memoization ensures each interval is computed once, reducing the exponential brute force search to cubic time.
Approach 2: Dynamic Programming with Bottom‑up (Interval DP) (Time: O(n^3), Space: O(n^2))
The bottom‑up version removes recursion and fills a DP table iteratively. Define dp[left][right] as the maximum coins obtainable by bursting balloons strictly between left and right. Iterate over interval lengths from small to large. For each interval, try every balloon k as the last one to burst and update:
dp[left][right] = max(dp[left][right], nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right])
This works because when k is chosen as the last balloon, the two smaller intervals are already solved. The DP table gradually builds solutions for larger intervals until the full range is computed. This approach is a textbook example of interval dynamic programming, where each state depends on smaller subranges.
Recommended for interviews: Interviewers typically expect the interval DP insight. Starting with the naive idea of trying all burst orders shows understanding, but recognizing that choosing the last balloon converts the problem into overlapping subproblems is the real breakthrough. Both memoized recursion and bottom‑up DP reach the optimal O(n^3) time and O(n^2) space complexity. The top‑down version is easier to reason about, while the bottom‑up version demonstrates stronger control over DP state transitions.
Approach 1: Recursive with Memoization Approach
This approach involves using a recursive function to try bursting each balloon and calculating the coins collected, while storing results of already computed subproblems to avoid redundant calculations. We pad the nums array with 1 at both ends to handle boundary conditions easily. For each subproblem defined by indices left and right, we choose a balloon i to burst last and calculate the coins.
This Python solution uses a memoized recursive approach. We define the function dp(left, right) to compute the maximum coins that can be obtained from balloons between left and right. The base case is when there are no balloons to burst between left and right. For each possible balloon i to burst, we maximize our coins by considering bursting i last in that subarray and adding the result from recursive calls to the left and right subproblems.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time Complexity: O(n^3), where n is the total number of balloons including the padding ones.
Space Complexity: O(n^2) due to memoization table.
Approach 2: Dynamic Programming with Bottom-up Approach
In this approach, we use a DP table to systematically build up solutions from smaller problems to a larger one without recursion. We create a dynamic programming matrix dp where dp[left][right] indicates the max coins to be obtained from subarray nums[left:right]. For each subarray defined by len, we consider bursting each possible k as the last balloon and compute the result using previously computed results.
The Python solution uses a bottom-up dynamic programming table to iterate through all subarray lengths from 3 upwards since we initially padded the nums array. This way, we are able to systematically determine the most coins by considering each k element in this sub-array as the last balloon to burst and combining results from smaller subproblems.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time Complexity: O(n^3)
Space Complexity: O(n^2)
Approach 3: Dynamic Programming
Let's denote the length of the array nums as n. According to the problem description, we can add a 1 to both ends of the array nums, denoted as arr.
Then, we define f[i][j] as the maximum number of coins we can get by bursting all the balloons in the interval [i, j]. Therefore, the answer is f[0][n+1].
For f[i][j], we enumerate all positions k in the interval [i, j]. Suppose k is the last balloon to burst, then we can get the following state transition equation:
$
f[i][j] = max(f[i][j], f[i][k] + f[k][j] + arr[i] times arr[k] times arr[j])
In implementation, since the state transition equation of f[i][j] involves f[i][k] and f[k][j], where i < k < j, we need to traverse i from large to small and j from small to large. This ensures that when calculating f[i][j], f[i][k] and f[k][j] have already been calculated.
Finally, we return f[0][n+1].
The time complexity is O(n^3), and the space complexity is O(n^2). Where n$ is the length of the array nums.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive with Memoization Approach | Time Complexity: O(n^3), where n is the total number of balloons including the padding ones. |
| Dynamic Programming with Bottom-up Approach | Time Complexity: O(n^3) |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive with Memoization (Top‑Down DP) | O(n^3) | O(n^2) | When reasoning about interval subproblems is easier with recursion and memoization. |
| Dynamic Programming Bottom‑up (Interval DP) | O(n^3) | O(n^2) | Preferred in interviews when you want deterministic iteration order and no recursion stack. |
Video Solution
DP 51. Burst Balloons | Partition DP | Interactive G-Meet Session Update • take U forward • 253,111 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Burst Balloons easy or hard?
Burst Balloons Python/Java solution
How to solve Burst Balloons in O(n)?
What is the best approach for Burst Balloons?
Is Burst Balloons asked at Google/Amazon/Meta?
What data structure is used in Burst Balloons?
What is the time complexity of Burst Balloons?
Ready to solve this problem?
Practice Burst Balloons with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor