Problem statement

Balloons are horizontal segments points[i] = [xstart, xend]. An arrow shot vertically at x bursts every balloon with xstart <= x <= xend.

Return the minimum number of arrows to burst all balloons.

Example 1

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: Arrows at x=6 and x=11.

Example 2

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4

Constraints

• 1 <= points.length <= 20
• -100 <= xstart <= xend <= 100

Hints for Minimum Number of Arrows to Burst Balloons

1. Hint 1

   Sort by right end; shoot at the first balloon's right edge.

2. Hint 2

   That arrow bursts every balloon starting before it — repeat for the rest.

How to solve Minimum Number of Arrows to Burst Balloons

Exactly the activity-selection greedy again, wearing a different costume. Sort the balloons by their right edge and shoot at the first balloon's right edge — that arrow is as far right as it can be while still bursting that balloon, so it sweeps up as many others as possible. Skip everything it hits and repeat.

Approach

1. Sort the balloons by xend.
2. Shoot the first arrow at the first balloon's xend and count it.
3. Walk the rest: any balloon whose xstart is at or before the current arrow position is already burst — skip it.
4. The first balloon starting after the arrow needs a new one: shoot at its xend and count again.
5. Return the number of arrows.

Why it works

The first balloon to end must be burst by some arrow, and that arrow cannot be positioned further right than its xend. Placing it exactly there is therefore optimal: any valid arrow for that balloon is at a position <= xend, so it bursts a subset of what the rightmost placement bursts. Removing all balloons hit leaves a smaller instance of the identical problem, so induction gives optimality.

Complexity

• Time — O(n log n)
• Space — O(1)

Pitfalls

• Sort by the right edge. Sorting by the left edge breaks the argument and over-counts.
• A balloon touching the arrow exactly at its edge is burst, so the skip test is xstart <= arrowX.
• Compare against the current arrow's position, not the previous balloon's end.
• Coordinates can be negative; initialise the arrow position from the first balloon rather than from zero.

Reference solution

Python

from typing import List

def findMinArrowShots(points: List[List[int]]) -> int:
    s = sorted(points, key=lambda p: p[1])
    arrows = 0
    x = float("-inf")
    for st, en in s:
        if st > x:
            arrows += 1
            x = en
    return arrows

Java

public static int findMinArrowShots(int[][] points) {
    int[][] s = points.clone();
    Arrays.sort(s, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 0;
    int arrowX = 0;
    for (int[] p : s) {
        if (arrows == 0 || p[0] > arrowX) {
            arrows++;
            arrowX = p[1];
        }
    }
    return arrows;
}

C++

int findMinArrowShots(vector<vector<int>>& points) {
    vector<vector<int>> s = points;
    sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
    int arrows = 0;
    int arrowX = 0;
    for (const auto& p : s) {
        if (arrows == 0 || p[0] > arrowX) {
            arrows++;
            arrowX = p[1];
        }
    }
    return arrows;
}

JavaScript

var findMinArrowShots = function(points) {
    const s = points.slice().sort(function(a, b) { return a[1] - b[1]; });
    let arrows = 0, x = -Infinity;
    for (const p of s) {
        if (p[0] > x) {
            arrows++;
            x = p[1];
        }
    }
    return arrows;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium