0312 - Burst Balloons (Hard)

Problem Link

https://leetcode.com/problems/burst-balloons/

Problem Statement

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

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

Example 1:

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

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

Approach 1: Dynamic Programming - Memoization

If we solve this problem recursively we must think of our base case. When all balloons are already popped we can only get 0 coins. Then building up from then, we know, if we have 1 balloon, we will get the coins only from that balloon.

From our base case, we can then build on it. Our goal being that for each $kth$ balloon we select as the last balloon we pop, we can calculate the subproblems around that $kth$ balloon. That being the subproblem from $[i : k - 1]$ and the sub-problem $[k + 1 : j]$. Meaning for each $i$ and $j$ we can select all $k$ values to test first, and continue to check the sub problems.

If we preprocess our $nums$ array with $1$ values on each side to handle the case where we pop and end balloon that need to be multiplied by one, then we can initialize our $i$ and $j$ values as $1$ and $nums.length - 2$ which will be the start and end points of our old $nums$ array inside our new processed $nums$ array.

The memoization comes from storing the max coins we get for each $k$ we try at each $i$ and $j$ value. By checking the amount of coins we can get for each $k$ from $i$ to $j$ and caching the max coin value out of all the $k$'s we test we can reuse the work of that $i,j$ pair for future sub problems.

Time Complexity: $O(n^3)$ where n in the length of $nums$. We are going to have $n^3$ sub problems where we check each $i$, $j$, and $k$ value.

Space Complexity: $O(n^2)$. Since we are only storing the $i,j$ values in our cache, we will only end up with $n^2$ values inside our cache.

Python

Written by @ColeB2

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        # Pre process nums with 1s on each end to handle the edge
        # ballons where when we pop them the coins are multiplied by 1.   
        nums = [1] + nums + [1]
        # initialize our cache with key: (i, j) where i, j are the
        # start and end points of our array and the value: max_coins
        # being the max number of coins we can get from that subproblem
        # with those (i, j) end points.
        cache = {}
        # recursive function. Parameter i, j are our start and endpoints
        # in the array.
        def helper(i, j):
            # base case: 
            #i > j it means we have 0 values inside our array.
            if i > j:
                # return 0, as we can't get any coins from empty array.
                return 0
            # memoization: If we calculated this sub problem before:
            if (i, j) in cache:
                # get the value from the sub problem.
                return cache[(i, j)]
            # initialize max coins to -infinity.
            max_c = float('-inf')
            # loop through all the balloons from i to j. We use j + 1
            # as we want j to be an inclusive balloon that we can pop.
            # k will represent the last balloon we pop in the sub array.
            for k in range(i, j + 1):
                # initialize coins as k, being the last balloon we pop.
                coins = nums[k]
                # multiply that kth balloon by the end points, which
                # will be the balloons next to k when we pop all the
                # other balloons between the end points. Those endpoints
                # will be i - 1, and j + 1 which on the first iteration
                # will be the 1's that we preprocessed nums with.
                coins *= nums[i - 1]
                coins *= nums[j + 1]
                # We solved the base case for k being the last balloon
                # popped, now we need to add that to the sub problems
                # where we select ballons between i, k - 1 and k + 1, j.
                # This skips k, as that is the last balloon.
                coins += (helper(i, k - 1) + helper(k + 1, j))
                # update our max coin counter.
                max_c = max(max_c, coins)
                # update our cache so we don't have to redo this work
                # on future iterations.
                cache[(i,j)] = max_c
            # return the value we calculated above.
            return cache[(i, j)]
        # initialize our algorithm with the endpoints of the array.
        # example 1: 3,1,5,8. We preprocess it with 1's giving us:
        # 1,3,1,5,8,1 meaning the first number 3, will be indexed at
        # index 1, and the last number will be indexed at nums.length - 2.
        return helper(1, len(nums) - 2)