Burst Balloons - Video Solutions

Problem Overview: You are given an array where each element represents a balloon with a number on it. Bursting balloon i earns coins equal to nums[left] * nums[i] * nums[right], where left and right are the adjacent balloons still remaining. The goal is to determine the maximum coins you can collect by choosing the best order to burst all balloons.

Approach 1: Recursive with Memoization (Top‑Down DP) (Time: O(n^3), Space: O(n^2))

The key insight is to reverse the thinking: instead of deciding which balloon to burst first, decide which balloon will be burst last within a subarray. When balloon k is the last burst between indices left and right, the coins gained are nums[left] * nums[k] * nums[right]. The remaining work splits into two independent subproblems: bursting balloons in (left, k) and (k, right). Use recursion to try every possible last balloon and store results in a memo table to avoid recomputing overlapping subproblems. This is a classic Dynamic Programming pattern over intervals where each state represents a range of the array.

To simplify boundary cases, add virtual balloons with value 1 at both ends of the array. The recursive function solve(left, right) computes the best score obtainable between those boundaries. Memoization ensures each interval is computed once, reducing the exponential brute force search to cubic time.

Approach 2: Dynamic Programming with Bottom‑up (Interval DP) (Time: O(n^3), Space: O(n^2))

The bottom‑up version removes recursion and fills a DP table iteratively. Define dp[left][right] as the maximum coins obtainable by bursting balloons strictly between left and right. Iterate over interval lengths from small to large. For each interval, try every balloon k as the last one to burst and update:

dp[left][right] = max(dp[left][right], nums[left] * nums[k] * nums[right] + dp[left][k] + dp[k][right])

This works because when k is chosen as the last balloon, the two smaller intervals are already solved. The DP table gradually builds solutions for larger intervals until the full range is computed. This approach is a textbook example of interval dynamic programming, where each state depends on smaller subranges.

Recommended for interviews: Interviewers typically expect the interval DP insight. Starting with the naive idea of trying all burst orders shows understanding, but recognizing that choosing the last balloon converts the problem into overlapping subproblems is the real breakthrough. Both memoized recursion and bottom‑up DP reach the optimal O(n^3) time and O(n^2) space complexity. The top‑down version is easier to reason about, while the bottom‑up version demonstrates stronger control over DP state transitions.