312. Burst Balloons (Hard)

Problem

You’re given n balloons in a row, each with a value nums[i]. Bursting balloon i gives you nums[i - 1] * nums[i] * nums[i + 1] coins (treating out-of-bounds indices as having value 1). After bursting, neighbors become adjacent. Return the maximum coins.

Example

• nums = [3, 1, 5, 8] → 167
• nums = [1, 5] → 10

LeetCode 312 · Link · Hard

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try every order

n! orderings. Feasible only for tiny inputs.

Python

from itertools import permutations

def max_coins(nums):
    n = len(nums)
    best = 0
    for perm in permutations(range(n)):                # L1: n! orderings
        active = [True] * n
        coins = 0
        for idx in perm:                                # L2: simulate this order
            left = 1
            for i in range(idx - 1, -1, -1):
                if active[i]: left = nums[i]; break
            right = 1
            for i in range(idx + 1, n):
                if active[i]: right = nums[i]; break
            coins += left * nums[idx] * right
            active[idx] = False
        best = max(best, coins)
    return best

Swift

final class Solution {
    func maxCoins(_ nums: [Int]) -> Int {
        if nums.isEmpty { return 0 }
        func solve(_ values: [Int]) -> Int { if values.isEmpty { return 0 }; var best = 0; for i in values.indices { let left = i == 0 ? 1 : values[i - 1]; let right = i == values.count - 1 ? 1 : values[i + 1]; var next = values; next.remove(at: i); best = max(best, left * values[i] * right + solve(next)) }; return best }
        return solve(nums)
    }
}

For each permutation, scan inward to find the active left and right neighbors at burst time.

Complexity

• Time: $O(n! · n²)$.
• Space: $O(n)$.

Approach 2: Recursive, pick the “first to burst” in each subproblem (wrong framing)

Picking the first to burst leaves a dependency where the next step depends on which balloons are gone, messy. The trick is to reframe.

Python

def max_coins(nums):
    if not nums:
        return 0
    best = 0
    for i in range(len(nums)):                          # L1: pick first to burst
        left = nums[i - 1] if i > 0 else 1
        right = nums[i + 1] if i + 1 < len(nums) else 1
        coins = left * nums[i] * right
        coins += max_coins(nums[:i] + nums[i + 1:])     # L2: recurse on remainder
        best = max(best, coins)
    return best

Swift

final class Solution {
    func maxCoins(_ nums: [Int]) -> Int {
        func solve(_ values: [Int]) -> Int {
            if values.isEmpty { return 0 }
            var best = 0
            for index in values.indices {
                let left = index == 0 ? 1 : values[index - 1]
                let right = index == values.count - 1 ? 1 : values[index + 1]
                var remaining = values
                remaining.remove(at: index)
                best = max(best, left * values[index] * right + solve(remaining))
            }
            return best
        }
        return solve(nums)
    }
}

Correct, but the subproblem state is “the actual remaining sequence,” which has exponentially many distinct values. Memoization on the list itself is unwieldy, and the recurrence doesn’t simplify into a clean (i, j) pair the way “last to burst” does. Exponential time without memoization, and even with memoization the state space blows up.

This is why Approach 3 reverses the framing.

Approach 3: Interval DP, pick the last balloon to burst in each interval (canonical)

Pad nums with 1’s on both sides. Let dp[i][j] = max coins from bursting all balloons strictly between indices i and j. For each k ∈ (i, j), assume balloon k is the last burst in this interval, at that moment its neighbors are nums[i] and nums[j].

Python

def max_coins(nums):
    nums = [1] + nums + [1]                          # L1: O(n) pad with sentinel 1s
    n = len(nums)                                    # L2: O(1) (n is now original_n + 2)
    dp = [[0] * n for _ in range(n)]                 # L3: O(n^2) table init

    for length in range(2, n + 1):                   # L4: O(n) loop over interval lengths
        for i in range(n - length + 1):              # L5: O(n) loop over left endpoints
            j = i + length - 1                       # L6: O(1) compute right endpoint
            for k in range(i + 1, j):                # L7: O(n) try each last-burst k
                coins = nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]  # L8: O(1)
                if coins > dp[i][j]:
                    dp[i][j] = coins                 # L9: O(1) update best

    return dp[0][n - 1]                              # L10: O(1) answer (full interval)

TypeScript

function maxCoins(nums: number[]): number {
    const padded = [1, ...nums, 1];                                        // L1: O(n) pad sentinels
    const n = padded.length;                                               // L2: O(1)
    const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));  // L3: O(n^2) init
    for (let length = 2; length <= n; length++) {                         // L4: O(n) length loop
        for (let i = 0; i <= n - length; i++) {                           // L5: O(n) left endpoint
            const j = i + length - 1;                                     // L6: O(1) right endpoint
            for (let k = i + 1; k < j; k++) {                             // L7: O(n) last-burst k
                const coins = padded[i] * padded[k] * padded[j] + dp[i][k] + dp[k][j];  // L8
                if (coins > dp[i][j]) dp[i][j] = coins;                   // L9: O(1) update best
            }
        }
    }
    return dp[0][n - 1];                                                   // L10: O(1) answer
}

Go

func maxCoins(nums []int) int {
    padded := make([]int, len(nums)+2)               // L1: O(n) pad with sentinel 1s
    padded[0], padded[len(padded)-1] = 1, 1
    for i, v := range nums { padded[i+1] = v }
    n := len(padded)                                 // L2: O(1)
    dp := make([][]int, n)
    for i := range dp { dp[i] = make([]int, n) }    // L3: O(n^2) table init
    for length := 2; length <= n; length++ {         // L4: O(n) length loop
        for i := 0; i <= n-length; i++ {             // L5: O(n) left endpoint
            j := i + length - 1                      // L6: O(1) right endpoint
            for k := i + 1; k < j; k++ {             // L7: O(n) last-burst k
                coins := padded[i]*padded[k]*padded[j] + dp[i][k] + dp[k][j] // L8
                if coins > dp[i][j] { dp[i][j] = coins } // L9: O(1) update best
            }
        }
    }
    return dp[0][n-1]                                // L10: O(1) answer
}

Where the time goes, line by line

Variables: n = len(nums) after padding (original length + 2).

Line	Per-call cost	Times executed	Contribution
L1-L3 (init)	$O(n)$ or $O(n^2)$	1	$O(n^2)$
L4 (length loop)	$O(1)$	n	$O(n)$ outer
L5 (left endpoint loop)	$O(1)$	$O(n)$ per length	$O(n^2)$ combined
L7 (last-burst k loop)	$O(1)$ body	$O(n)$ per (i,j) pair	$O(n^3)$ ← dominates
L8-L9 (coin calc + update)	$O(1)$	once per (i,j,k) triple	included above

The three nested loops at L4/L5/L7 iterate over all $O(n^3)$ triples (i, j, k). Each triple does $O(1)$ work, so the total is $O(n^3)$.

Complexity

• Time: $O(n^3)$, driven by L4/L5/L7 (the three nested loops over all interval triples).
• Space: $O(n^2)$ for the DP table.

Why “last to burst”

When k is the last balloon in (i, j), everything between i and k, and between k and j, has already been bursted. Those sub-intervals are independent subproblems, clean recurrence. Trying “first to burst” instead, the subproblems are not independent (their boundaries shift).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    func maxCoins(_ nums: [Int]) -> Int {
        let values = [1] + nums + [1], n = nums.count; var dp = Array(repeating: Array(repeating: 0, count: n + 2), count: n + 2)
        if n > 0 { for length in 1...n { for left in 1...(n - length + 1) { let right = left + length - 1; for last in left...right { dp[left][right] = max(dp[left][right], values[left - 1] * values[last] * values[right + 1] + dp[left][last - 1] + dp[last + 1][right]) } } } }
        return dp[1][n]
    }
}

Summary

Approach	Time	Space	Notes
Enumerate orderings	$O(n!)$	$O(n)$	Infeasible
Naive recursion (“first to burst”)	-	-	Wrong framing
Interval DP (“last to burst”)	$O(n^3)$	$O(n^2)$	Canonical

Interval DP is a major pattern, same template solves Matrix Chain Multiplication and Minimum Cost Tree From Leaf Values (1130).

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_312.py and run.
# Uses the canonical implementation (Approach 3: interval DP).

def max_coins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i + 1, j):
                coins = nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]
                if coins > dp[i][j]:
                    dp[i][j] = coins
    return dp[0][n - 1]

def _run_tests():
    # problem statement examples
    assert max_coins([3, 1, 5, 8]) == 167
    assert max_coins([1, 5]) == 10
    # edge: single balloon
    assert max_coins([5]) == 5
    # edge: two balloons, all equal
    assert max_coins([3, 3]) == 12
    # all ones
    assert max_coins([1, 1, 1]) == 3
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function maxCoins(nums: number[]): number {
    const padded = [1, ...nums, 1];
    const n = padded.length;
    const dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let length = 2; length <= n; length++)
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            for (let k = i + 1; k < j; k++) {
                const coins = padded[i] * padded[k] * padded[j] + dp[i][k] + dp[k][j];
                if (coins > dp[i][j]) dp[i][j] = coins;
            }
        }
    return dp[0][n - 1];
}

console.assert(maxCoins([3, 1, 5, 8]) === 167);
console.assert(maxCoins([1, 5]) === 10);
console.assert(maxCoins([5]) === 5);
console.assert(maxCoins([3, 3]) === 12);
console.assert(maxCoins([1, 1, 1]) === 3);
console.log("all tests pass");

Go

package main

import "fmt"

func maxCoins(nums []int) int {
    padded := make([]int, len(nums)+2)
    padded[0], padded[len(padded)-1] = 1, 1
    for i, v := range nums { padded[i+1] = v }
    n := len(padded)
    dp := make([][]int, n)
    for i := range dp { dp[i] = make([]int, n) }
    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            for k := i + 1; k < j; k++ {
                coins := padded[i]*padded[k]*padded[j] + dp[i][k] + dp[k][j]
                if coins > dp[i][j] { dp[i][j] = coins }
            }
        }
    }
    return dp[0][n-1]
}

func main() {
    if maxCoins([]int{3, 1, 5, 8}) != 167 { panic("fail") }
    if maxCoins([]int{1, 5}) != 10 { panic("fail") }
    if maxCoins([]int{5}) != 5 { panic("fail") }
    if maxCoins([]int{3, 3}) != 12 { panic("fail") }
    if maxCoins([]int{1, 1, 1}) != 3 { panic("fail") }
    fmt.Println("all tests pass")
}

Related data structures

• Arrays, 2-D DP table over intervals

Related concepts

• Dynamic Programming, the state and transition model for reusing answers to overlapping subproblems.
• Divide and Conquer, the split, solve, and combine pattern for independent subproblems.