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

Minimum Number of Arrows to Burst Balloons

Difficulty: Medium

Problem Description

Given a 2D integer array points where points[i] = [x_start, x_end] represents a balloon that stretches horizontally between x_start and x_end, determine the minimum number of arrows that must be shot to burst all the balloons. An arrow can burst a balloon if it is shot vertically at a point x such that x_start <= x <= x_end.

Key Insights

  • The problem can be approached using a greedy algorithm.
  • Sorting the balloons based on their end points allows us to minimize the number of arrows.
  • By shooting an arrow at the end of the first balloon that cannot be burst by the previously shot arrow, we can maximize the number of balloons burst by that arrow.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the balloons based on their end points.
Space Complexity: O(1) - as we are using a constant amount of extra space for variables.

Solution

The solution involves the following steps:

  1. Sort the array of balloons based on their end points.
  2. Initialize a counter for arrows and a variable to track the position of the last shot arrow.
  3. Iterate through the sorted list of balloons:
    • If the current balloon starts after the last shot arrow's position, increment the arrow counter and update the position of the last shot arrow to the end of the current balloon.
  4. Return the total number of arrows used.

This greedy approach ensures that we burst as many balloons as possible with each arrow.

Code Solutions

def findMinArrowShots(points):
    if not points:
        return 0
    
    # Sort the balloons by their end points
    points.sort(key=lambda x: x[1])
    arrows = 1  # Start with one arrow
    last_end = points[0][1]  # End of the first balloon
    
    for start, end in points[1:]:
        # If the current balloon starts after the last arrow's position
        if start > last_end:
            arrows += 1  # Need a new arrow
            last_end = end  # Update to the end of the current balloon
            
    return arrows
← Back to All Questions