312. Burst Balloons - Explanation

Description

You are given an array of integers nums of size n. The ith element represents a balloon with an integer value of nums[i]. You must burst all of the balloons.

If you burst the ith balloon, you will receive nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then assume the out of bounds value is 1.

Return the maximum number of coins you can receive by bursting all of the balloons.

Example 1:

Input: nums = [4,2,3,7]

Output: 143

Explanation:
nums = [4,2,3,7] --> [4,3,7] --> [4,7] --> [7] --> []
coins =  4*2*3    +   4*3*7   +  1*4*7  + 1*7*1 = 143

Constraints:

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

Recommended Time & Space Complexity

You should aim for a solution with O(n ^ 3) time and O(n ^ 2) space, where n is the size of the input array.

Hint 1

Try to simulate the process recursively by passing the array to the recursive function. At each step, iterate through the array, pop an element, and recursively apply the same process to the two subarrays on both sides of the popped element, returning the maximum result from all recursive paths. This approach is exponential. Can you think of a way to optimize it? Maybe you should consider observing the subproblems instead of modifying the array.

Hint 2

Instead of passing the array, we can pass the range of indices l and r that need to be processed. We pad the input array with 1s on both sides for easier computation, but l and r represent the first and last indices of the original input array. Can you think of a reverse engineering approach for popping elements?

Hint 3

We determine the result by considering each element as the last one to be popped in the current range. For each element, we calculate its value by multiplying it with the elements at l - 1 and r + 1, then recursively solve the subproblems for the ranges (l, i - 1) and (i + 1, r), where i is the current element in the given range. Can you think of a way to optimize and avoid redundant calculations?

Hint 4

We can use memoization to cache the results of recursive calls and avoid redundant calculations. A hash map or a 2D array can be used to store results since the recursive function parameters l and r are within the range of the input array size.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force (Recursion)

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]

        def dfs(nums):
            if len(nums) == 2:
                return 0

            maxCoins = 0
            for i in range(1, len(nums) - 1):
                coins = nums[i - 1] * nums[i] * nums[i + 1]
                coins += dfs(nums[:i] + nums[i + 1:])
                maxCoins = max(maxCoins, coins)
            return maxCoins

        return dfs(nums)

Time & Space Complexity

Time complexity: $O(n*2^n)$
Space complexity: $O(n*2^n)$

2. Dynamic Programming (Top-Down)

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        dp = {}
        def dfs(l, r):
            if l > r:
                return 0
            if (l, r) in dp:
                return dp[(l, r)]

            dp[(l, r)] = 0
            for i in range(l, r + 1):
                coins = nums[l - 1] * nums[i] * nums[r + 1]
                coins += dfs(l, i - 1) + dfs(i + 1, r)
                dp[(l, r)] = max(dp[(l, r)], coins)
            return dp[(l, r)]

        return dfs(1, len(nums) - 2)

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

class Solution:
    def maxCoins(self, nums):
        n = len(nums)
        new_nums = [1] + nums + [1]

        dp = [[0] * (n + 2) for _ in range(n + 2)]
        for l in range(n, 0, -1):
            for r in range(l, n + 1):
                for i in range(l, r + 1):
                    coins = new_nums[l - 1] * new_nums[i] * new_nums[r + 1]
                    coins += dp[l][i - 1] + dp[i + 1][r]
                    dp[l][r] = max(dp[l][r], coins)

        return dp[1][n]

Time & Space Complexity

Time complexity: $O(n^3)$
Space complexity: $O(n^2)$