Get started

Minimum Number of Arrows to Burst Balloons — Medium Problem & Solution

Balloon i spans the horizontal interval [xstart, xend]. An arrow shot straight up at x bursts every balloon whose interval contains x, endpoints included,…

Problem statement

Balloon i spans the horizontal interval [x_start, x_end]. An arrow shot straight up at x bursts every balloon whose interval contains x, endpoints included, and travels infinitely upwards.

Return the minimum number of arrows needed to burst all the balloons.

Example 1

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

Example 2

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

Example 3

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: Shoot at x = 2 and x = 4.

Constraints

  • 1 <= points.length <= 100000
  • points[i].length == 2
  • -1000000000 <= x_start <= x_end <= 1000000000

How to solve Minimum Number of Arrows to Burst Balloons

The classic interval-stabbing greedy. Sorting by right endpoint and always shooting at the earliest end bursts as many balloons as any single arrow can, without ever forcing an extra arrow later.

Approach

  1. Sort by right endpoint ascending.
  2. Shoot at the first balloon's right endpoint and remember it as end.
  3. Scan on: a balloon starting at or before end is already burst; otherwise fire a new arrow at its right endpoint and update end.

Why it works

Exchange argument: in any optimal solution, the arrow that bursts the earliest-ending balloon can be moved to that balloon's right endpoint without losing any balloon it already hit — every balloon it hit starts at or before that point and ends at or after it. Repeating the argument turns any optimal solution into the greedy one, so the greedy is optimal.

Complexity

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

Pitfalls

  • Sorting by the left endpoint needs a different rule and is easy to get wrong.
  • Endpoints count as hits, so the test is start > end, strictly.
  • Subtracting coordinates in a comparator can overflow a 32-bit int; compare rather than subtract.

Reference solution

Python

from typing import List

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

JavaScript

var findMinArrowShots = function(points) {
    var p = points.slice().sort(function(a, b) {
        return a[1] < b[1] ? -1 : (a[1] > b[1] ? 1 : 0);
    });
    var arrows = 1, end = p[0][1];
    for (var i = 1; i < p.length; i++) {
        if (p[i][0] > end) { arrows++; end = p[i][1]; }
    }
    return arrows;
};

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

All 667 arrays problems · the whole catalogue