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

Minimum Number of Arrows to Burst Balloons

Number: 452

Difficulty: Medium

Paid? No

Companies: Goldman Sachs, TikTok, Amazon, Adobe, Apple, Microsoft

Problem Description

Given a collection of balloons represented as intervals [x_start, x_end] on the x-axis, determine the minimum number of vertical arrows that must be shot (each arrow fired at some x coordinate) to burst all the balloons. An arrow shot at x bursts all balloons for which x_start <= x <= x_end.

Key Insights

  • Sort the balloon intervals by their ending coordinate.
  • Start by shooting an arrow at the end of the first interval.
  • Iterate through the sorted intervals and only shoot a new arrow if the next balloon's start is greater than the position where the last arrow was shot.
  • This greedy approach minimizes arrows by overlapping as many balloons as possible with one arrow.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the intervals. Space Complexity: O(1) additional space if sorting is done in-place (ignoring the input storage).

Solution

The solution uses a greedy algorithm combined with sorting. First, sort the array of balloon intervals based on their x_end values. Initialize the arrow count to 1 with the first arrow shot at the end of the first interval. Then, for each subsequent balloon, check if its x_start is greater than the x position of the last shot arrow. If so, shoot another arrow at the current balloon's end and update the arrow position. This ensures that each arrow covers the maximum number of overlapping balloons.

Code Solutions

def findMinArrowShots(points):
    # If there are no balloons, return 0
    if not points:
        return 0
    
    # Sort the balloons by their end coordinate
    points.sort(key=lambda x: x[1])
    
    # Start with one arrow at the end of the first balloon
    arrows = 1
    current_arrow_position = points[0][1]
    
    # Traverse through each balloon interval
    for x_start, x_end in points:
        # Only shoot a new arrow if the current balloon is not covered by the last arrow
        if x_start > current_arrow_position:
            arrows += 1  # Increment the arrow count
            current_arrow_position = x_end  # Update the arrow position
        
    return arrows

# Example usage:
print(findMinArrowShots([[10,16],[2,8],[1,6],[7,12]]))  # Output: 2
← Back to All Questions