Burst Balloons

HARD✓ CHIP-TIMEDLC #312 — FULL STATEMENT ↗

The drill: Balloons in a row each carry a number; bursting one pays its value times the values of its current left and right neighbors, and the row closes up afterward. Choose a bursting order that maximizes total coins collected.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A row of balloons arrives, each printed with a number. Popping one pays out the printed value of that balloon times the values of whichever balloons are currently its immediate left and right neighbors — and the row closes the gap right after.

Because bursting a balloon changes who becomes neighbors with whom, the order balloons are popped in changes the total payout. The task is choosing a popping order — every balloon eventually goes — that maximizes coins collected overall.

The row's two open ends behave as if an invisible balloon worth 1 sits just off each edge, so an end balloon still has two neighbors to multiply against when it goes.

EX 01

nums = [4, 2, 6, 3]

→ 136

THE BOARD'S EXAMPLE

EX 02

nums = [7, 9, 3]

→ 217

EX 03

nums = [1]

→ 1

MINIMUM SIZE, SINGLE BALLOON

every balloon must eventually be burst — the row always ends empty
balloon values are small non-negative numbers, arrays sized modestly
boundary balloons off each end of the row count as value 1 during scoring
the payout to maximize is the running total across every burst, not any single pop

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Thinking about which balloon to burst first is a trap — bursting it changes who's adjacent to everyone else, so the leftover subproblems aren't independent. What if instead you decided which balloon burst LAST inside a stretch of the row?

HINT 2 THE STRUCTURE

If balloon k is the last one burst within an open interval (l, r), then at that moment its neighbors are still whichever balloons stand at the interval's own ends — l and r — no matter what already happened in between. The interval splits cleanly around k.

HINT 3 ONE STEP FROM THE ANSWER

dp(l, r) = the most coins from bursting everything strictly between l and r, leaving l and r themselves unburst. dp(l, r) = max over k in (l, r) of dp(l,k) + dp(k,r) + val[l]·val[k]·val[r]. Pad the row with a 1 on each end as permanent boundary balloons.

COACH'S BOARD — THE PATTERN, STEP BY STEP

BURST IT LASTPATTERN · INTERVAL DP — LAST BALLOONnums = [4, 2, 6, 3]

STEP 1

Balloons padded to [1,4,2,6,3,1]. dp(l,r) is the most coins from bursting everything strictly between l and r. Adjacent pairs have nothing between — 0.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/burst-balloons.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        balloons = [1] + nums + [1]
        n = len(balloons)
        memo = {}

        def dp(l, r):
            if r - l < 2:
                return 0
            if (l, r) in memo:
                return memo[(l, r)]
            best = 0
            for k in range(l + 1, r):
                best = max(best, dp(l, k) + dp(k, r) + balloons[l] * balloons[k] * balloons[r])
            memo[(l, r)] = best
            return best

        return dp(0, n - 1)

TIME O(N³)SPACE O(N²)PYTHON · RACE PACE · 18 LN

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        def rec(balloons):
            if not balloons:
                return 0
            best = 0
            for i in range(len(balloons)):
                left = balloons[i - 1] if i > 0 else 1
                right = balloons[i + 1] if i < len(balloons) - 1 else 1
                gained = left * balloons[i] * right
                remaining = balloons[:i] + balloons[i + 1:]
                best = max(best, gained + rec(remaining))
            return best

        return rec(nums)

TIME O(N!)SPACE O(N)PYTHON · TRAINING PACE · 15 LN

class Solution {
    private int[] balloons;
    private Integer[][] memo;

    public int maxCoins(int[] nums) {
        int n = nums.length;
        balloons = new int[n + 2];
        balloons[0] = 1;
        balloons[n + 1] = 1;
        for (int i = 0; i < n; i++) balloons[i + 1] = nums[i];
        memo = new Integer[n + 2][n + 2];
        return dp(0, n + 1);
    }

    private int dp(int l, int r) {
        if (r - l < 2) return 0;
        if (memo[l][r] != null) return memo[l][r];
        int best = 0;
        for (int k = l + 1; k < r; k++) {
            best = Math.max(best, dp(l, k) + dp(k, r) + balloons[l] * balloons[k] * balloons[r]);
        }
        memo[l][r] = best;
        return best;
    }
}

TIME O(N³)SPACE O(N²)JAVA · RACE PACE · 25 LN

class Solution {
    public int maxCoins(int[] nums) {
        List<Integer> balloons = new ArrayList<>();
        for (int v : nums) balloons.add(v);
        return rec(balloons);
    }

    private int rec(List<Integer> balloons) {
        if (balloons.isEmpty()) return 0;
        int best = 0;
        for (int i = 0; i < balloons.size(); i++) {
            int left = i > 0 ? balloons.get(i - 1) : 1;
            int right = i < balloons.size() - 1 ? balloons.get(i + 1) : 1;
            int gained = left * balloons.get(i) * right;
            List<Integer> remaining = new ArrayList<>(balloons);
            remaining.remove(i);
            best = Math.max(best, gained + rec(remaining));
        }
        return best;
    }
}

TIME O(N!)SPACE O(N)JAVA · TRAINING PACE · 21 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED