Minimum Number of Arrows to Burst Balloons
Last Updated: April 4, 2026
Understanding the Problem
At first, this might feel like a complex geometry problem, but it boils down to something much simpler: finding groups of overlapping intervals that can all be pierced by a single vertical line. Each balloon is really just an interval on the x-axis, and an arrow at position x bursts every balloon whose interval contains x.
So the question becomes: what is the minimum number of points you need to place on the number line such that every interval contains at least one point? This is a classic interval scheduling/greedy problem. The key observation is that if we process the balloons in a smart order, we can greedily decide where to place each arrow to cover as many balloons as possible.
Key Constraints:
1 <= points.length <= 10^5→ With n up to 100,000, we need O(n log n) or better. O(n^2) would be 10 billion operations, which is too slow.-2^31 <= x_start < x_end <= 2^31 - 1→ Full 32-bit integer range. Be careful with subtraction-based comparisons that could overflow. Use explicit comparisons instead.points[i].length == 2→ Each balloon is a simple interval with a start and end point. The strict inequalityx_start < x_endguarantees no zero-length balloons.
Approach 1: Brute Force (Check All Subsets)
Intuition
The most naive way to think about this: try every possible set of arrow positions and find the minimum set that bursts all balloons. For each balloon, we could potentially shoot an arrow at any integer position within its range. We want the smallest number of arrows such that every balloon is hit by at least one.
In practice, we only need to consider shooting at the endpoints of the balloons, since any optimal arrow position can be shifted to an endpoint without losing coverage. But even so, with up to 10^5 balloons and two endpoints each, enumerating all subsets is exponentially expensive.
This approach is purely conceptual. It helps us understand the problem structure, but we would never implement it for the given constraints.
Algorithm
- Collect all unique endpoints from the balloons.
- Try every subset of endpoints as potential arrow positions.
- For each subset, check if every balloon is burst by at least one arrow in the subset.
- Track the minimum subset size that covers all balloons.
Example Walkthrough
Code
- Time Complexity: O(2^(2n) * n). We have 2n candidate positions and need to check all subsets. For each subset, checking if all n balloons are covered takes O(n). This is astronomically slow.
- Space Complexity: O(n). Storing the candidate positions.
We're examining every possible subset of arrow positions, which is exponentially expensive. What if we processed balloons in a specific order and greedily decided where to shoot each arrow?
Approach 2: Greedy (Sort by End Point)
Intuition
Here's the key insight that unlocks this problem: if we sort the balloons by their end points, we can process them left to right and greedily place arrows.
Why sort by end point? Consider the balloon with the smallest end point. We must burst it with some arrow, and the best place to shoot that arrow is at the balloon's end point. Shooting earlier would work too, but shooting at the end point maximizes the chance of also bursting subsequent balloons (since their start points might overlap with our arrow position).
After placing an arrow, we skip all balloons whose start point is at or before the arrow's position, because they're already burst. Then we repeat: find the next unbursted balloon, shoot at its end point, and skip everything it covers.
This greedy strategy works because:
- Sorting by end point means we always handle the "most constrained" balloon first (the one that ends earliest).
- Shooting at the end point gives maximum coverage to the right.
- Any balloon we skip is guaranteed to be burst, because its start point overlaps with our arrow.
This is an instance of the classic "interval point cover" problem. The greedy choice of always shooting at the earliest end point is provably optimal. If we don't shoot at the earliest end point, we'd have to shoot somewhere earlier to cover that balloon, which would cover fewer subsequent balloons. So delaying the arrow to the end point is always at least as good as any earlier position.
More formally, this is equivalent to the "activity selection" problem in reverse. In activity selection, you pick the maximum number of non-overlapping intervals. Here, the number of arrows equals the number of non-overlapping groups.
Algorithm
- Sort the
pointsarray by the end point (points[i][1]) in ascending order. - Initialize
arrows = 1and setarrowPosto the end point of the first balloon. - Iterate through the remaining balloons:
- If the current balloon's start point is greater than
arrowPos, this balloon is not burst by the current arrow. Incrementarrowsand updatearrowPosto the current balloon's end point. - Otherwise, the current balloon is already burst by the existing arrow. Skip it.
- Return
arrows.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). The single pass through the sorted array is O(n). The sort dominates.
- Space Complexity: O(1). Only a couple of extra variables (arrows, arrowPos). No additional data structures beyond what the sort uses.