Minimum Number of Arrows to Burst Balloons
Understanding the Problem
This looks like a geometry problem, but it reduces to finding groups of overlapping intervals that can all be pierced by a single vertical line. Each balloon is an interval on the x-axis, and an arrow at position x bursts every balloon whose interval contains x.
The question becomes: what is the minimum number of points you need to place on the number line so that every interval contains at least one point? This is the interval point cover problem. If we process the balloons in a sorted order, we can greedily decide where to place each arrow so that one arrow covers as many overlapping balloons as possible.
Key Constraints:
1 <= points.length <= 10^5→ With n up to 100,000, an O(n^2) check of all pairs is about 10 billion operations and too slow, so the solution has to run in O(n log n) or better.-2^31 <= x_start < x_end <= 2^31 - 1→ Endpoints span the full signed 32-bit range. A comparator written asa[1] - b[1]can overflow a 32-bit int (for example2^31 - 1minus-2^31), so the comparisons must be value comparisons rather than subtractions.
Approach 1: Greedy (Sort by Start Point)
Intuition
One arrow can burst a set of balloons only if all of those balloons share a common x-position, which means their intervals have a non-empty intersection. So the answer is the number of groups the balloons split into, where every balloon in a group overlaps a single shared point.
Sort the balloons by their start point and sweep left to right, maintaining the intersection of the current group as a single value: the smallest end point seen so far in the group. Call it end. As long as the next balloon's start is at or before end, it overlaps the running intersection [start, end], so it joins the current group and we shrink end to the smaller of the two end points. When a balloon's start is greater than end, it cannot share any point with the current group, so it starts a new group and needs a new arrow.
Shrinking end to the minimum end point keeps it equal to the right edge of the intersection of every balloon in the group. A new balloon overlaps the whole group exactly when it overlaps that intersection, so comparing its start against end is enough to decide membership.
Algorithm
- Sort
pointsby start point (points[i][0]) in ascending order. - Initialize
arrows = 1andend = points[0][1](the right edge of the first group's intersection). - For each remaining balloon:
- If its start point is greater than
end, it does not overlap the current group. Incrementarrowsand resetendto this balloon's end point. - Otherwise it overlaps the group. Set
end = min(end, current balloon's end point). - Return
arrows.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting by start point dominates. The single sweep through the sorted array is O(n).
- Space Complexity: O(1) beyond the input, or O(log n) to O(n) for the sort's internal stack depending on the language. Only
arrowsandendare kept.
Sorting by start point requires a min on every overlap to track the group's intersection. The next approach removes that step by changing the sort key, which leads to a slightly tighter loop.
Approach 2: Greedy (Sort by End Point)
Intuition
With the array sorted by end point, the arrow position for a group is fixed the moment the group opens and never has to be updated again.
Consider the balloon with the smallest end point. It has to be burst, and shooting at its end point is the position that covers it while reaching as far right as possible. Any earlier position covers this balloon too but ends sooner, so it can only burst the same balloons or fewer. After fixing the arrow at this end point, every balloon whose start point is at or before it is also burst, so those balloons are skipped. The next balloon with a start point beyond the arrow opens a new group, and the same choice repeats.
The arrow position is the end point of the first balloon in each group. Because the array is sorted by end point, that first balloon has the smallest end in the group, so its end point lies inside every later balloon of the group that the arrow bursts. No min step is needed.
An exchange argument shows the greedy is optimal. Take any optimal solution and look at its arrow that bursts the balloon with the smallest end point. Move that arrow rightward to sit exactly on this smallest end point. The set of balloons it can burst only grows, because every balloon it previously hit had a start at or before the smallest end and an end at or after it, so it still contains the new position. Repeating this on the remaining balloons turns any optimal solution into the greedy one without ever increasing the arrow count, so the greedy uses the minimum number of arrows.
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 by end point dominates; the single pass through the sorted array is O(n).
- Space Complexity: O(1) beyond the input, plus O(log n) to O(n) for the sort's internal stack depending on the language. Only
arrowsandarrowPosare kept.