Minimum Number of Arrows to Burst Balloons (LeetCode 452)

The problem

Each balloon spans a horizontal range [start, end]. An arrow shot straight up at position x bursts every balloon with start <= x <= end. Return the minimum number of arrows needed to burst all of them.

Input:  [[10, 16], [2, 8], [1, 6], [7, 12]]
Output: 2

An arrow at x = 6 bursts [1, 6] and [2, 8]. An arrow at x = 12 bursts [7, 12] and [10, 16].

How to think about it

Start with brute force. Try arrow positions at every balloon end and search over combinations. That blows up quickly. Even a simpler “shoot where most balloons overlap, repeat” greedy is O(n²) and not always optimal.

The key insight: the balloon that ends first decides the first arrow. Some arrow must hit the balloon with the earliest end, and it must be at or before that end. Shooting exactly at that end is never worse than shooting earlier: it still hits that balloon, and it hits every other balloon that has started by then. So sort by end, shoot at the first end, and skip every balloon that starts at or before that point.

Fire a new arrow only when a balloon starts after the last shot. That balloon cannot be hit by the previous arrow, so it needs a new one, placed at its own end. This is the same greedy as Non-overlapping Intervals: the number of arrows equals the number of intervals you would keep there (with touching counted as overlapping).

Which pattern is this? Intervals with a greedy choice by end time. The tell is “minimum number of points that stab all intervals”.

Approach

1. Sort balloons by end.
2. Fire the first arrow at the first balloon’s end: arrows = 1, end = points[0][1].
3. For each later balloon [s, e]: if s > end, it is not hit, so arrows += 1 and end = e.
4. Return arrows.

Solution

def find_min_arrows(points):
    points.sort(key=lambda x: x[1])         # earliest end first
    arrows = 1; end = points[0][1]          # first arrow at the first end
    for s, e in points[1:]:
        if s > end:                         # starts after the last shot: missed
            arrows += 1; end = e            # new arrow at this balloon's end
    return arrows
# find_min_arrows([[10,16],[2,8],[1,6],[7,12]]) -> 2

Dry run

Sorted by end: [[1, 6], [2, 8], [7, 12], [10, 16]].

The answer is 2.

Complexity

• Time: O(n log n). Sorting dominates; the sweep is O(n).
• Space: O(1) extra. Sorted in place, two variables.

Edge cases and pitfalls

• Touching balloons share an arrow. [[1, 2], [2, 3]] needs 1 arrow at x = 2, so the test is s > end, not s >= end. This is the one difference from LeetCode 435.
• Empty input would crash on points[0]. LeetCode guarantees at least one balloon; add if not points: return 0 otherwise.
• Sorting by start without tracking the minimum end gives too few arrows for nested balloons.
• Overflow: coordinates go up to ±2³¹. Python is fine, but in Java, comparing with a[1] - b[1] in a comparator overflows; use Integer.compare.

Related problems

• Non-overlapping Intervals (LeetCode 435): the same greedy-by-end sweep, counting removals.
• Meeting Rooms II (LeetCode 253): counts peak overlap instead of the fewest stabbing points.
• Merge Intervals (LeetCode 56): the basic sort-then-sweep that all of these build on.