Bursting Balloons

Leetcode Problem #312 (Hard)

Published in

Algorithms Digest

6 min readApr 8, 2021

Introduction

This blog post covers the Bursting Balloons problem on Leetcode. It is a dynamic programming problem in which coming up with the sub-problem definition is hard.
Instead of directly explaining the solution, this post goes through the thought process of formulating the DP solution in a step-by-step manner.

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.

Let’s look at an example to understand this.
Input: nums = {5, 2, 4, 9}

There are multiple sequences in which we may burst the balloons.
Say we burst the balloons in this order: [2, 4, 9, 5]. This is what the steps would look like.

However, the optimal sequence (to maximize coins collected) would be [2, 4, 5, 9]. The steps for this would look like this:

Thought Process / Intuition

GREEDY VS DP

This is an optimization problem (coin maximization) and we’re trying to select the best ordering. This is usually a hint that we need a greedy or DP algorithm.

Some greedy strategies could be:

Burst the balloon which maximizes the coins collected that step.
Doesn’t work for {2, 9, 2}. Greedy solution (9, 2, 2) gives 42 coins whereas we can get 45 coins with (2, 2, 9).
Burst the smallest balloon since that allows the bigger numbers to be utilized multiple times.
Doesn’t work for {2, 3, 4}. Greedy solution (2, 3, 4) gives 22 coins whereas we can get 36 coins with (3, 2, 4).

This preliminary check is no guarantee that a greedy solution doesn’t exist. But since these ones don’t work, we are tempted to consider a DP solution.

DP FORMULATION

To formulate a DP algorithm, we must think about what the sub-problems should be and how they can be recursively computed.

From experience, the sub-problems for arrays are subsets of the array.

The recursive relationship can be figured out by thinking about the choices we make to construct our solution.
In this case, we burst balloons, so the choice could be ‘Which balloon is burst first?’ or ‘Which balloon is burst last?’.

We’ve got a basic idea. Let’s dig deeper!
We’ll start with a simple approach, see its limitations and modify it step by step to solve our problem.

Idea 1: Define the sub-problems with a 1D array (DP[]) where DP[i] represents the optimal solution for the sub-array nums[0...i] and the recursive structure is based on what balloon we burst first.

To compute DP[i], we should iterate over the different choices we can make and choose the best one. But notice that while computing DP[i], if we burst the balloon at index j , the resulting array cannot be represented by any of our subproblems (see below figure). In other words, balloon j-1 and balloon j+1 are dependent on each other (for calculating the profit) and so the array is not split into independent sub-problems.

This clearly won’t work.

Idea 2: Instead, suppose that the recursive structure is based on which balloon is burst last. While computing DP[i], if the balloon at index j is burst last, we need to deal with the two parts that the balloons have been divided into.

This cannot be done with the current sub-problem definition since it doesn’t represent the array [(j+1)…(n-1)]. To deal with this, our subproblems need to represent subarrays between any two indices.

Idea 3:
Let’s say that DP[i,j] represents the maximum coins collected by considering balloons[i…j].
If the balloon at index k is the last one to burst, it means we need to first burst all balloons [i…(k-1)] and [(k+1)…j] and then burst the balloon at index k. This would give us DP[i][k-1] + DP[k+1][j] + (Coins on bursting balloon at index k).
Do you see the problem with this?

We are computing DP[i][k-1] and DP[k+1][j]without considering the balloon at index k. Let’s try to deal with this by modifying the definition of DP[i,j].

Idea 4: Let DP[i,j] represent the maximum coins collected by bursting balloons [(i+1)…(j-1)] i.e. we DO NOT burst the balloons on the extreme left and right.

Now, when we burst the balloon at index k, we can get:

DP[i,k] (Maximum coins collected by bursting balloons[(i+1)…(k-1)])+
DP[k,j] (Maximum coins collected by bursting balloons[(k+1)…(j-1)])+
nums[i]*nums[k]*nums[j] (Coins collected on bursting the index k balloon (it’s surrounded by balloons i and j when everything else in between has been burst)).

Notice how by keeping the left-most and right-most balloon untouched we circumvent the dependency on balloons outside our range.

To solve the original problem, we can assume that the original balloons are surrounded by balloons with value 1 on the left and right as this doesn’t change the answer in any way.
So, we create an array A[] = {1, nums[0], nums[1], …, nums[n-1], 1} (as shown below) of size n+2 over which we apply the DP algorithm described above.

Adding balloons with value 1 on the extreme left and right.

Our final answer will be DP[0, n+1].

Algorithm

To summarise the discussion above:

Define A[] = {1, nums[0], nums[1], …, nums[n-1], 1} of size (n+2). Let these represent the balloons.
Define DP[n+2][n+2] such that DP[i][j] (j > i) represents the maximum coins collected by bursting balloons [(i+1)…(j-1)].
(Base Case) DP[i][i+1] = 0 because we have no ballons to burst.
DP[i][j] = Max ( DP[i][k] + DP[k][j] + (nums[i]*nums[k]*nums[j]), (i+1)≤ k ≤ (j-1) ).
Final answer is DP[0,n+1].

Runtime Analysis

Our 2D DP table has O(N²) entries. To compute each entry, we are looking at all the possible choices for the last balloon to be burst and taking the maximum one. There are O(N) choices in the worst case at each step and for each choice computing the coins collected is an O(1) operation.
Thus, computing each entry of DP[][] takes O(N) * O(1) = O(N) time.
Hence, the overall runtime is O(N²) x O(N) = O(N³).

Please endorse the article and let me know in the comments if this explanation helped you understand the problem better. Would love to hear any feedback/suggestions/edits as well.

Can’t get enough of DP? Check out these articles.