452. Minimum Number of Arrows to Burst Balloons - Detailed Explanation

Each balloon is given as a horizontal interval [start, end]. An arrow shot straight up at coordinate x bursts every balloon whose interval contains x, including at its endpoints. Return the minimum number of arrows needed to burst them all. The answer is a greedy sweep, and the only real decision is what to sort by.

It appears in the intervals section of LeetCode 75.

Examples

Constraints

• 1 <= points.length <= 100000
• Each entry has exactly two values.
• Coordinates range over the full signed 32-bit span, from -2^31 to 2^31 - 1.

That coordinate range is a deliberate trap, covered below.

Which pattern this problem belongs to

This is the merge intervals pattern, in its greedy form. Interval questions almost always begin by sorting, and the entire difficulty is choosing the sort key. Here you sort by the end coordinate, not the start.

The reason is worth being able to state. If you must burst the balloon that ends earliest, the best possible place to shoot is exactly at its end coordinate, because that is the furthest right an arrow can go while still hitting it. Shooting any earlier can only hit a subset of what shooting at the end would hit. So the greedy choice is safe, and the same exchange argument underpins the whole family of interval scheduling questions.

Approach

Sort by end coordinate. Fire the first arrow at the end of the first balloon. Walk the rest in order. If a balloon starts after the current arrow position, it was not burst, so fire a new arrow at that balloon's end and continue. Otherwise it was already burst and you skip it.

The sort dominates, so the time is O(n log n) and the extra space is whatever the sort uses.

Note that touching counts as overlapping. A balloon [2,3] is burst by an arrow at 2, so the comparison must be start > arrow, with a strict greater-than. Using >= fires an extra arrow on every touching pair and produces answers that are too large.

Python code

def find_min_arrow_shots(points):
    """Sort by end, fire greedily. O(n log n) time, O(1) beyond the sort."""
    if not points:
        return 0
    points.sort(key=lambda p: p[1])
    arrows = 1
    arrow = points[0][1]
    for start, end in points[1:]:
        if start > arrow:          # strict: touching still bursts
            arrows += 1
            arrow = end
    return arrows

Java code

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) return 0;
    // compare, never subtract: a - b overflows across the full int range
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 1;
    long arrow = points[0][1];
    for (int[] p : points) {
        if (p[0] > arrow) {
            arrows++;
            arrow = p[1];
        }
    }
    return arrows;
}

Complexity

Common mistakes

• Sorting by start. It is the obvious choice and it does not give the greedy guarantee. Sorting by end is what makes the local choice provably optimal.
• Subtracting in the Java comparator. Writing a[1] - b[1] overflows when the coordinates span the full integer range, which these do, and the sort then produces a wrong order. Use Integer.compare.
• Treating touching as non-overlapping. An arrow at the shared coordinate bursts both, so the test is start > arrow, strictly.
• Returning the count of overlaps. The question asks for arrows, which is the number of groups, not the number of balloons that overlapped.

Related problems

• Non-overlapping Intervals, which is the same greedy sweep counting removals instead of groups.
• Merge Intervals, which sorts by start because it is combining rather than stabbing.
• Meeting Rooms II, which sorts by start and uses a heap on end times.

How to Prepare

• Learn the sort key as a decision, not a habit. Sorting by end suits "how few points cover everything", and sorting by start suits "merge what touches". Say which you are using and why.
• Use Integer.compare in every comparator. Subtraction is a latent overflow bug that passes small tests.
• Work the interval family together. They share one setup and differ only in the sweep, which is how Grokking the Coding Interview teaches them. The short list is in the most common LeetCode patterns.