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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Burst Balloons

Number: 312

Difficulty: Hard

Paid? No

Companies: Google, Samsung, Amazon, PhonePe, Flipkart, Uber, Cisco, Snap

Problem Description

Given an array of numbers where each number represents a balloon, burst all the balloons to maximize the total number of coins collected. When you burst a balloon at index i, the coins obtained are equal to nums[i - 1] * nums[i] * nums[i + 1]. If an adjacent balloon is out of bounds, treat it as having the value 1. The goal is to determine the maximum coins you can collect by bursting the balloons wisely.

Key Insights

  • Transform the problem by adding virtual balloons with value 1 at both ends to simplify edge handling.
  • Use interval dynamic programming where dp[i][j] represents the maximum coins that can be obtained by bursting all balloons between indices i and j (exclusive).
  • Realize that the order of bursting balloons matters; choose the last balloon to burst in each interval to break dependencies into independent subproblems.
  • The solution involves iterating over all possible intervals and determining the optimal burst order.

Space and Time Complexity

Time Complexity: O(n^3) – Three nested loops: one for the interval length, one for the starting index, and one for the final balloon choice. Space Complexity: O(n^2) – A 2D dynamic programming table is used to store the maximum coins for each interval.

Solution

The problem is solved using interval dynamic programming. First, extend the input array by adding 1 at both ends to handle edge cases seamlessly. Define a dp table where dp[i][j] represents the maximum coins that can be obtained by bursting all the balloons between i and j (not including i and j, as these are the virtual boundaries). For every interval [i, j], iterate through the possible choices for the last balloon k to burst in that interval. The value for bursting balloon k will be determined by the coins from bursting it last (i.e., nums[i] * nums[k] * nums[j]) plus the maximum coins from the two resulting subintervals: (i, k) and (k, j). By filling the dp table in increasing interval lengths, you build up to the solution for the overall interval that covers the entire (extended) array.

Code Solutions

# Define the function to compute maximum coins
def maxCoins(nums):
    # Add virtual balloons with value 1 at both boundaries
    n = len(nums)
    extended = [1] + nums + [1]
    # Initialize dp table with 0's; dimensions: (n+2) x (n+2)
    dp = [[0] * (n + 2) for _ in range(n + 2)]
    
    # Calculate dp values for intervals with length 2 to n+1
    for length in range(2, n + 2):  # interval length from 2 to n+1
        for left in range(0, n + 2 - length):
            right = left + length
            # Iterate through all possible last burst balloons in the interval (left, right)
            for k in range(left + 1, right):
                # Coins when bursting balloon k last in the interval:
                # value from bursting: extended[left] * extended[k] * extended[right]
                # plus coins from subintervals [left, k] and [k, right]
                coins = extended[left] * extended[k] * extended[right] + dp[left][k] + dp[k][right]
                dp[left][right] = max(dp[left][right], coins)
    
    # The final answer is stored in dp[0][n+1] which represents bursting all real balloons.
    return dp[0][n+1]

# Example test cases
print(maxCoins([3,1,5,8]))  # Expected output: 167
print(maxCoins([1,5]))      # Expected output: 10
← Back to All Questions