Minimum Number of Arrows to Burst Balloons

This is the classic greedy-with-sorting problem. The whole algorithm is one sort and three lines of sweep, and the whole difficulty is choosing what to sort by. Sort by the right edge and it works; reach for the "obvious" crowd-pleasing rule instead and it quietly fails.

It sits right next to the Intervals section. Non-overlapping Intervals, covered there, uses the same sort and nearly the same loop. Learn why the sort key is right here, and both problems become one.

The problem

Balloons are taped to a wall. Each one covers a horizontal range [left, right] — only the horizontal position matters. An arrow shot straight up from position x bursts every balloon with left ≤ x ≤ right, and keeps flying. Return the fewest arrows needed to burst every balloon.

• [[3, 9], [7, 12], [1, 4], [10, 15], [13, 14]] → 3. Shoot at 4 (bursts [1, 4] and [3, 9]), 12 ([7, 12] and [10, 15]) and 14 ([13, 14]). You cannot do it with 2: [1, 4], [7, 12] and [13, 14] share no point, so each needs its own arrow.
• [[1, 2], [2, 3], [3, 4], [4, 5]] → 2. A balloon that only touches the arrow's position still bursts: shoot at 2 and at 4.

Constraints: 1 ≤ n ≤ 10⁵, and coordinates are any 32-bit integers, negative included.

Clarifying questions

• Does touching count? Yes: left ≤ x ≤ right, both ends included. This decides > versus >= in the code.
• Can coordinates be negative? Yes, down to about −2³¹. This decides how you initialise the sweep.
• Can a balloon be a single point, like [5, 5]? Yes.
• Is the input sorted? No.

Approach 1: the simple way

First, a useful fact: you only ever need to shoot at some balloon's right edge. Take any arrow and slide it right until it reaches the nearest right edge of a balloon it bursts. It still bursts everything it did, because none of those balloons end before that point. So try one arrow at every right edge, then every pair, then every triple, until one choice bursts everything.

1from itertools import combinations234def min_arrows_brute(balloons: list[list[int]]) -> int:5    """Try 1 arrow, then 2, ... using only balloon right edges as positions."""6    if not balloons:7        return 08    spots = sorted({end for _, end in balloons})9    for count in range(1, len(spots) + 1):10        for shots in combinations(spots, count):11            if all(any(lo <= x <= hi for x in shots) for lo, hi in balloons):12                return count13    return len(spots)

This is correct and exponential: up to 2ⁿ sets of positions, each checked in O(n × k) time. At n = 30 it is already a billion subsets; at n = 10⁵ it will never finish.

A faster idea that people try next is to shoot wherever the most balloons overlap, remove them, and repeat. It is wrong. On [[1, 2], [1, 3], [2, 3], [3, 4], [3, 5], [4, 7]], position 3 is inside four balloons — the unique best spot — so the rule shoots there. That leaves [1, 2] and [4, 7], which share no point: 3 arrows. Shooting at 2 and 4 bursts everything with 2. Taking the biggest crowd left two stragglers on opposite sides.

The key insight

Look at the balloon that ends first. Some arrow must burst it, so some arrow sits at or before its right edge. Slide that arrow right until it is exactly on the right edge. It still bursts this balloon. And every other balloon it used to burst starts no later than the arrow's old position and ends no earlier than this right edge — because this balloon ends first — so it still bursts them too. That is the exchange argument: an optimal answer with an arrow at the first right edge always exists.

So: sort by right edge. Shoot the first balloon at its right edge. Skip every balloon that arrow already pierces. The next balloon that survives is the one ending first among the rest — shoot it at its right edge. Repeat.

There is also a neat lower bound. Every balloon that made you fire a new arrow started after the previous arrow — so those balloons share no point with each other. Pairwise-separate balloons each need their own arrow, so no answer can use fewer arrows than greedy fired. Greedy meets the lower bound: it is optimal.

Approach 2: optimised — sort by the right edge

1def min_arrows(balloons: list[list[int]]) -> int:2    """Sort by right edge; shoot at the right edge of each balloon still whole."""3    arrows = 04    shot = float("-inf")               # position of the last arrow5    for start, end in sorted(balloons, key=lambda b: b[1]):6        if start > shot:               # the last arrow missed this balloon7            arrows += 18            shot = end                 # as far right as this balloon allows9    return arrows

1. Sort by the right edge.
2. shot = float("-inf") means "no arrow yet"; any balloon, at any coordinate, starts after it.
3. If the balloon starts after the last arrow, the arrow missed it: fire a new one at its right edge.
4. Otherwise the balloon contains shot — it starts at or before shot, and it ends at or after shot because the sort put it later — so it is already burst.

Dry run on [[3, 9], [7, 12], [1, 4], [10, 15], [13, 14]]. Sorted by right edge: [1, 4], [3, 9], [7, 12], [13, 14], [10, 15].

Answer 3. The three balloons that fired arrows — [1, 4], [7, 12], [13, 14] — are the pairwise-separate set from the lower bound.

Complexity: O(n log n) time for the sort; the sweep is O(n). O(n) space for the sorted copy, or O(1) extra if you sort the input in place.

Approach 3: sort by the left edge instead

You can also sort by the left edge and keep the overlap of the current group of balloons. Each new balloon either touches the overlap (shrink it) or starts after it (fire, start a new group).

1def min_arrows_by_start(balloons: list[list[int]]) -> int:2    """Sort by left edge; keep the overlap of the current group, shrink it."""3    arrows = 04    reach = float("-inf")              # rightmost spot that still hits the whole group5    for start, end in sorted(balloons):6        if start > reach:              # does not touch the group: new arrow7            arrows += 18            reach = end9        else:10            reach = min(reach, end)    # the group's overlap shrinks11    return arrows

Same O(n log n) time. It mirrors Merge Intervals, except the group keeps the intersection rather than the union. The right-edge version is shorter and has the cleaner proof, so lead with that one. Both were tested against the brute force on 3,000 random inputs.

Edge cases

• One balloon, or a single point [5, 5]: one arrow.
• Touching balloons, [[1, 2], [2, 3]]: one arrow at 2, because the comparison is strictly start > shot.
• Negative coordinates, [[-5, -3], [-4, -1]]: one arrow at −3. This only works because shot starts at minus infinity.
• Nested balloons, [[1, 10], [3, 4]]: sorted by right edge, [3, 4] comes first; its arrow at 4 also bursts [1, 10].

Follow-ups

• Non-overlapping Intervals — remove the fewest intervals so the rest do not overlap? Same sort by end; count the intervals you keep with start >= last_end (touching is allowed there), and return n minus that count. The Intervals section works it in full.
• Touching does not burst? Change start > shot to start >= shot.
• Return the arrow positions? Append end every time you fire.