Minimum Number of Arrows to Burst Balloons
Balloons are given as horizontal intervals. An arrow shot upward at x bursts every balloon whose interval contains x. Return the minimum number of arrows needed.
- 1 <= points.length <= 10⁵
- points[i].length == 2
- -2³¹ <= xstart < xend <= 2³¹ - 1
Intuition
Minimum number of arrows to burst balloons finds the fewest vertical arrows needed to pop every balloon, where each balloon is a horizontal interval and an arrow bursts all balloons it passes through.
This is an interval-covering problem, and the sorting key decides whether the greedy works:
- Sort by end coordinate, then shoot at the end of the first balloon — that arrow bursts every balloon it can, and nothing is lost by placing it there.
The argument is that the balloon ending earliest must be burst by some arrow, and placing that arrow at its right edge is optimal: any arrow further left bursts a subset of what this one does. So the greedy choice never sacrifices a later opportunity.
After placing an arrow, skip every balloon whose start is at or before that arrow's position — those are already burst. The next balloon starting after it needs a new arrow.
Sorting by start instead is the classic error. It leads to shooting at the wrong position and overcounting on inputs where a wide balloon starts early and ends late.
The overlap test must be <=, since a balloon merely touching the arrow's position is still burst — the endpoints are inclusive.
Coordinates can reach the limits of 32-bit integers, so computing a midpoint or a difference can overflow in some languages. Comparing directly rather than computing spans avoids the issue.
Every balloon is examined once after the sort, so the cost is dominated by sorting at O(n log n), with O(1) extra space.
Interval scheduling again: sort by end coordinate and fire an arrow at the end of the first balloon, which pops every balloon overlapping it. Choosing the earliest possible end maximises what a single arrow covers — the same exchange argument as Non-overlapping Intervals.
Approach
Before reading on: price up what sorting first costs here, then ask what sorting by one endpoint makes obvious that was hidden before. Aim for O(n log n) time and O(1) space.
Sort by end coordinate
Sorting by end is what makes the greedy correct. Sorting by start leads to arrows in the wrong position and overcounts on wide early balloons.
Shoot at the first balloon's end
The earliest-ending balloon must be burst, and its right edge is the best position — any arrow further left bursts strictly fewer balloons.
Skip everything already burst
Advance past every balloon whose start is at or before the arrow's position. These are covered and need no further arrows.
Use inclusive comparison
Test with <= — a balloon merely touching the arrow's position is still burst, since the interval endpoints are inclusive.
Place a new arrow on a gap
The first balloon starting after the arrow's position requires a new arrow at its own end. Repeat until every balloon is covered.
Watch for coordinate overflow
Coordinates can reach the 32-bit limits, so computing midpoints or spans can overflow. Compare endpoints directly instead.
Cost of the approach
Sorting dominates at O(n log n) time, with a single O(n) pass afterwards and O(1) extra space.
Solution & live demo
Common pitfalls
Sorting by start coordinate
points.sort(key=lambda x: x[0])
points.sort(key=lambda x: x[1])
Firing at a balloon's start can miss later balloons that a slightly further shot would catch. Anchoring at the earliest end guarantees the arrow is as far right as it can be while still bursting the current balloon.
Using >= for the new-arrow test
if s >= pos:
if s > pos:
A balloon starting exactly where the arrow was fired is still touched by it — the ranges are inclusive. The strict test correctly reuses the arrow; >= fires an unnecessary extra one.
Sorting with subtraction on large coordinates
sort(points.begin(), points.end(), [](auto&a, auto&b){ return a[1] - b[1] < 0; });return a[1] < b[1];
Coordinates reach ±2^31, so a[1] - b[1] overflows a 32-bit int and produces an inconsistent comparator — which can corrupt the sort or crash. Compare directly instead of subtracting.
Edge cases
One arrow suffices.
One arrow bursts them all.
Still burst by a single arrow — the <= comparison is what gets this right.
Each needs its own arrow, so the answer equals the count.