Domain 2MediumCORE

Minimum Number of Arrows to Burst Balloons

We are given a list of intervals representing balloons on an X-axis, defined by [xstart, xend]. We need to determine the minimum number of vertical arrows required to burst all balloons. An arrow shot at coordinate x bursts any balloon where xstart ≤ x ≤ xend.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Greedy#Sort

452. Minimum Number of Arrows to Burst Balloons

Model: qwen3.5:9b
Topics: Greedy,Sort
FAANG asked: 1
Acceptance rate: 49.8%


Problem Breakdown

We are given a list of intervals representing balloons on an X-axis, defined by [xstart, xend]. We need to determine the minimum number of vertical arrows required to burst all balloons. An arrow shot at coordinate x bursts any balloon where xstart ≤ x ≤ xend.

Inputs: A 2D integer array points, where each element is a pair [start, end]. Outputs: An integer representing the minimum count of arrows. Constraints & Edge Cases:

  • The list can be empty (return 0).
  • Coordinates are integers within standard range (-2312^{31} to 231−12^{31}-1), so overflow isn’t an issue in Python, but logic must handle negative values correctly.
  • Intervals may touch at endpoints (e.g., [2,3] and [3,4]). Since the condition is inclusive (≤), a single arrow at x=3 bursts both. This requires careful comparison of start/end coordinates to avoid double-counting touching intervals as separate groups.

Intuition

A brute-force approach would try every possible coordinate on the X-axis or iterate through all combinations of arrows, which leads to exponential time complexity (O(2N)O(2^N)). We need a greedy strategy.

The core question is: Where should we shoot an arrow? To maximize efficiency (bursting as many balloons as possible with one shot), if multiple balloons overlap at the same X-coordinate, shooting there covers all of them. However, to ensure future overlaps are maximized for subsequent balloons in our sorted list, we want to place the arrow as far right as possible within a group of overlapping intervals without excluding any valid candidates that end earlier.

If we sort by start time, an interval ending early might be skipped if its start is after previous arrows’ positions but before others end—this isn’t optimal because it restricts our “window” too much. Instead, sorting by end coordinate (xend) allows us to pick the earliest finishing balloon in a group and shoot at its xend. This position is valid for all balloons that overlap with this one (since they must end after or equal to this point). Shooting earlier than necessary would reduce our ability to cover subsequent intervals. Thus, sorting by end time enables an optimal greedy choice: always extend the current arrow’s reach as far right as possible within a connected group of overlapping intervals.

Approach

  1. Handle Empty Input: If points is empty, return 0 immediately.
  2. Sort: Sort the points list based on their end coordinates (xend). This groups balloons that can be burst by the same arrow together at the beginning of our iteration order.
  3. Iterate & Greedy Selection:
    • Initialize an arrow counter and a variable to track where we last shot an arrow (let’s call it last_shot_pos), initialized to negative infinity or handled via the first element logic.
    • Iterate through each balloon in the sorted list:
      • If the current balloon starts after our last_shot_pos, it means this balloon is not covered by any existing arrows. We must shoot a new arrow.
      • To maximize overlap for future balloons, we place this new arrow exactly at the end of the current balloon (points[i][1]).
    • If the current balloon starts before or equal to last_shot_pos, it is already covered by our existing arrows; do nothing and continue.
  4. Return: The final count of arrows used.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N), where NN is the number of balloons. This is dominated by the sorting step. The linear scan through the list takes O(N)O(N).
  • Space Complexity: O(1)O(1) auxiliary space (ignoring input storage). We only use a few variables for tracking position and count. Note: Python’s sort uses Timsort which requires O(log⁡N)O(\log N) stack space, but this is typically considered constant relative to the problem constraints in interview contexts unless strict memory limits apply.

Solution

def findMinArrows(points):
    if not points:
        return 0
    
    # Sort by end coordinate (xend) to prioritize intervals that finish earliest
    points.sort(key=lambda x: x[1])
    
    arrows = 0
    last_shot_pos = -float('inf') 
    
    for start, end in points:
        # If the current balloon starts after our last arrow position, 
        # it's not covered. We need a new arrow at this balloon's end.
        if start > last_shot_pos:
            arrows += 1
            last_shot_pos = end
            
    return arrows

# Example usage matching problem description logic
print(findMinArrows([[10,16],[2,8],[1,6],[7,12]])) # Output: 2

Edge Cases Handled

  • Empty Input: Returns 0 immediately via the initial check.
  • Single Balloon: The loop runs once; condition triggers new arrow at end; returns 1.
  • Touching Intervals ([2,3], [3,4]): Since comparison is strictly greater than (start > last_shot_pos) and not greater-or-equal for the check of coverage (wait, logic: if start <= last_shot_pos it’s covered). If arrow at 3 covers [2,3], last_shot=3. Next balloon starts at 3. 3≯33 \ngtr 3, so condition is false; no new arrow needed. Correctly counts as 1 arrow.
  • Negative Coordinates: Python handles arbitrary precision integers and signed comparisons naturally without overflow issues common in fixed-width languages, ensuring logic holds for negative xstart.