Jobs

Interviews

Discussions

Burst Balloons

Hard

Samsung

0 views

Topics:

ArraysDynamic Programming

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.

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

Burst Balloons

Hard

Samsung

0 views

Topics:

ArraysDynamic Programming

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.

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the balloon numbers? Can they be negative or zero?
What is the maximum number of balloons, i.e., the maximum size of the input array?
If the input array is empty or contains only one balloon, what should I return?
Is the goal to maximize the total coins earned, or is there some other objective?
If there are multiple ways to achieve the maximum coins, is any one of them acceptable, or is there a preferred order or strategy for bursting the balloons?

Brute Force Solution

Approach

Imagine you have a row of balloons, and you want to maximize your score by bursting them. The brute force strategy involves trying every single possible order of bursting the balloons and calculating the score for each order.

Here's how the algorithm would work step-by-step:

First, consider bursting the first balloon. Calculate the score for doing that, and remember what the remaining balloons are.
Then, consider bursting the second balloon first, and so on, until you've considered bursting each balloon first.
For each of those initial choices, consider all the possible ways to burst the remaining balloons. This means choosing another balloon from what's left, calculating the score based on that choice, and remembering the balloons that are still unburst.
Keep repeating this process of choosing a balloon to burst and calculating the score, until you've burst all the balloons in every possible order.
For each complete order of bursting the balloons, you'll have a total score. Compare all these total scores to find the highest one.
The highest score you find is the best possible score you can get by bursting the balloons.

Code Implementation

def burst_balloons_brute_force(balloons):
    def calculate_max_score(remaining_balloons):
        # If no balloons left, score is zero
        if not remaining_balloons:
            return 0

        maximum_score = 0

        # Try bursting each balloon in the remaining list
        for index_to_burst in range(len(remaining_balloons)):
            current_score = 0

            # Calculate score for bursting this balloon
            left_value = 1
            if index_to_burst > 0:
                left_value = remaining_balloons[index_to_burst - 1]

            right_value = 1
            if index_to_burst < len(remaining_balloons) - 1:
                right_value = remaining_balloons[index_to_burst + 1]

            current_score = left_value * remaining_balloons[index_to_burst] * right_value

            # Create new list of remaining balloons after bursting
            next_balloons = remaining_balloons[:index_to_burst] + remaining_balloons[index_to_burst+1:]

            # Recursively calculate score for remaining balloons
            remaining_score = calculate_max_score(next_balloons)

            total_score = current_score + remaining_score
            maximum_score = max(maximum_score, total_score)

        return maximum_score

    return calculate_max_score(balloons)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n!) – The provided brute force approach involves considering every possible order of bursting the n balloons. There are n! (n factorial) possible permutations or orderings of bursting the balloons. For each of these permutations, we calculate the score, which takes O(n) time to iterate through each of the n balloons in the permutation. Therefore, the overall time complexity is O(n * n!), which simplifies to O(n!). The factorial component dominates the linear factor.

Space Complexity

O(N!) – The brute force approach explores every possible order of bursting the balloons. The recursion depth goes up to N, where N is the number of balloons. At each level of recursion, we create a copy of the remaining balloons (a list of size at most N) to pass to the next recursive call. The call stack can have a depth of N, and each call might hold a list of size N, but the dominant factor is the exploration of permutations. The total number of permutations (and thus recursive calls and associated data structures) can reach N! in the worst-case scenario. Therefore, the space complexity is O(N!).

Optimal Solution

Approach

The best way to solve this balloon problem is to think backward. Instead of figuring out which balloon to burst first, we figure out which balloon should be burst *last* to maximize the points.

Here's how the algorithm would work step-by-step:

Imagine the balloons are still there, even if you've virtually burst them.
Find the balloon that, if burst last, would give you the highest score based on its neighbors.
Calculate the score you'd get for bursting that balloon last.
Now, pretend that balloon is gone and repeat the process for the remaining balloons: find the balloon that, if burst *second to last*, would give you the highest score considering its remaining neighbors.
Keep doing this until you're down to just two balloons and figure out which one to burst next to last.
Finally, burst the last balloon and add that score.
By always choosing the balloon that gives the best score when burst at the *end* of the process, you ensure you're maximizing your overall score.

Code Implementation

def burst_balloons(balloons):
    number_of_balloons = len(balloons)
    # Pad balloons to handle edge cases neatly
    padded_balloons = [1] + balloons + [1]
    
    # DP table to store maximum coins
    dp_table = [[0] * (number_of_balloons + 2) for _ in range(number_of_balloons + 2)]

    # Iterate through subproblems of increasing length
    for length in range(2, number_of_balloons + 2):
        for left in range(number_of_balloons + 2 - length):
            right = left + length
            
            # Find the last balloon to burst in this range
            for last_burst in range(left + 1, right):
                # Calculate coins earned by bursting 'last_burst' last
                coins = padded_balloons[left] * padded_balloons[last_burst] * padded_balloons[right]
                coins += dp_table[left][last_burst] + dp_table[last_burst][right]
                # Store the maximum coins for this range
                dp_table[left][right] = max(dp_table[left][right], coins)

    return dp_table[0][number_of_balloons + 1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm considers each balloon as the last balloon to be burst. This involves iterating through all n balloons. For each of these balloons, we need to determine the maximum score obtainable by bursting the remaining balloons. This 'remaining balloons' problem is solved recursively by considering each of the remaining balloons as the second-to-last balloon and so on. In the worst case, this results in a recursive call for each of the remaining balloons, leading to approximately n recursive calls at each level. The depth of recursion will be proportional to n, leading to an overall time complexity of O(n^3).

Space Complexity

O(N^2) – The described solution inherently implies a dynamic programming approach to find the optimal bursting order. This would involve storing the maximum scores achievable for bursting balloon subranges. Thus, a 2D array (or similar data structure) of size N x N is required, where N is the number of balloons, to memoize these intermediate results. The space required grows quadratically with the number of balloons. Therefore, the auxiliary space complexity is O(N^2).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty to avoid null pointer exceptions and handle the base case of no balloons.
Array with a single balloon	Return the value of the single balloon as the maximum coins obtainable.
Array with two balloons	Return the product of the two balloons plus their values multiplied by the implicit 1 on each end.
Array with all identical balloon values	The algorithm should still find the optimal burst order, although multiple optimal solutions might exist; the dynamic programming approach will handle this case correctly.
Large array size potentially leading to recursion depth issues or memory limitations in dynamic programming table	The bottom-up dynamic programming approach avoids excessive recursion depth and should be implemented to fit within memory constraints for the maximum allowed input size.
Input array contains zero values	Zero values should be handled correctly by the multiplication operations in the algorithm, not leading to incorrect results.
Input array contains negative values or extreme positive values, potentially leading to integer overflow during multiplication	Use a larger integer data type (e.g., long) to store intermediate multiplication results to prevent integer overflow.
The optimal bursting order causes index out of bounds errors if not handled correctly.	Pad the input array with 1s on both ends to represent implicit boundary balloons and simplify boundary condition checking.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values for the balloon numbers? Can they be negative or zero?
What is the maximum number of balloons, i.e., the maximum size of the input array?
If the input array is empty or contains only one balloon, what should I return?
Is the goal to maximize the total coins earned, or is there some other objective?
If there are multiple ways to achieve the maximum coins, is any one of them acceptable, or is there a preferred order or strategy for bursting the balloons?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, consider bursting the first balloon. Calculate the score for doing that, and remember what the remaining balloons are.
Then, consider bursting the second balloon first, and so on, until you've considered bursting each balloon first.
For each of those initial choices, consider all the possible ways to burst the remaining balloons. This means choosing another balloon from what's left, calculating the score based on that choice, and remembering the balloons that are still unburst.
Keep repeating this process of choosing a balloon to burst and calculating the score, until you've burst all the balloons in every possible order.
For each complete order of bursting the balloons, you'll have a total score. Compare all these total scores to find the highest one.
The highest score you find is the best possible score you can get by bursting the balloons.

Code Implementation

def burst_balloons_brute_force(balloons):
    def calculate_max_score(remaining_balloons):
        # If no balloons left, score is zero
        if not remaining_balloons:
            return 0

        maximum_score = 0

        # Try bursting each balloon in the remaining list
        for index_to_burst in range(len(remaining_balloons)):
            current_score = 0

            # Calculate score for bursting this balloon
            left_value = 1
            if index_to_burst > 0:
                left_value = remaining_balloons[index_to_burst - 1]

            right_value = 1
            if index_to_burst < len(remaining_balloons) - 1:
                right_value = remaining_balloons[index_to_burst + 1]

            current_score = left_value * remaining_balloons[index_to_burst] * right_value

            # Create new list of remaining balloons after bursting
            next_balloons = remaining_balloons[:index_to_burst] + remaining_balloons[index_to_burst+1:]

            # Recursively calculate score for remaining balloons
            remaining_score = calculate_max_score(next_balloons)

            total_score = current_score + remaining_score
            maximum_score = max(maximum_score, total_score)

        return maximum_score

    return calculate_max_score(balloons)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The best way to solve this balloon problem is to think backward. Instead of figuring out which balloon to burst first, we figure out which balloon should be burst *last* to maximize the points.

Here's how the algorithm would work step-by-step:

Imagine the balloons are still there, even if you've virtually burst them.
Find the balloon that, if burst last, would give you the highest score based on its neighbors.
Calculate the score you'd get for bursting that balloon last.
Now, pretend that balloon is gone and repeat the process for the remaining balloons: find the balloon that, if burst *second to last*, would give you the highest score considering its remaining neighbors.
Keep doing this until you're down to just two balloons and figure out which one to burst next to last.
Finally, burst the last balloon and add that score.
By always choosing the balloon that gives the best score when burst at the *end* of the process, you ensure you're maximizing your overall score.

Code Implementation

def burst_balloons(balloons):
    number_of_balloons = len(balloons)
    # Pad balloons to handle edge cases neatly
    padded_balloons = [1] + balloons + [1]
    
    # DP table to store maximum coins
    dp_table = [[0] * (number_of_balloons + 2) for _ in range(number_of_balloons + 2)]

    # Iterate through subproblems of increasing length
    for length in range(2, number_of_balloons + 2):
        for left in range(number_of_balloons + 2 - length):
            right = left + length
            
            # Find the last balloon to burst in this range
            for last_burst in range(left + 1, right):
                # Calculate coins earned by bursting 'last_burst' last
                coins = padded_balloons[left] * padded_balloons[last_burst] * padded_balloons[right]
                coins += dp_table[left][last_burst] + dp_table[last_burst][right]
                # Store the maximum coins for this range
                dp_table[left][right] = max(dp_table[left][right], coins)

    return dp_table[0][number_of_balloons + 1]

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty to avoid null pointer exceptions and handle the base case of no balloons.
Array with a single balloon	Return the value of the single balloon as the maximum coins obtainable.
Array with two balloons	Return the product of the two balloons plus their values multiplied by the implicit 1 on each end.
Array with all identical balloon values	The algorithm should still find the optimal burst order, although multiple optimal solutions might exist; the dynamic programming approach will handle this case correctly.
Large array size potentially leading to recursion depth issues or memory limitations in dynamic programming table	The bottom-up dynamic programming approach avoids excessive recursion depth and should be implemented to fit within memory constraints for the maximum allowed input size.
Input array contains zero values	Zero values should be handled correctly by the multiplication operations in the algorithm, not leading to incorrect results.
Input array contains negative values or extreme positive values, potentially leading to integer overflow during multiplication	Use a larger integer data type (e.g., long) to store intermediate multiplication results to prevent integer overflow.
The optimal bursting order causes index out of bounds errors if not handled correctly.	Pad the input array with 1s on both ends to represent implicit boundary balloons and simplify boundary condition checking.