Burst Balloons
Filed under Samsung
Free read 3 of 3Understand that subproblems overlap because bursting one balloon affects the neighbors of adjacent remaining balloons.
The question
Given n balloons indexed from 0 to n - 1, each with a number of coins represented by an array nums, find the maximum coins you can collect by bursting all balloons wisely. Bursting balloon i gives nums[i - 1] * nums[i] * nums[i + 1] coins. If an index is out of bounds, treat it as having a value of 1.
Constraints
- n == nums.length
- 1 <= n <= 300
- 0 <= nums[i] <= 100
Examples
- Input
- nums = [3, 1, 5, 8]
- Output
- 167
- Why
- nums = [3,1,5,8] -> [3,5,8] -> [3,8] -> [8] -> [], coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167.
Approach
Understand that subproblems overlap because bursting one balloon affects the neighbors of adjacent remaining balloons.
Try all possible permutations of bursting balloons, which results in O(n!) time complexity and will time out.
Use Interval Dynamic Programming. Instead of picking the first balloon to burst, pick the *last* balloon k to burst in the range (left, right). The total coins will be nums[left] * nums[k] * nums[right] + dp(left, k) + dp(k, right).
Arrays containing zeros or length 1.
Solution
O(N^3) time, O(N^2) space
class Solution:
def maxCoins(self, nums: list[int]) -> int:
nums = [1] + nums + [1]
n = len(nums)
dp = [[0] * n for _ in range(n)]
for length in range(1, n - 1):
for left in range(1, n - length):
right = left + length
for k in range(left, right):
dp[left][right] = max(dp[left][right],
nums[left-1] * nums[k] * nums[right] + dp[left][k] + dp[k+1][right])
return dp[1][n-1]
Tips
- What they are testing: Test with a single balloon array [3] and arrays with zeros.
- Common mistake: Trying to choose which balloon to burst *first* instead of thinking backwards about which balloon to burst *last* in a given range.
Related Samsung questions
Collected from public candidate posts and coding forums. Updated Nov 2026.