Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
This is interval-point-stabbing: each balloon is an interval [start,end], and one arrow at position x bursts every balloon whose interval contains x. Sort balloons by their END coordinate, then greedily fire an arrow at the end of the first unburst balloon — it pops every overlapping balloon for free. Count a new arrow only when a balloon starts strictly after the last arrow's position. O(n log n) for the sort, O(1) extra space. The answer is the number of arrows fired.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize this as interval point-stabbing and know to sort by END (not start), plus whether you handle the touching-endpoints case with the correct strict comparison.
Where candidates slip
Sorting by start and getting a suboptimal arrow count, or using `>=` instead of `>` and firing an extra arrow for balloons that merely touch at an endpoint. Also `a[0]-b[0]` comparator overflow on extreme coordinates.
How to stand out
Justify the by-end sort with the exchange argument ('the earliest-ending balloon must be hit by some arrow; placing it at that end can only help later balloons'), and connect it to Non-overlapping Intervals as the same greedy family.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewSort balloons by ENDNext balloon: start > arrowAt?No (overlaps)Yes (gap)Explore the full treeCollapse the tree
How to read it:Two arrows cover four balloons after sorting by end.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Try Arrow Positions Against All Balloons
1Hint 1Explore hintHide hint
Without a sorting insight, deciding the minimum set of stabbing points means searching over which balloons share an arrow — a set-cover-flavored search.
2Hint 2Explore hintHide hint
You could try every candidate arrow position (each balloon's endpoints) and greedily/recursively cover, but the naive search explodes combinatorially.
3Hint 3Explore hintHide hint
This is why we look for a structural property — sorting by end — that makes a simple greedy provably optimal.
A · Core idea
The literal reading of the problem — 'find the minimum set of x-positions such that every balloon contains one' — is a covering problem. Without exploiting structure, you'd be searching over subsets of balloons that can be grouped under a shared arrow, which blows up combinatorially.
Why naive search fails. With up to 10⁵ balloons, any approach that explores combinations of which balloons share an arrow is hopeless. Even a more disciplined recursion that, at each step, picks a balloon and branches over which other balloons to co-burst, has exponential worst-case behavior. There's no polynomial brute force worth writing here.
Why it's still worth a sentence. Naming the brute-force framing — 'this is essentially a minimum point-cover over intervals' — signals to the interviewer that you understand the problem's true nature before you reveal the trick. It also sets up the payoff: interval problems with this shape almost always have a greedy that sorting unlocks, so the natural next question is what should we sort by?
The pivot. The moment you sort the balloons by their end coordinate, the search collapses: a single left-to-right pass with one running 'last arrow position' computes the optimum. That transformation from exponential search to linear greedy is the entire lesson of this problem.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
points = [[1,6],[2,8],[7,12]]group?
could [1,6] & [2,8] share? yes (overlap at 2..6)
candidate arrow in [2,6]2 (impractical to reach this way for large n)C · Code with teaching comments
Reference implementation preview// Illustrative only — exponential, NOT for production. // The real solution is the greedy below. public int findMinArrowShots(int[][] points) { // A correct brute force would search over groupings of balloons // that can share an arrow (set-cover style) — exponential in n.Explore the full codeHide the full code
D · Why it works and complexityexponential / impractical timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
When the brute force for an interval problem is set-cover-flavored and exponential, that's the cue to find a sort order that makes a greedy optimal. The candidate that recognizes 'this smells like interval greedy' and asks 'sort by start or end?' is already most of the way to the answer.
Complexityexponential / impractical time, O(n) space — Choosing which balloons each arrow handles, without the sorting structure, is a covering search whose naive form is exponential in the number of balloons — utterly impractical at n = 10⁵. Listed only to motivate the greedy.
E · Edge cases and pitfalls2Trying to actually implement a covering search at n = 10⁵ — it will time out / blow up.Explore edge casesHide edge cases
Pitfalls
- Trying to actually implement a covering search at n = 10⁵ — it will time out / blow up.
- Believing you must consider non-endpoint arrow positions — the optimum always places an arrow at some balloon's end.
Approach 2 of 2 · Optimal
Greedy — Sort by End, Shoot at Earliest End (Optimal)
1Hint 1Explore hintHide hint
Think about the balloon that ends earliest. Some arrow must burst it. Where should that arrow go to also help as many other balloons as possible?
2Hint 2Explore hintHide hint
Put the arrow exactly at that earliest end. Any balloon whose start is at or before that position is also burst for free. Only when a balloon starts strictly after your arrow do you need a new one.
3Hint 3Explore hintHide hint
So: sort by end, fire at points[0].end, and walk forward — increment the arrow count and reset the arrow position only when a balloon's start exceeds the current arrow position.
A · Core idea
Model each balloon as a closed interval [start, end]; an arrow at x bursts a balloon iff start <= x <= end. We want the fewest arrow positions covering every interval — classic interval point-stabbing, solved by a greedy that sorts by end coordinate.
The greedy choice and why end, not start. Consider the balloon that finishes earliest (smallest end). Some arrow has to burst it, and that arrow must be placed at a position <= end. Among all such positions, placing it exactly at end is weakly best: it's the rightmost legal spot, so it can also reach the most balloons that start later. Formally, by an exchange argument, in any optimal solution we can slide the arrow that bursts the earliest-ending balloon rightward to that balloon's end without losing any coverage — so there's always an optimal solution that fires at the earliest end. Sorting by start doesn't give this guarantee: a balloon with a small start but huge end could swallow the decision and force suboptimal grouping.
The single pass. After sorting by end, fire the first arrow at points[0].end and set arrowAt = points[0].end, with arrows = 1. Scan the rest: for each balloon, if its start <= arrowAt, the current arrow already pierces it (because we sorted by end, its end is ≥ arrowAt, and its start ≤ arrowAt means arrowAt lies inside it) — do nothing. The instant a balloon has start > arrowAt, the current arrow misses it entirely, so we must fire a fresh arrow; we place it at this balloon's end and bump the count. Each balloon is examined once, so the scan is linear.
Why the comparison must be strict (`>`). The intervals are closed, so two balloons that merely touch — [1,2] and [2,3] — both contain the point 2 and can be burst by one arrow. If we used start >= arrowAt to decide a new arrow is needed, we'd wrongly fire a second arrow for the touching balloon. Using strict start > arrowAt correctly treats touching as overlapping. This single character is the most common bug on this problem.
Why sort comparison must avoid overflow. Coordinates span the full 32-bit range down to -2³¹ and up to 2³¹ − 1. A naive comparator return a[1] - b[1]; can overflow (e.g. a large positive minus a large negative wraps to a negative-looking result), corrupting the sort. Use Integer.compare(a[1], b[1]) in Java; Python's sort(key=lambda p: p[1]) has arbitrary precision and is safe. With a correct sort and the strict comparison, the pass yields the provably minimum arrow count.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
points = [[10,16],[2,8],[1,6],[7,12]]Interactive diagram
Exchange-argument intuition
sortSlide any arrow that bursts the earliest-ending balloon to that balloon's end — coverage never decreases.
2C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
This is the twin of Non-overlapping Intervals: both sort by end because the earliest finisher is the 'safe' greedy pick. Here, firing at the earliest end stabs the maximal overlapping group; there, keeping the earliest finisher leaves maximal room. When you see 'minimum X to handle all overlapping intervals', reach for sort-by-end and an exchange-argument proof.
ComplexityO(n log n) time, O(1) space — Sorting dominates at O(n log n). The single pass that counts arrows is O(n). Aside from the sort (which can be in place), only a couple of scalars are used → O(1) extra space (O(1) ignoring sort's recursion, or O(log n) for the sort's stack depending on implementation).
E · Edge cases and pitfalls8points = [[1,2]] — Single balloon → arrows initialized to 1, loop body never runs → 1.Explore edge casesHide edge cases
Edge cases handled
points = [[1,2]]Single balloon → arrows initialized to 1, loop body never runs → 1.points = [[1,2],[2,3]]Touching at 2; start 2 is NOT > arrowAt 2 → one arrow.points = [[1,2],[3,4]]Gap; start 3 > arrowAt 2 → two arrows.points = [[-2147483648,-2147483647],[2147483646,2147483647]]Extreme coords; Integer.compare keeps the sort correct where a-b would overflow → two arrows.
Pitfalls
- Sorting by start instead of end — produces wrong (often too-many) arrow counts.
- Using >= instead of > — fires an extra arrow for balloons that merely touch.
- Comparator a[1] - b[1] overflowing at int extremes — use Integer.compare.
- Initializing arrows to 0 and forgetting the first balloon always needs one (guard empty input separately).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int findMinArrowShots(int[][] points) { if (points.length == 0) return 0; // Sort by END; Integer.compare avoids a-b overflow at int extremes. Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Sorting by start instead of end
The greedy proof relies on the earliest-ENDING balloon: its end is the optimal arrow position. Sorting by start can group balloons that don't actually share a common point optimally, inflating the count.
Explore the code comparisonHide the code comparison
Sorting by start instead of end
The greedy proof relies on the earliest-ENDING balloon: its end is the optimal arrow position. Sorting by start can group balloons that don't actually share a common point optimally, inflating the count.
Don't write this
points.sort(key=lambda p: p[0]) # by start — wrong greedyWrite this instead
points.sort(key=lambda p: p[1]) # by end — earliest finisher first2Using >= instead of strict >
Intervals are closed, so [1,2] and [2,3] both contain x=2 and burst with one arrow. With >=, a balloon starting exactly at arrowAt is treated as a miss, firing a needless extra arrow.
Explore the code comparisonHide the code comparison
Using >= instead of strict >
Intervals are closed, so [1,2] and [2,3] both contain x=2 and burst with one arrow. With >=, a balloon starting exactly at arrowAt is treated as a miss, firing a needless extra arrow.
Don't write this
if (points[i][0] >= arrowAt) { // touching balloons wrongly get a new arrow
arrows++;
arrowAt = points[i][1];
}Write this instead
if (points[i][0] > arrowAt) { // touching balloons share the arrow
arrows++;
arrowAt = points[i][1];
}3Comparator overflow at int extremes
x can be -2³¹ or 2³¹-1. The subtraction a[1] - b[1] overflows (e.g. 2³¹-1 minus -2³¹ wraps negative), so Arrays.sort orders elements incorrectly.
Explore the code comparisonHide the code comparison
Comparator overflow at int extremes
x can be -2³¹ or 2³¹-1. The subtraction a[1] - b[1] overflows (e.g. 2³¹-1 minus -2³¹ wraps negative), so Arrays.sort orders elements incorrectly.
Don't write this
Arrays.sort(points, (a, b) -> a[1] - b[1]); // overflow at extremesWrite this instead
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));Revise
Carry the pattern into the interview
Pattern to remember
Greedy interval point-stabbing — sort by END, shoot at end of current group
Code pattern to memorize
points.sort(by end)
arrows = 1
arrowAt = points[0].end
for s, e in points[1:]:
if s > arrowAt: # this balloon starts after the arrow
arrows += 1
arrowAt = e # new arrow at this balloon's end
return arrowsRules to remember
- 1Sort by END coordinate, not start. Shooting at the earliest end maximizes how many later balloons that single arrow can also catch.
- 2Place the arrow at the end of the current balloon and reuse it for every balloon that starts at or before that position.
- 3A new arrow is needed only when
start > arrowAt— use strict>because touching endpoints ([1,2]and[2,3]) still share point 2 and burst together. - 4Start with
arrows = 1(an empty array returns 0, so guard that first) — the first balloon always needs one arrow. - 5Sort by end using a comparator that avoids `a-b` overflow (values reach ±2³¹); use
Integer.comparein Java.
Use this pattern when
- Minimum points to 'stab' / cover all intervals (point-stabbing)
- Fewest resources to handle every overlapping interval at once
- Any 'one action clears a whole overlapping group' framing
- Maximize reuse of a shared resource across overlapping ranges
Choose another pattern when
- You must MERGE overlaps into combined intervals → Merge Intervals, sort by start (LC 56)
- You need the count of overlaps / rooms at a time → sweep-line or heap (Meeting Rooms II)
- You delete the fewest intervals to make them disjoint → sort by end but COUNT keepers (LC 435)
- Weighted intervals where each has a value → greedy fails, use DP
Interview takeaway
Sorting by END is the fingerprint of greedy interval problems where the earliest finisher is the safe choice. Here, an arrow at the earliest end stabs the most balloons; in Non-overlapping Intervals the earliest finisher leaves the most room. Same sort, same proof structure — recognize it and these problems collapse to a one-pass count.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternGreedy interval point-stabbing. Recognize it when one action (an arrow, a point) must cover every overlapping interval and you want the fewest actions. Sort by END and shoot at the earliest end — the same exchange-argument greedy behind Non-overlapping Intervals and Maximum Length of Pair Chain. Contrast with Merge Intervals (sort by start) and Meeting Rooms II (count concurrency).
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Non-overlapping IntervalsSame sort-by-end greedy; count KEEPERS (survivors) and return n − keepers.
- Merge IntervalsDifferent goal — combine overlaps; sort by START and sweep, extending the running end.
- Meeting Rooms IICount max concurrent overlaps with a min-heap of end times or a sweep line.
- Maximum Length of Pair ChainComing soonActivity-selection again: sort by end, greedily chain non-overlapping pairs.