Scale Engineer

Burst Balloons

Hard
#0299Time: Exponential, roughly `O(n * C_n)` where `C_n` is the n-th Catalan number. This is because the recursion tree branches extensively, leading to a number of calls that grows exponentially with `n`.Space: `O(n)` for the recursion call stack depth.5 companies
Patterns
Dynamic Programming
Data structures
Array
Companies
FlipkartSamsungSnapPhonePe

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

The problem can be reframed by thinking about the last balloon to be burst in a given range. A brute-force recursive approach can be designed based on this idea. For any range of balloons, we try every balloon as the last one to burst, calculate the coins, and recursively solve the subproblems on its left and right. This method explores all possibilities but is highly inefficient due to redundant calculations.

Algorithm

  • Pad the nums array with 1s at both ends to create new_nums.
  • Define a recursive function solve(left, right).
  • Base Case: If left + 1 >= right, return 0.
  • Initialize max_coins = 0.
  • Loop k from left + 1 to right - 1:
    • Calculate 
      current_coins = new_nums[left] * new_nums[k] * new_nums[right] + solve(left, k) + solve(k, right)
      .
    • Update max_coins = max(max_coins, current_coins).
  • Return max_coins.
  • The final answer is solve(0, n + 2).

Walkthrough

The core idea is to not think about which balloon to burst first, but which to burst last. If we decide balloon k is the last one to burst in an interval (left, right), all other balloons in this interval must have been burst already. This means its neighbors are the boundary balloons at left and right. The coins gained from this last burst are nums[left] * nums[k] * nums[right]. The total coins would be this value plus the maximum coins from bursting all balloons in (left, k) and (k, right) independently.

This naturally leads to a recursive solution. We define a function solve(left, right) that computes the maximum coins from bursting all balloons between indices left and right (exclusive). To handle boundary conditions gracefully, we pad the original nums array with 1s at both ends.

The function iterates through all possible k as the last balloon to burst in (left, right) and recursively calls itself for the sub-ranges (left, k) and (k, right). The maximum value over all choices of k is the result for solve(left, right).

class Solution {    public int maxCoins(int[] nums) {        int n = nums.length;        // Create a new array with virtual balloons (value 1) at the boundaries.        int[] newNums = new int[n + 2];        newNums[0] = 1;        newNums[n + 1] = 1;        for (int i = 0; i < n; i++) {            newNums[i + 1] = nums[i];        }        // The problem is now to find the max coins for the range (0, n+1).        return solve(newNums, 0, n + 1);    }     private int solve(int[] nums, int left, int right) {        // Base case: If there are no balloons to burst, return 0 coins.        if (left + 1 >= right) {            return 0;        }         int maxCoins = 0;        // Iterate through each balloon 'k' in the range (left, right)        // and consider it as the last one to be burst.        for (int k = left + 1; k < right; k++) {            // Coins from bursting 'k' last.            int currentCoins = nums[left] * nums[k] * nums[right];            // Add coins from recursively solving the subproblems.            currentCoins += solve(nums, left, k) + solve(nums, k, right);            // Update the maximum coins found so far.            maxCoins = Math.max(maxCoins, currentCoins);        }        return maxCoins;    }}

Complexity

Time

Exponential, roughly `O(n * C_n)` where `C_n` is the n-th Catalan number. This is because the recursion tree branches extensively, leading to a number of calls that grows exponentially with `n`.

Space

`O(n)` for the recursion call stack depth.

Trade-offs

Pros

  • Conceptually simple if you reframe the problem correctly.

Cons

  • Extremely inefficient due to massive redundant computations.

  • Will result in a 'Time Limit Exceeded' error on most platforms for non-trivial inputs.

Solutions

class Solution { public int maxCoins ( int [] nums ) { int [] vals = new int [ nums . length + 2 ]; vals [ 0 ] = 1 ; vals [ vals . length - 1 ] = 1 ; System . arraycopy ( nums , 0 , vals , 1 , nums . length ); int n = vals . length ; int [][] dp = new int [ n ][ n ]; for ( int l = 2 ; l < n ; ++ l ) { for ( int i = 0 ; i + l < n ; ++ i ) { int j = i + l ; for ( int k = i + 1 ; k < j ; ++ k ) { dp [ i ][ j ] = Math . max ( dp [ i ][ j ], dp [ i ][ k ] + dp [ k ][ j ] + vals [ i ] * vals [ k ] * vals [ j ]); } } } return dp [ 0 ][ n - 1 ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem