Minimum Arrows Balloons LeetCode 452

LeetCode 452, Minimum Number of Arrows to Burst Balloons, models each balloon as a horizontal interval [xstart, xend] on an x-axis. An arrow is shot vertically at any x-coordinate and bursts every balloon whose interval covers that x. Your task is to find the minimum number of arrows needed to burst all balloons.

The key observation is that a single arrow at position x bursts all balloons with xstart <= x <= xend. If several balloons all overlap at some common x, a single arrow through that point bursts them all. The problem thus reduces to finding the minimum number of groups of mutually overlapping intervals — exactly the greedy interval scheduling problem.

With up to 100,000 balloons and coordinates in the range of a 32-bit integer, you need an efficient O(n log n) solution. The greedy approach delivers exactly this: sort once, then process all balloons in a single linear pass.

The greedy strategy is to sort all balloons by their end coordinate (xend). Then shoot the first arrow at the end of the first balloon — this is the leftmost possible arrow that bursts the first balloon, placed as far right as possible within that balloon to maximize its overlap with future balloons. Any balloon whose xstart is at or before this arrow position will be burst by the same arrow.

After placing the first arrow, skip all balloons that are burst by it (those with xstart <= arrow position). The next unbursted balloon starts a new group: shoot another arrow at its end. Repeat this process until all balloons are burst. Each iteration of the main loop accounts for one additional arrow.

This greedy is provably optimal: placing the arrow at the end of each group's first balloon (sorted by end) is the best possible position because it covers as far right as possible within the first balloon, giving all subsequent overlapping balloons the maximum chance to be covered without adding a new arrow.

The algorithm requires only a sort and a single linear scan. After sorting by xend, initialize the arrow position at the first balloon's end and set the count to 1. Then walk through every subsequent balloon: if its xstart is greater than the current arrow position, this balloon cannot be burst by the existing arrow, so fire a new arrow at this balloon's end and increment the count.

If the balloon's xstart is at or before the current arrow position, it overlaps with the existing arrow and is burst for free — no new arrow is needed and the arrow position stays unchanged. This single comparison is the entire inner loop body.

The algorithm runs in O(n log n) time dominated by the sort and O(1) extra space — no additional data structures are needed beyond the arrow position and count variables.

Sorting by xstart instead of xend can lead to suboptimal arrow placement. Consider balloons [[1,10],[2,3],[4,5]]: sorted by start, you would place the first arrow at position 10 (end of the first balloon after processing it), but balloons [2,3] and [4,5] are already burst — this happens to work here. However in [[1,5],[2,10],[3,4]], sorting by start and placing an arrow at the end of the first balloon (position 5) bursts all three, which is correct — but this depends on the specific instance and the logic becomes harder to reason about.

Sorting by end is the canonical approach because it is provably correct: placing the arrow at the earliest end of each group (the first balloon in sorted order) is always optimal. Every balloon in the current group has xstart <= current arrow position and xend >= current arrow position (since they were sorted by end and overlap with the first balloon), so the arrow at the first balloon's end is always a valid placement for the entire group.

This insight — sort by finish time, act greedily at the finish — is the backbone of the activity selection proof by exchange argument. Any alternative placement of the arrow can be "swapped" to the end of the first balloon without increasing the arrow count and without uncovering any balloon that was previously burst.

A subtle but important detail: balloons [1,6] and [6,10] are burst by the same arrow at x=6. The intervals share only the single point x=6, but that is enough — the problem uses closed intervals (endpoints inclusive), so an arrow at 6 bursts both balloons.

The overlap condition for the algorithm is xstart <= arrow (not strictly less than). When checking whether a new balloon is burst by the current arrow, the condition is points[i][0] <= arrow. If they are equal (the new balloon starts exactly at the arrow position), the balloon is burst. Only when points[i][0] > arrow is a new arrow required.

This endpoint-inclusive rule affects the arrow count when balloons share only their boundary points. For example, with balloons [[1,2],[2,3],[3,4]], a single arrow at x=2 bursts the first two, and then x=3 bursts the third — two arrows total, not three. Without the inclusive rule (if endpoints were exclusive), each would require its own arrow.

Python solution: def findMinArrowShots(points): points.sort(key=lambda x: x[1]); arrow = points[0][1]; count = 1; for i in range(1, len(points)): if points[i][0] > arrow: arrow = points[i][1]; count += 1; return count. The sort key lambda x: x[1] sorts by the second element (xend). Time complexity O(n log n), space O(1) — the sort is in-place and no extra data structures are used.

Java solution: Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1])); int count = 1; int arrow = points[0][1]; for (int i = 1; i < points.length; i++) { if (points[i][0] > arrow) { arrow = points[i][1]; count++; } } return count. The comparator uses Integer.compare to safely handle the full 32-bit integer range without overflow.

Both implementations follow the same pattern: sort by end, initialize with the first arrow, iterate through remaining balloons checking xstart against the current arrow. The only difference is the sort syntax and integer safety concerns in Java.

Minimum Arrows to Burst Balloons is structurally identical to Non-Overlapping Intervals (LeetCode 435): the minimum number of arrows equals the number of non-overlapping interval groups, and LeetCode 435 asks for the number of intervals to remove to make all remaining intervals non-overlapping. Both problems share the sort-by-end greedy; LeetCode 435 just frames the answer differently (intervals removed = total - groups kept).

Merge Intervals (LeetCode 56) is the union counterpart: instead of counting non-overlapping groups, you merge overlapping intervals into combined ranges. Meeting Rooms II (LeetCode 253) counts the maximum overlap depth at any point (minimum rooms needed), solved with a min-heap or sweep-line approach. Insert Interval (LeetCode 57) adds a new interval to a sorted disjoint list and merges as needed.

The greedy interval scheduling family — sort by end, act at the end, skip overlaps — appears across dozens of problems. Once you internalize the exchange argument proof, you can apply this pattern confidently to any problem that asks for the minimum number of "actions" to cover a set of intervals.