Minimum Number of Arrows to Burst Balloons

GREEDY · MEDIUM

The problem

Balloons are taped to a wall, each one a horizontal span [xStart, xEnd] on the x-axis. An arrow is shot straight up from some x-coordinate and bursts every balloon whose span contains that x-coordinate — one arrow can burst many balloons at once, as long as their spans all overlap at that single point. Given the list of balloon spans, return the minimum number of arrows needed to burst every balloon.

Solution 1: Brute force — repeatedly rediscover the best arrow, from scratch

A greedy-looking approach still works here, but a naive implementation of it is wasteful. Each round: scan every still-unburst balloon to find the one with the smallest xEnd (that’s the correct arrow position — shooting there is guaranteed not to miss any balloon that could have been grouped in), shoot an arrow there, then scan the entire remaining list again to remove everything that arrow bursts. Repeat until nothing is left. This is correct — it makes the same greedy choice the optimal solution does — but it rediscovers that choice with a full linear scan every single round instead of sorting once up front, so two full passes over the (shrinking) list happen per arrow.

Flow diagram

Brute force: rediscover the arrow, then rescan everything, every round

┌──────────────────┐     ┌────────────────┐     ┌──────────────────────┐
│ scan for         │────▶│ shoot arrow    │────▶│ rescan ALL to        │
│ smallest end     │     │ there          │     │ remove burst         │
│ (full pass,      │     │                │     │ (another full pass,  │
│  every round)    │     │                │     │  every round)        │
└──────────────────┘     └────────────────┘     └──────────────────────┘

Cost: two full scans per arrow, repeated for every arrow — O(n²) total.

Interactive visualization

current arrow's target balloon (smallest end) burst this round still unburst

Press Play or Step to begin.

This animation traces points=[[10,16],[2,8],[1,6],[7,12]] — a canonical case verified above.

The code

function findMinArrowShotsBrute(points) {
  if (points.length === 0) return 0;
  const remaining = points.map((p) => p.slice());
  let arrows = 0;

  while (remaining.length > 0) {
    // Full re-scan #1: find the unburst balloon with the smallest end.
    let minIdx = 0;
    for (let i = 1; i < remaining.length; i++) {
      if (remaining[i][1] < remaining[minIdx][1]) minIdx = i;
    }
    const arrowX = remaining[minIdx][1];
    arrows++;

    // Full re-scan #2: remove every balloon this arrow bursts.
    for (let i = remaining.length - 1; i >= 0; i--) {
      if (remaining[i][0] <= arrowX && arrowX <= remaining[i][1]) {
        remaining.splice(i, 1);
      }
    }
  }
  return arrows;
}

Line by line:

The inner for loop that finds minIdx is doing, by hand and every single round, exactly the work a single up-front sort would do once.
arrowX is always the smallest xEnd among what’s left — that choice is provably safe: no balloon that could have shared this arrow is ever left unburst by picking the earliest-ending one.
The second loop walks backward and splices out every balloon the arrow bursts, scanning the full remaining list again — this is the second wasted full pass.
Both scans happen once per arrow, and there can be up to n arrows — that’s the O(n²).

Complexity

Time	Space	Approach
O(n²)	O(n)	Repeated full rescans, one pair per arrow

Solution 2: Optimal — sort by end once, one linear pass

Do the expensive part exactly once: sort every balloon by xEnd ascending. Now walk the sorted list left to right, tracking the current arrow’s boundary (end, starting from the first balloon’s end). If the next balloon’s xStart is beyond that boundary, it can’t share this arrow — shoot a new one and reset the boundary to this balloon’s xEnd. Otherwise, it’s already burst by the current arrow, no new arrow needed. Same greedy choice as the brute force, made once per balloon instead of rediscovered every round.

Flow diagram

Optimal: sort by end once, then one linear pass

┌────────────────┐     ┌───────────────────┐     ┌──────────────────────┐
│ sort by xEnd   │────▶│ xStart > current  │────▶│ new arrow / reset    │
│ (once, up      │     │ end?              │     │ end (else: already   │
│  front)        │     │ (check once per   │     │  burst)              │
│                │     │  balloon)         │     │                      │
└────────────────┘     └───────────────────┘     └──────────────────────┘

Cost: O(n log n) — one sort, then every balloon is visited exactly once.

Interactive visualization

current arrow's boundary burst by the current arrow not yet reached

Press Play or Step to begin.

This animation traces points=[[10,16],[2,8],[1,6],[7,12]] — the same canonical case, sorted by end first.

The code

function findMinArrowShotsOptimal(points) {
  if (points.length === 0) return 0;
  const sorted = points.slice().sort((a, b) => a[1] - b[1]);

  let arrows = 1;
  let end = sorted[0][1];

  for (let i = 1; i < sorted.length; i++) {
    const [start, xEnd] = sorted[i];
    if (start > end) {
      // This balloon starts after the current arrow's reach — needs a new arrow.
      arrows++;
      end = xEnd;
    }
    // Otherwise start <= end: already burst by the current arrow, nothing to do.
  }
  return arrows;
}

Line by line:

.sort((a, b) => a[1] - b[1]) — sort by end coordinate, not start. This is the whole insight: after sorting by end, the earliest-ending balloon is always the best one to anchor the first arrow at.
end = sorted[0][1] seeds the boundary with the first (smallest-end) balloon — the first arrow always gets placed there.
start > end is the ONLY condition that forces a new arrow — as long as a balloon’s start still reaches back into the current arrow’s position, it’s already burst.
When a new arrow is needed, end resets to this balloon’s xEnd — the new arrow is placed as late as possible (at this balloon’s own end), maximizing the chance it also bursts whatever comes right after.

Complexity

Time	Space	Approach
O(n log n)	O(n)	One sort by end, then a single linear pass

Complexity comparison

Solution	Time	Space
Brute force (repeated rescans)	O(n²)	O(n)
Optimal (sort by end + linear pass)	O(n log n)	O(n)

This is a real, meaningful gap, not a rounding difference — both make the exact same greedy choice at every step (always anchor the arrow at the smallest remaining end), but the brute force pays for that choice with a fresh O(n) scan every round instead of paying for it once with a single O(n log n) sort. For 1,000 balloons that’s roughly a million operations for the brute force versus roughly ten thousand for the optimal solution.

Interview corner

Q: Why sort by xEnd and not xStart?

The arrow that bursts the earliest-ending balloon has to be placed no later than that balloon’s own end — there’s no flexibility to push it further right.
Placing that arrow exactly at the earliest end is the position most likely to also catch other overlapping balloons, since it’s as far right as this balloon allows.
Sorting by xStart instead can pick a “wide” balloon early (like [1, 100]) and anchor the first arrow too far right, missing the chance to burst several short balloons that don’t reach that far.

Q: How does this relate to Non-overlapping Intervals (Day 27) and Insert Interval, already on this site?

All three are the same underlying pattern: sort by end coordinate, then walk once with a running boundary.
Non-overlapping Intervals asks “how many intervals must be removed to make the rest non-overlapping” — same sort-by-end greedy, different question being asked of the same walk.
Insert Interval doesn’t need the sort at all (its input already arrives sorted), but its 3-phase scan is structurally the same “walk once, track a boundary” shape.
Recognizing “sort by end, track a boundary” as one reusable pattern — not three separate tricks — is what makes all three fast to solve in an interview.

Q: Why is start > end (strict) the correct condition for needing a new arrow, not start >= end?

start === end means the two balloons touch at exactly one point — that single x-coordinate still bursts both.
Using >= would treat touching balloons as needing separate arrows, overcounting the true minimum.
This mirrors the “touching intervals still merge” trap from Insert Interval — same off-by-one boundary condition, same fix.

Q: Trick question — what does this log?

const ends = [10, 9, 2];
console.log(ends.sort());

Answer: [10, 2, 9], not [2, 9, 10].
.sort() with no comparator converts every element to a string and compares them lexicographically — "10" sorts before "2" because "1" comes before "2" character by character.
The array is left numerically scrambled, not sorted by value at all.

⚠️ Trap: This is exactly why the optimal solution above always passes an explicit numeric comparator — .sort((a, b) => a[1] - b[1]) — instead of calling .sort() bare. Balloon end coordinates like 10 and 2 would silently end up in the wrong order otherwise, and the whole greedy walk depends on that order being correct.

Quiz

1. Why does the optimal solution sort balloons by xEnd instead of xStart?

The arrow for the earliest-ending balloon can’t go past its end — placing it exactly there catches the most possible overlapping balloons
Sorting by start or end always produces the identical order, so it doesn’t matter
Sorting by end coordinate always literally uses fewer array elements than sorting by start

Correct! The arrow burst the earliest-ending balloon can never be placed later than that balloon’s own end. Placing it exactly there is the rightmost — and therefore most balloon-catching — position that’s still guaranteed valid, which is why sorting by end (not start) is the key insight.

2. What can go wrong if you sort by xStart instead of xEnd?

A wide balloon can sort first and anchor the first arrow too early, missing chances to burst several short balloons together
The code throws a runtime error on any input with more than 2 balloons
Nothing — start order and end order always agree for balloon inputs

Correct! Sorting by start can put a wide balloon like [1, 100] first. Anchoring the first arrow near its start leaves it far from several short, non-overlapping balloons later in the range that a smarter arrow placement (anchored at the smallest end) would have burst together.

3. What’s actually different between the brute force and the optimal solution?

They make the exact same greedy choice each round — the brute force just rediscovers it with a fresh scan instead of sorting once
They can return different arrow counts on the same input
They use completely unrelated strategies with nothing in common

Correct! Both solutions make the identical greedy choice at every step: anchor the arrow at the unburst balloon with the smallest end. The brute force rediscovers that choice with a full O(n) scan every round; the optimal solution computes it once via a single O(n log n) sort.

4. In the optimal solution, why is start > end (strict, not >=) the condition for needing a new arrow?

When start === end, the balloons touch at one point and the same arrow bursts both — treating that as “needs a new arrow” would overcount
Strict comparison runs faster in JavaScript than >=
There’s no real difference — either comparison produces the same arrow count on every input

Correct! start === end means the balloons touch at exactly one x-coordinate, and a single arrow shot there bursts both. Using strict > (not >=) as the new-arrow condition correctly treats touching balloons as burstable by the same arrow.

5. What’s the time complexity difference between the two solutions, and why?

Brute force is O(n²) from repeated full rescans; optimal is O(n log n), dominated by a single sort
They’re the same — O(n log n) for both
Brute force is O(n log n); optimal is O(n²)

Correct! The brute force pays for its greedy choice with two full scans per arrow, up to n arrows — O(n²). The optimal solution pays for the same choice once via a single O(n log n) sort, then a single O(n) pass — dominated by the sort.