# Burst Balloons
**Difficulty:** HARD
[External](https://leetcode.com/problems/burst-balloons)
Canonical: https://scaleengineer.com/dsa/problems/burst-balloons
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Samsung](https://scaleengineer.com/companies/samsung), [Snap](https://scaleengineer.com/companies/snap), [PhonePe](https://scaleengineer.com/companies/phonepe), [QBurst](https://scaleengineer.com/companies/qburst)
---
## Problem
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
## Brute Force Recursion
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.
**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.
**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.
### Explanation
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 `1`s 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)`.

```java
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;
    }
}
```
### Algorithm
- Pad the `nums` array with `1`s 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)`.

## Recursion with Memoization (Top-Down DP)
This approach optimizes the brute-force recursion by using memoization, a dynamic programming technique. It avoids re-calculating results for the same subproblems by storing them in a cache (a 2D array). When the function is called with a pair of `(left, right)` indices that have been solved before, it returns the cached result instantly.
**Time:** `O(n^3)`. There are `O(n^2)` possible states `(left, right)`. Each state takes `O(n)` time to compute due to the loop for `k`. With memoization, each state is computed only once. · **Space:** `O(n^2)`. `O(n^2)` for the memoization table and `O(n)` for the recursion stack. The table dominates.
**Pros:** Significantly faster than brute-force recursion.; Acceptable performance for the given constraints.; Maintains the logical flow of the recursive solution.
**Cons:** Can cause a stack overflow for very large `n` (not an issue for `n <= 300`).; Slightly more memory usage than the bottom-up approach due to the recursion stack.
### Explanation
The recursive structure remains the same as the brute-force approach. The key difference is the addition of a 2D array, `memo`, to store the results of subproblems `solve(left, right)`. Before computing the result for a given `(left, right)` pair, we first check if it's already in our `memo` table. If it is, we return the stored value. If not, we compute it as before, but before returning, we store the result in `memo[left][right]` for future use. This simple addition drastically reduces the number of computations from exponential to polynomial.

```java
class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        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];
        }

        // Memoization table, initialized to 0 (since coins are non-negative)
        int[][] memo = new int[n + 2][n + 2];
        return solve(newNums, 0, n + 1, memo);
    }

    private int solve(int[] nums, int left, int right, int[][] memo) {
        if (left + 1 >= right) {
            return 0;
        }
        // If result is already computed, return it.
        if (memo[left][right] != 0) {
            return memo[left][right];
        }

        int maxCoins = 0;
        for (int k = left + 1; k < right; k++) {
            int currentCoins = nums[left] * nums[k] * nums[right];
            currentCoins += solve(nums, left, k, memo) + solve(nums, k, right, memo);
            maxCoins = Math.max(maxCoins, currentCoins);
        }
        
        // Store the result before returning.
        memo[left][right] = maxCoins;
        return maxCoins;
    }
}
```
### Algorithm
- Pad the `nums` array with `1`s at both ends.
- Create a 2D `memo` array of size `(n+2)x(n+2)` and initialize it with a value indicating 'not computed' (e.g., 0).
- Define a recursive function `solve(left, right, memo)`.
- Base Case: If `left + 1 >= right`, return 0.
- Memoization Check: If `memo[left][right]` is computed, return it.
- 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, memo) + solve(k, right, memo)`.
    - Update `max_coins = max(max_coins, current_coins)`.
- Store `max_coins` in `memo[left][right]`.
- Return `max_coins`.
- The final answer is `solve(0, n + 2, memo)`.

## Tabulation (Bottom-Up Dynamic Programming)
This is the most efficient approach, implementing the dynamic programming solution iteratively. It eliminates recursion entirely. We use a 2D DP table, `dp[left][right]`, to store the maximum coins for bursting balloons in the interval `(left, right)`. The table is filled by iterating through intervals of increasing length, ensuring that when we compute `dp[left][right]`, the solutions for all smaller subproblems (like `dp[left][k]` and `dp[k][right]`) have already been computed.
**Time:** `O(n^3)`. There are three nested loops, each iterating up to `n` times. · **Space:** `O(n^2)` for the DP table.
**Pros:** Most efficient time complexity for this problem.; Avoids recursion overhead and potential stack overflow.; Iterative nature can sometimes be easier to debug.
**Cons:** The loop structure can be less intuitive to come up with compared to the direct recursive translation.
### Explanation
The bottom-up approach systematically solves subproblems of increasing size. We iterate through the length of the balloon interval, `len`, from 2 up to `n+2`. For each length, we iterate through all possible starting positions `left`. The `right` boundary is then `left + len`.

For each interval `(left, right)`, we calculate the maximum coins by trying every balloon `k` within it as the last one to burst. The formula remains the same: `coins = new_nums[left] * new_nums[k] * new_nums[right] + dp[left][k] + dp[k][right]`. Since we are iterating by increasing `len`, the values `dp[left][k]` and `dp[k][right]` correspond to smaller intervals and are guaranteed to be already computed. The final answer is stored in `dp[0][n+1]`.

```java
class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        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];
        }

        int m = n + 2;
        int[][] dp = new int[m][m];

        // len is the distance between left and right boundaries
        for (int len = 2; len < m; len++) {
            // left is the starting boundary
            for (int left = 0; left < m - len; left++) {
                int right = left + len;
                // k is the last balloon to burst in (left, right)
                for (int k = left + 1; k < right; k++) {
                    int currentCoins = newNums[left] * newNums[k] * newNums[right];
                    currentCoins += dp[left][k] + dp[k][right];
                    dp[left][right] = Math.max(dp[left][right], currentCoins);
                }
            }
        }
        // The result for the entire range (0, m-1)
        return dp[0][m - 1];
    }
}
```
### Algorithm
- Pad the `nums` array with `1`s at both ends to create `new_nums` of size `m = n + 2`.
- Create a 2D `dp` table of size `m x m`, initialized to 0.
- Loop for `len` from 2 to `m - 1` (the length of the interval).
-   Loop for `left` from 0 to `m - 1 - len` (the start of the interval).
-     Calculate `right = left + len`.
-     Loop for `k` from `left + 1` to `right - 1` (the last balloon to burst).
-       Calculate `coins = new_nums[left] * new_nums[k] * new_nums[right] + dp[left][k] + dp[k][right]`.
-       Update `dp[left][right] = max(dp[left][right], coins)`.
- Return `dp[0][m - 1]`.

# Solutions
### Java

```java
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 ]; } }
```

### CPP

```cpp
class Solution { public: int maxCoins ( vector < int >& nums ) { nums . insert ( nums . begin (), 1 ); nums . push_back ( 1 ); int n = nums . size (); vector < vector < int >> dp ( n , vector < int > ( 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 ] = max ( dp [ i ][ j ], dp [ i ][ k ] + dp [ k ][ j ] + nums [ i ] * nums [ k ] * nums [ j ]); } } } return dp [ 0 ][ n - 1 ]; } };
```

### Python

```python
class Solution : def maxCoins ( self , nums : List [ int ]) -> int : nums = [ 1 ] + nums + [ 1 ] n = len ( nums ) dp = [[ 0 ] * n for _ in range ( n )] for l in range ( 2 , n ): for i in range ( n - l ): j = i + l for k in range ( i + 1 , j ): dp [ i ][ j ] = max ( dp [ i ][ j ], dp [ i ][ k ] + dp [ k ][ j ] + nums [ i ] * nums [ k ] * nums [ j ] ) return dp [ 0 ][ - 1 ]
```