We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Burst Balloons

Difficulty: Hard

Problem Description

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 i-th 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.

Key Insights

  • The problem can be solved using Dynamic Programming to find the optimal order of bursting balloons.
  • By treating bursting a balloon as an interval problem, we can calculate the maximum coins for subproblems.
  • The idea is to use a DP table where dp[left][right] represents the maximum coins that can be collected by bursting all balloons between indices left and right.

Space and Time Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Solution

The approach is based on dynamic programming. We will define a DP table where dp[left][right] represents the maximum coins obtainable by bursting all balloons between the indices left and right (exclusive). The main idea is to iterate over all possible subarrays of balloons and calculate the maximum coins that can be collected by bursting one balloon at a time in that range. We will also consider the coins earned from the adjacent balloons. The final result will be in dp[0][n-1].

Code Solutions

def maxCoins(nums):
    # Add 1 to both ends of the nums array
    nums = [1] + nums + [1]
    n = len(nums)
    
    # Create a 2D DP array initialized to 0
    dp = [[0] * n for _ in range(n)]
    
    # Iterate over the length of the interval
    for length in range(2, n):
        for left in range(n - length):
            right = left + length
            for i in range(left + 1, right):
                # Calculate coins for bursting balloon i
                coins = nums[left] * nums[i] * nums[right]
                # Add coins from subproblems
                dp[left][right] = max(dp[left][right], dp[left][i] + dp[i][right] + coins)
    
    return dp[0][n - 1]
← Back to All Questions