Skip to content

Volume ITechnology

4.24.10 — Burst Balloons ​

LeetCode 312 · Hard

The problem ​

Balloons hold numbers. Bursting balloon i earns nums[left] × nums[i] × nums[right], where left and right are its current neighbours — the ones still unburst. Balloons outside the array count as 1. Maximise the total.

nums = [3,1,5,8]   →  167
    burst 1:  3×1×5  = 15    →  [3,5,8]
    burst 5:  3×5×8  = 120   →  [3,8]
    burst 3:  1×3×8  = 24    →  [8]
    burst 8:  1×8×1  = 8     →  []
    total 167

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • 0 <= nums[i] <= 100

Plain-English Restatement: You have a row of balloons, each painted with a number. When you pop a balloon, you get coins equal to its number multiplied by the numbers on the balloons immediately to its left and right. Once popped, it disappears, and the balloons that were on its left and right slide together to become new neighbors. You want to pop all the balloons in the exact sequence that maximizes your total coins.

Brute Force Approach: A recursive function could simulate popping each available balloon one by one.

  • Time Complexity: O(n!). For the first pop, you have n choices. For the second, n-1 choices.
  • Why it's wasteful: Bursting balloons A then B vs B then A might lead to the exact same remaining set of balloons, yet the brute force path recalculates the optimal bursts for that remaining set every time it encounters it.

Why the obvious approach fails ​

The natural state is "the best score for this set of remaining balloons", which is 2^n states — far too many.

The natural recursion is "which balloon do I burst first?" — and it does not work either, and understanding why is the whole problem.

When you burst a balloon first, the array splits into a left part and a right part — but they are not independent. After bursting the middle balloon, the balloons on either side become neighbours of each other, so what happens on the left changes the score on the right. The subproblems overlap in a way that cannot be separated, which means no clean recurrence.

The reversal that makes it work ​

Ask which balloon is burst LAST in a range, not first.

If balloon i is the last one to burst in the open range (left, right), then at that moment everything strictly between left and right is already gone, so i's neighbours are exactly left and right. Its score is a known number:

nums[left] \times nums[i] \times nums[right]

And now the two sides are independent. Everything in (left, i) was burst before i, with i still present as a wall, so that side never sees anything beyond i. Same on the right.

dp[left][right] = \max_{left < i < right}\Big( nums[left] \cdot nums[i] \cdot nums[right] + dp[left][i] + dp[i][right] \Big)

Choosing the last event instead of the first is what makes the subproblems separable. That reversal is the transferable idea, and it appears in several hard interval DPs.

Two setup details ​

Pad the array with 1s at both ends. The problem says out-of-range balloons count as 1, so [1] + nums + [1] removes every boundary check from the recurrence.

dp[left][right] uses an open interval — it covers the balloons strictly between left and right, and both endpoints stay unburst. Getting this convention wrong is where the off-by-one errors live, so state it before writing code.

The fill order, which is the real difficulty ​

dp[left][right] reads dp[left][i] and dp[i][right], both shorter ranges. So you must fill by increasing range length, not by row or column.

python
for length in range(2, n):          # gap between left and right
    for left in range(n - length):
        right = left + length

This is the standard interval DP loop shape, and you should recognise it on sight: outer loop over length, inner loop over start position, end worked out from both.

The solution ​

python
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        balloons = [1] + nums + [1]  # (1)
        n = len(balloons)
        dp = [[0] * n for _ in range(n)]  # (2)

        for length in range(2, n):                 # (3) open-interval width
            for left in range(n - length):  # (4)
                right = left + length  # (5)

                for i in range(left + 1, right):   # (6) i is burst LAST
                    dp[left][right] = max(  # (7)
                        dp[left][right],
                        balloons[left] * balloons[i] * balloons[right]
                        + dp[left][i] + dp[i][right]
                    )

        return dp[0][n - 1]  # (8)
ts
function maxCoins(nums: number[]): number {
  const balloons = [1, ...nums, 1];  // (1)
  const n = balloons.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));  // (2)

  for (let length = 2; length < n; length++) {  // (3)
    for (let left = 0; left + length < n; left++) {  // (4)
      const right = left + length;  // (5)

      for (let i = left + 1; i < right; i++) {  // (6)
        dp[left][right] = Math.max(  // (7)
          dp[left][right],
          balloons[left] * balloons[i] * balloons[right] + dp[left][i] + dp[i][right]
        );
      }
    }
  }

  return dp[0][n - 1];  // (8)
}

Line by line ​

Here dp[left][right] means "the most coins you can collect by bursting every balloon strictly between positions left and right, while left and right themselves are still standing".

(1) Put a balloon of value 1 at each end. Bursting the first or last real balloon then has a neighbour on both sides, so no special case is needed. These two extra balloons are never burst.

(2) A table of answers, all 0 at the start. A gap with no balloon inside it is worth 0.

(3) Work on gaps from narrow to wide. length is the distance from left to right. A distance of 2 means exactly one balloon inside. Wider gaps are built from narrower ones, so narrower ones must be finished first.

(4) Every possible left wall for this gap width,

(5) and its right wall.

(6) Try each balloon i inside the gap as the one burst LAST. This reversal is the key idea of the problem. If i is the last balloon in the gap to go, then at the moment it bursts, its neighbours are exactly left and right, because everything between them is already gone.

(7) The coins for that choice. Bursting i last earns balloons[left] × balloons[i] × balloons[right]. Before that, the balloons between left and i were burst on their own, earning dp[left][i], and the balloons between i and right earned dp[i][right]. The two sides never affect each other, because i stands between them until the end. Keep the best choice of i.

(8) The answer is the gap between the two padding balloons, which contains every real balloon.

length starts at 2, because an open interval needs at least one balloon strictly inside it.

dp[left][i] and dp[i][right] are both shorter than dp[left][right], so the length-ordered loop guarantees they are filled.

The answer is dp[0][n-1] — the whole padded array, with the two sentinel 1s as the outer walls.

Trace on [3,1,5,8] ​

Padded: [1,3,1,5,8,1].

The optimal order bursts 1, then 5, then 3, then 8 — meaning 8 is burst last overall. So the top-level split takes i as the index of 8, scoring 1 × 8 × 1 = 8, plus dp for everything to its left. That left range then chooses 3 as its last balloon, and so on.

Reading the answer as a nesting of "who went last" is what makes the recurrence believable.

The top-down version ​

python
from functools import lru_cache

def maxCoins(self, nums):
    balloons = [1] + nums + [1]

    @lru_cache(None)
    def best(left: int, right: int) -> int:
        if left + 1 == right:
            return 0
        return max(balloons[left] * balloons[i] * balloons[right]
                   + best(left, i) + best(i, right)
                   for i in range(left + 1, right))

    return best(0, len(balloons) - 1)

Easier to write and easier to trust, because you never work out the fill order — the recursion finds it. This is the case 4.22 makes for deriving top-down.

Complexity ​

O(n^3) time, and you can read that straight off the structure: O(n^2) states — one per (left, right) pair — times O(n) transitions, one per choice of the last balloon. That is the states × transitions formula.

O(n^2) space.

Complexity Derivation ​

  • Time Complexity: O(n^3). Let's break it down intuitively:
    1. There are roughly n^2 / 2 pairs of (left, right) intervals we evaluate (the outer two loops).
    2. For each interval, we loop over every balloon i inside that interval to try it as the last balloon to burst (the inner loop).
    3. Since the interval length can be up to n, the inner loop runs up to n times.
    4. (n^2 \text{ states}) \times (n \text{ work per state}) = O(n^3).
  • Space Complexity: O(n^2) because we allocate a 2D matrix of size n \times n to store the maximum coins for each open interval (left, right).

Edge cases ​

  • Empty Array: Handled by constraints n >= 1.
  • Zeros in the Array: A balloon with 0 will yield 0 coins when burst, but it acts as a boundary. The DP correctly evaluates when to burst it (usually as early as possible so it stops zeroing out adjacent bursts).

Where this goes next ​

Interval DP is a small family with a shared loop shape and a shared question — what is the last, or the outermost, thing to happen in this range?

  • Matrix Chain Multiplication — the classic. Which multiplication happens last?
  • Minimum Cost to Cut a Stick — which cut is made last?
  • Strange Printer, Remove Boxes — same family, harder states.
  • Longest Palindromic Subsequence — an interval DP where the question is about the two ends rather than a split point.

The recognition cue: a range, a choice of split point inside it, and O(n^3) allowed by the constraints. n ≤ 300 gives 2.7 \times 10^7, which is precisely an O(n^3) budget — the constraint is telling you the answer.

What the interviewer will push on ​

"Why does thinking about the first balloon fail?" The two sides become neighbours after the burst, so the subproblems are not independent. This is the question the problem exists to ask.

"Why does the last balloon work?" At the moment it bursts, everything inside is gone, so its neighbours are exactly the range's endpoints — and each side is then a self-contained subproblem.

"Why pad with 1s?" Out-of-range balloons count as 1, and padding removes every boundary check.

"What is the fill order and why?" By increasing range length, because each state reads shorter ranges.

"What is the complexity, and how do you know?" O(n^2) states times O(n) transitions.

One thing to volunteer: say the reversal out loud before anything else. "I will pick which balloon bursts last, not first, because that is what makes the two sides independent." Everything else on this page follows from that sentence, and an interviewer who hears it knows you have understood the problem rather than remembered it.

Next: 4.24.11 Regular Expression Matching — the last problem in the chapter, and the one with the most cases to get right.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet