Burst Balloons | LeetCode | Solution Explained
LeetCode 312. Burst Balloons is a hard problem. I explain the dynamic programming approach in detail, along with intuitions on how to reach to the solution. Problem Link.
0. Burst Balloons: Problem Discussion
0.0. IO Format
- Input: array of integers, nums representing balloon coins
- Output: Maximum coins we can collect after bursting all the balloons
- ith balloon bursted gets nums[i-1] * nums[i] * nums[i+1] score.
n == nums.length
1 <= n <= 500
0 <= nums[i] <= 100
Given the input as [3, 1, 5] the best sequence of removal/bursting of balloons is 1 then 3 then 5.
1. Burst Balloons: Observations & Logic
Looking at the decision tree, it looks like we have to make N decisions initially, then N-1 then N-2 and so on. This means that we are looking at O(N!) time complexity. Ouch!
But notice the last column. We don’t need to compute values for   and  over and over again. Perhaps … there are overlapping sub-problems.
1.1. Dynamic Programming
DP is the first thing that should come to mind, when we talk about overlapping subproblems.
The goal of DP is to tell – by looking at an array – that this number is the maximum amount of coins you can get from all the possibilities of removal. One way we can map an array to an integer is by converting the array to a tuple and then creating a dictionary to store the answers for that tuple.
A better way however, is to use bitmasks which can ease out the implementation quite a bit.
In any case, this is the chain of logic we can follow:
- take an array as the input
- pop a balloon – basically, remove an element from the array
- get the score currently => score1 = nums[i-1] * nums[i] * nums[i+1]
- send the remaining array to the same function => score2
- return the total scores = score 1 + score2
And before we jump to the code, let’s quickly talk about the space time complexity. Since we have an array of N elements, storing each and every possible subset means that the time complexity to go over all of those – and then store – will be O(2N).
Well … O(2N) won’t work either, given the constraints. So, what do we do? We know we have to use DP … but how?
1.2. A Smarter DP
We need a perspective change. What if we remove the element, but instead of merging the two subarrays we send them to the same function, individually.
What we used here is called divide and conquer. And since don’t keep a track of the subsets, we are free from the chains of 2^N complexity.
In this approach, we only ever need to keep a track of two pointers, left and right, demarcating the space in which we are computing the answer. Going over all the combinations of left and right give us N^2. Much better!
1.3. An Issue with Divide & Conquer
Divide and Conquer assumes independence between the sub-problems. But is it really the case? What if we pop the balloon c?
We should get a score of
bce … which is clearly dependent on the other sub-problem. So it means that we are at another dead-end!
1.4. Fixing the Issue – A Complete Flip
I have realized this much after solving 200+ LC problems – if a strategy does not work, try flipping it on its own head.
Currently, we look at a balloon to pop in the range L to R (as seen in divide and conquer), then we pop it, get the rewards, and see the consequences of our action play out with new L and R demarcations for the two sub-arrays. But what if … instead of popping the balloon, we save it?
That is, instead of popping the balloon right away, we will say that this balloon gets popped at last, we save it till the very very end.
In that case, for the ith balloon with demarcations as L and R in the array, since i gets popped the last, we get score for the last balloon as
nums[L-1] * i * nums[R+1].
This makes it completely independent of the other sub-problem, thus making this approach work! Let’s see it in action below.
2. Burst Balloons: Optimized Implementation
class Solution: def maxCoins(self, nums: List[int]) -> int: nums =  + nums +  n = len(nums) if n > 1 and len(set(nums)) == 1: return (nums ** 3) * (n - 2) + nums ** 2 + nums @lru_cache(None) def dp(l, r): if l > r: return 0 ans = 0 for i in range(l, r+1): temp = nums[l-1] * nums[i] * nums[r+1] ans = max(ans, temp + dp(l, i-1) + dp(i+1, r)) return ans return dp(1, n-2)
2.1. Complexity Analysis
June 13, 2022
January 24, 2022