Minimum Number of Arrows to Burst Balloons

mediumGreedy & Intervals14 stepsJava · Python · C++

Each balloon spans [start, end] on the x-axis; an arrow at x bursts every balloon covering x. Sort by end; shoot at the first balloon's end, which bursts everything starting at or before it. The next balloon that starts after the arrow needs a new arrow.

▶ Watch the animated trace

Traced input: points = [[10, 16], [2, 8], [1, 6], [7, 12]] → 2. Original problem: leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

Complexity

BestO(n log n)

AverageO(n log n)

WorstO(n log n)

SpaceO(1)

Sorting dominates.

Key idea

Shooting at the smallest end bursts the most balloons that must be burst anyway.
A balloon starting after the arrow's x needs a new arrow.
Touching counts: a balloon starting exactly at x is burst.

Common mistakes

a[1] - b[1] in the comparator overflows for values near ±2³¹; use Integer.compare.
Using >= when comparing start to the arrow, which misses touching balloons.

Solution

Java

int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 1;
    long x = points[0][1];
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > x) {
            arrows++;
            x = points[i][1];
        }
    }
    return arrows;
}

Python

def findMinArrowShots(points: List[List[int]]) -> int:
    points.sort(key=lambda p: p[1])
    arrows = 1
    x = points[0][1]
    for start, end in points[1:]:
        if start > x:
            arrows += 1
            x = end
    return arrows

C++

int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
    int arrows = 1;
    long long x = points[0][1];
    for (size_t i = 1; i < points.size(); i++) {
        if (points[i][0] > x) {
            arrows++;
            x = points[i][1];
        }
    }
    return arrows;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No overlaps One arrow each.	`points = [[1, 2], [3, 4], [5, 6], [7, 8]]`	`4`
Touching balloons Arrows at 2 and 4.	`points = [[1, 2], [2, 3], [3, 4], [4, 5]]`	`2`
Overflow-prone values Integer.compare avoids the subtraction overflow.	`points = [[-2147483646, -2147483645], [2147483646, 2147483647]]`	`2`