← Samsung questions
CodingHard

Burst Balloons

Filed under Samsung

Free read 3 of 3

Understand 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

  1. Understand that subproblems overlap because bursting one balloon affects the neighbors of adjacent remaining balloons.

Solution

O(N^3) time, O(N^2) space

Python
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.