#452 Minimum Number of Arrows to Burst Balloons
the problem
In plain words
Each balloon spans [xstart, xend] on the x-axis. A vertical arrow shot at x bursts every balloon with xstart ≤ x ≤ xend. Return the minimum number of arrows that burst all balloons.
in points = [[10,16],[2,8],[1,6],[7,12]]
out 2
An arrow at x = 6 bursts [2,8] and [1,6]; one at x = 11 bursts [10,16] and [7,12].
in points = [[1,2],[3,4],[5,6],[7,8]]
out 4
No two balloons share a point.
in points = [[1,2],[2,3],[3,4],[4,5]]
out 2
Touching counts: x = 2 and x = 4.
- 1 ≤ points.length ≤ 10⁵
- −2³¹ ≤ xstart < xend ≤ 2³¹ − 1
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternInterval scheduling (sort by end)
The balloon that ends first must be hit somewhere at or before its end. Shooting exactly at its end hits the most other balloons.
solutions
From brute force to optimal
Group balloons while they share a common point. Track the smallest end in the group.
- Sort by start.
- If a balloon starts after the shared end, add an arrow and start a new group.
- Otherwise shared = min(shared, end).
Sort + one pass.
The sort.
class Solution { public int findMinArrowShots(int[][] points) { Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0])); int arrows = 1; int shared = points[0][1]; // right edge of the zone every balloon in the group shares for (int i = 1; i < points.length; i++) { if (points[i][0] > shared) { // outside the shared zone: new arrow arrows++; shared = points[i][1]; } else { shared = Math.min(shared, points[i][1]); // shrink the shared zone } } return arrows; }}Shoot at the earliest end. Skip every balloon that arrow already bursts.
- Sort by end (with Integer.compare).
- arrowX = first end, arrows = 1.
- For each balloon starting after arrowX: arrows++, arrowX = its end.
Sort + one pass.
The sort.
class Solution { public int findMinArrowShots(int[][] points) { // Integer.compare, not a[1] - b[1]: coordinates span the whole int range. Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1])); int arrows = 1; int arrowX = points[0][1]; // shoot at the earliest end for (int[] p : points) { if (p[0] > arrowX) { // this balloon starts after the arrow: needs a new one arrows++; arrowX = p[1]; } } return arrows; }}in the room
How to say it in the interview
talk track
- Say it's activity selection in disguise: each arrow sits at an "end time".
- Mention the comparator overflow trap before the interviewer does.
traps
(a, b) -> a[1] - b[1]overflows on [[-2147483646,-2147483645],[2147483646,2147483647]].- Using
>=instead of>. Touching balloons share an arrow.
what they ask next
Follow-ups
Where exactly should the arrows go?
Record arrowX each time you add an arrow: those are valid positions (each is some balloon's end).
before you submit
Edge cases to test
- Touching [1,2] and [2,3] share one arrow at x = 2.
- Coordinates near ±2³¹: a subtraction comparator overflows and mis-sorts.
- One balloon → 1 arrow.
practise next
Similar problems
- #435Non-overlapping IntervalsMediumin Intervals
- #56Merge IntervalsMediumin Intervals