The Balloon Game

TIP103 Unit 12 Session 2 (Click for link to problem statements)

The Balloon Game

A row of balloons carries the numbers in nums. Bursting balloon i earns nums[i-1] * nums[i] * nums[i+1] coins, where out-of-range neighbors count as 1. After a burst, its neighbors become adjacent.

Return the maximum coins you can collect by bursting all the balloons.

def max_coins(nums):
    pass

Problem Highlights

• 💡 Difficulty: Hard
• ⏰ Time to complete: 35-45 mins
• 🛠️ Topics: Dynamic Programming, Interval DP, Memoization

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What happens to the row when a balloon bursts?
  • A: The balloon is removed and its former left and right neighbors become adjacent, so the coins earned by later bursts depend on which balloons are still in the row.
• Q: What value do we use for a neighbor that is out of range?
  • A: Out-of-range neighbors count as 1. Bursting the last remaining balloon x earns 1 * x * 1 coins.
• Q: Does the order of bursting matter?
  • A: Yes. Different burst orders produce different totals, and we must return the maximum total over all possible orders.

HAPPY CASE
Input: nums = [3, 1, 5, 8]
Output: 167
Explanation: Burst the balloons in the order 1, 5, 3, 8:
3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 15 + 120 + 24 + 8 = 167.

Input: nums = [1, 5]
Output: 10
Explanation: Burst the 1 first (1*1*5 = 5), then the 5 (1*5*1 = 5), for a total of 10.

EDGE CASE
Input: nums = [7]
Output: 7
Explanation: A single balloon has no real neighbors, so bursting it earns 1*7*1 = 7 coins.

Input: nums = []
Output: 0
Explanation: With no balloons to burst, no coins can be collected.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Optimization Over an Ordering, we can consider the following approaches:

• Interval Dynamic Programming: The maximum coins for a range of balloons can be built from the answers for smaller ranges, which is the classic interval DP pattern. The key trick is to decide which balloon is burst last in an interval, because at that moment its neighbors are the fixed boundaries of the interval.
• Greedy (does not work): Always bursting the balloon with the largest (or smallest) immediate payoff fails, because an early burst changes which balloons become adjacent later.
• Brute Force: Trying every burst order costs O(N!) and is only feasible for tiny inputs, but it is a useful mental model before optimizing.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Pad the row with a virtual balloon of value 1 on each end so boundary math never needs special cases. For an open interval (left, right), ask which balloon k inside the interval is burst last. When k bursts last, every other balloon between left and right is already gone, so k's neighbors are exactly balloons[left] and balloons[right], earning balloons[left] * balloons[k] * balloons[right] coins. The subproblems (left, k) and (k, right) are then independent. Fill a table dp[left][right] for all intervals from smallest to largest and return the answer for the full padded row.

1) Build `balloons` by padding nums with 1 on both ends; let n be its length.
2) Create an n x n table `dp` filled with 0, where dp[left][right] is the
   maximum coins from bursting every balloon strictly between left and right.
3) For each interval length from 2 up to n - 1:
   a) For each left where the interval fits, set right = left + length.
   b) For each k strictly between left and right (the last balloon burst):
      i) coins = balloons[left] * balloons[k] * balloons[right]
      ii) dp[left][right] = max(dp[left][right], dp[left][k] + coins + dp[k][right])
4) Return dp[0][n - 1], the answer for the whole padded row.

⚠️ Common Mistakes

• Choosing the first balloon to burst instead of the last. Picking the first burst leaves subproblems that depend on each other; picking the last burst makes the two sides independent.
• Forgetting to pad with 1s, which forces messy out-of-range handling at the boundaries.
• Multiplying by the wrong neighbors: the last burst in (left, right) uses the boundary values balloons[left] and balloons[right], not balloons[k-1] and balloons[k+1].
• Iterating intervals from largest to smallest, so dp[left][k] and dp[k][right] are read before they are computed.

4: I-mplement

Implement the code to solve the algorithm.

def max_coins(nums):
    # Pad the row with virtual balloons of value 1 on each end
    balloons = [1] + nums + [1]
    n = len(balloons)

    # dp[left][right] = max coins from bursting every balloon strictly between left and right
    dp = [[0] * n for _ in range(n)]

    # length is the distance between the two boundaries (right - left)
    for length in range(2, n):
        for left in range(0, n - length):
            right = left + length
            # k is the LAST balloon burst in the open interval (left, right)
            for k in range(left + 1, right):
                coins = balloons[left] * balloons[k] * balloons[right]
                dp[left][right] = max(dp[left][right],
                                      dp[left][k] + coins + dp[k][right])

    return dp[0][n - 1]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: nums = [3, 1, 5, 8]

  • Padded row: balloons = [1, 3, 1, 5, 8, 1].
  • Length-2 intervals score each balloon alone, e.g. dp[0][2] = 1*3*1 = 3 and dp[2][4] = 1*5*8 = 40.
  • Longer intervals combine them; for the full interval (0, 5), choosing k = 4 (the balloon worth 8 bursts last) gives dp[0][4] + 1*8*1 + dp[4][5] = 159 + 8 + 0.
  • Output: 167

• Input: nums = [1, 5]

  • Padded row: balloons = [1, 1, 5, 1].
  • dp[0][2] = 1*1*5 = 5, dp[1][3] = 1*5*1 = 5.
  • For the full interval, bursting the 5 last wins: dp[0][2] + 1*5*1 + dp[2][3] = 5 + 5 + 0 = 10.
  • Output: 10

• Input: nums = [7]

  • Padded row: balloons = [1, 7, 1]; the only choice is k = 1, earning 1*7*1 = 7.
  • Output: 7

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of balloons in nums.

• Time Complexity: O(N^3) because there are O(N^2) intervals (left, right) and each one tries O(N) choices for the last balloon k.
• Space Complexity: O(N^2) for the dp table over all pairs of boundaries.