Minimum Number of Arrows to Burst Balloons

MediumIntervals · Greedy · Sorting🧩 Intervals & Line Sweep LeetCode #452 ↗Updated Oct 30, 2026

Problem

Each balloon spans a closed horizontal range points[i] = [xStart, xEnd]. An arrow shot vertically at x bursts every balloon with xStart ≤ x ≤ xEnd and keeps flying. Return the minimum number of arrows needed to burst all balloons.

Inputpoints = [[10,16],[2,8],[1,6],[7,12]]Output2

Inputpoints = [[1,2],[3,4],[5,6],[7,8]]Output4

Inputpoints = [[1,2],[2,3],[3,4],[4,5]]Output2

1 ≤ points.length ≤ 10⁵ · -2³¹ ≤ xStart ≤ xEnd ≤ 2³¹-1

Try it yourself

Java

class Solution {
    public int findMinArrowShots(int[][] points) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Look at the balloon that ends first: some arrow must hit it, and shooting at its right edge hits it and as many others as possible. Sorting by end turns that into a single greedy pass.

PatternIntervals & Line Sweep

Instinct See [start, end] pairs, meetings, bookings or the word "overlap"? Sort by an endpoint, then sweep left to right carrying one running fact.

Memory hack Sort, then sweep - start time to merge, end time to choose, +1/-1 events to count the crowd.

Open the Intervals & Line Sweep guide →

Approaches

Brute ForceRepeated Earliest-End Scan (No Sorting)

Time O(n²)Space O(n)

While balloons remain, scan for the unburst balloon with the smallest end, shoot exactly there, and mark everything that arrow pierces. Each round costs O(n) and may remove only one balloon, so the total is quadratic.

Java

public int findMinArrowShots(int[][] points) {
    int n = points.length, left = n, arrows = 0;
    boolean[] burst = new boolean[n];
    while (left > 0) {
        int pick = -1; // unburst balloon that ends first
        for (int i = 0; i < n; i++) {
            if (!burst[i] && (pick == -1 || points[i][1] < points[pick][1])) pick = i;
        }
        int x = points[pick][1];
        arrows++;
        for (int i = 0; i < n; i++) {
            if (!burst[i] && points[i][0] <= x && x <= points[i][1]) {
                burst[i] = true;
                left--;
            }
        }
    }
    return arrows;
}

Captures the right greedy rule, but rescans the array every round.

BetterSort by Start, Shrink the Shared Window

Time O(n log n)Space O(log n)

Sort by start and grow a group of balloons that one arrow can still hit. The group's shootable window ends at the minimum end seen so far; a new balloon that starts after that point can't join, so a new arrow begins.

Java

public int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
    int arrows = 1;
    int windowEnd = points[0][1]; // last x that hits the whole group
    for (int i = 1; i < points.length; i++) {
        if (points[i][0] > windowEnd) {
            arrows++; // can't share: start a new group
            windowEnd = points[i][1];
        } else {
            windowEnd = Math.min(windowEnd, points[i][1]);
        }
    }
    return arrows;
}

Fast, but must track a shrinking window — easy to forget the min.

OptimalSort by End, Shoot at Right Edges

Time O(n log n)Space O(log n)

Sort by end. Fire the first arrow at the first balloon's end. Every later balloon that starts at or before that arrow is already burst (its end is ≥ the arrow); the first one that starts after it needs a new arrow at its end.

Java

public int findMinArrowShots(int[][] points) {
    // Integer.compare avoids overflow on values near the int limits
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 1;
    int arrowX = points[0][1];
    for (int[] p : points) {
        if (p[0] > arrowX) { // this balloon is past the last arrow
            arrows++;
            arrowX = p[1];
        }
    }
    return arrows;
}

Dry runpoints = [[10,16],[2,8],[1,6],[7,12]]

a arrow balloon changed

sorted
1-6

2-8

7-12

10-16

by end
i=0
1-6
a
2-8

7-12

10-16

arrow at 6, arrows=1
i=1
1-6
a
2-8

7-12

10-16

2 ≤ 6: burst
i=2
1-6

2-8

7-12
a
10-16

7 > 6: arrow at 12
i=3
1-6

2-8

7-12
a
10-16

10 ≤ 12: burst ✔

Same Big-O as Better with less state — the canonical greedy.

Pro tip

Never sort with a[1] - b[1]: with coordinates near ±2³¹ the subtraction overflows and corrupts the order.

At a glance

Level	Approach	Time	Space
Brute Force	Repeated Earliest-End Scan (No Sorting)	`O(n²)`	`O(n)`
Better	Sort by Start, Shrink the Shared Window	`O(n log n)`	`O(log n)`
Optimal	Sort by End, Shoot at Right Edges	`O(n log n)`	`O(log n)`

Common pitfalls

Comparator a[1] - b[1] — overflows on extreme coordinates.
Using >= — touching balloons ([1,2],[2,3]) share one arrow.
Sorting by start but keeping the first balloon's end instead of the running minimum.

Interview tips

Argue the exchange: moving any arrow right up to the first end never loses a balloon.
Note the link to Non-overlapping Intervals: arrows = n − removals there.
Point out closed intervals here versus half-open ones in meeting problems.

Pattern

Interval stabbing, sort by end → fewest points that hit every interval.

My notes saved in this browser