Min Arrows to Burst Balloons

Problem

Each balloon is an interval [xstart, xend] on a number line. An arrow shot at coordinate x bursts every balloon whose interval contains x. Return the minimum number of arrows needed to burst every balloon.

Constraints

• 1 ≤ points.length ≤ 10⁵
• −2³¹ ≤ xstart ≤ xend ≤ 2³¹−1

Approach — Greedy

This is a Greedy problem. The idea: make the locally best choice at each step, which provably builds up to the global optimum here. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log n) time.

Solution code

Python

class Solution:
    def findMinArrowShots(self, points):
        if not points:
            return 0
        points.sort(key=lambda p: p[1])
        arrows = 1
        end = points[0][1]
        for s, e in points[1:]:
            if s > end:
                arrows += 1
                end = e
        return arrows

Java

import java.util.*;

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.