Pattern this teaches:Intervals
Minimum Number of Arrows to Burst Balloons
A medium Greedy interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Greedy
- Sheets
- 2
- Core for
- 3 roles
The problem
There is a 2D grid of balloons. An arrow shot at coordinate x pops all balloons that have a horizontal diameter spanning x. Find the minimum number of arrows needed to pop all balloons.
Example 1
- Input
- points = [[1,5],[2,6],[3,7],[4,8]]
- Output
- 1
- Why
- All intervals overlap at [4,5], one arrow at 4.5 bursts all.
Example 2
- Input
- points = [[1,3],[2,4],[5,7],[6,8]]
- Output
- 2
- Why
- Two groups: [1,3]&[2,4] overlap, [5,7]&[6,8] overlap. Two arrows needed.
Constraints
- 1 <= points.length <= 10^5
- points[i].length == 2
- -2^31 <= xstart < xend <= 2^31 - 1
How to think about it
Updated 2026-09-29The balloon that ends first forces your hand: you must pierce it before or at its right edge. Shooting at its exact right edge gives the arrow the greatest possible reach into balloons that start later.
Approaches, worst first
Sort by start coordinate
time O(n log n) · space O(1)
Sort by xstart and maintain the current intersection window [currStart, currEnd]. When a balloon starts past currEnd, fire an arrow and reset the window. Correct, but requires maintaining both endpoints of the intersection.
Sort by end coordinateWrite this one
time O(n log n) · space O(1)
Sort balloons by xend. Shoot the first arrow at the first balloon's end coordinate. Skip all subsequent balloons whose start coordinate is within reach of this arrow. When a balloon starts after the current arrow, shoot a new arrow at its end coordinate.
Where people lose marks · 2
- Integer subtraction `a[1] - b[1]` inside comparator functions will overflow and flip signs because coordinates can span -2^31 to 2^31 - 1; use explicit `<` and `>` comparisons.
- Treating touching points as disjoint: a balloon [1, 2] and [2, 3] both get popped by an arrow at 2, so the condition to skip is `start <= arrowPos`, not `start < arrowPos`.
The theory behind it
Greedy — the ground this problem stands on. All Greedy problems
What Greedy is
A greedy algorithm makes the best-looking choice available right now, at every step, without ever looking back or second-guessing its decision. Think of a cashier making change by handing over the largest possible coin first, repeatedly, until the total is reached. Unlike dynamic programming, which saves and compares answers to multiple overlapping paths, a greedy strategy commits to one immediate option and keeps moving forward.
When to reach for it
Reach for greedy when problems ask for minimum jumps, interval scheduling, assigning resources to maximize satisfaction, or finding fractional values. Key signals include sorted orders where greedily taking the next item never hurts future options, or gas station round trips where running balances prove reachability. If you can prove that taking the immediate best choice never leaves you worse off than any alternative, greedy gives the fastest answer.
How the pattern works
Start by sorting the input to bring the most promising candidates to the front. At each position, evaluate your local rule, take the best available piece, and update your running state. The crucial mental step is proving the greedy choice property: demonstrate that picking this immediate winner cannot block a better global solution down the road. If choosing an item now forces you to reconsider past decisions when conditions change later, greedy fails and you must switch to dynamic programming instead.
More Greedy problems
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .