FAANG · LeetCode #452

Minimum Number of Arrows to Burst Balloons — three-stage drill

1The ProblemMedium

Minimum Number of Arrows to Burst Balloons

Min arrows to pop every balloon, where one arrow fired at x bursts every balloon spanning that x.

Examples

[[10,16],[2,8],[1,6],[7,12]]→ 2[[1,10],[2,3],[5,6],[7,8]]→ 3

constraintBalloons are closed intervals [start, end]; an arrow at x bursts every balloon with start ≤ x ≤ end.

2The PatternTIME O(n log n) · SPACE O(n)

Intervals

Given a pile of ranges, sort them by start — now any overlap is a neighbour, so a single left→right pass handles them.

Problems using this pattern

3The SolutionRESULT → 2

Step through it

given: 4 balloons spanning x-ranges · burst all with the fewest arrows

Step 1 / 7

Python▎sort by end · anchor arrows to earliest unburst end

1def findMinArrowShots(points):
2    points.sort(key=lambda p: p[1])      # by right edge
3    arrows = 0
4    arrow_x = -float('inf')
5    for s, e in points:
6        if s > arrow_x:                  # not covered by the last arrow
7            arrows += 1
8            arrow_x = e                  # fire at this balloon's right edge
9    return arrows

why it worksSort by right edge. Take the leftmost (earliest-ending) balloon and fire an arrow at its right edge — this is the latest position that still bursts it, and so the position that overlaps the MOST later balloons. Skip every balloon the arrow also bursts (start ≤ arrow), then repeat on the first balloon left standing. O(n log n). Why by right edge, not left? Try the big-balloon case: a wide balloon [1,10] tempts you to fire at x=10 if it leads the input. Sorting by END puts [1,10] LAST, so the first arrow (aimed at a small balloon's right edge) reaches into the big balloon for free.

Minimum Number of Arrows to Burst Balloons — three-stage drill