DSA AnimatorDSA animations
Minimum Arrows to Burst Balloons LC #452 Medium Intervals · Greedy
Problem

Balloons are [xstart, xend] on the x-axis. An arrow at x bursts all balloons where xstart ≤ x ≤ xend. Return the minimum arrows to burst all balloons.

Example
Input: [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: Shoot at x=6 (bursts [1,6],[2,8]). Shoot at x=12 (bursts [7,12],[10,16]).
Try Examples
Approach
Greedy — Sort by End, Shoot at Earliest End
Sort by end. Shoot at first balloon's end. All balloons that overlap that point burst. Repeat for next unburst.
Balloons (x-axis)
Load an example to begin.
Arrows 0
Variables
arrowPos
—
Balloon
—
In range?
—
Action
—
Step Logic
Press ▶ Play or Next Step to begin.
✓
Ready
0 / 0
Select an example and press Play.
Algorithm
1
Sort by end
2
Shoot at first balloon's end
3
If balloon.start > arrowPos → new arrow at balloon.end
Time
O(n log n)
Space
O(1)
Why Shoot at End

Shooting at the end of the first balloon maximizes the chance to hit overlapping balloons. Any balloon with start ≤ arrowPos gets burst. Same logic as Non-Overlapping Intervals.

How to solve Minimum Number of Arrows to Burst Balloons

LeetCode 452 · Medium · Intervals · Pattern: Greedy by End

Why the obvious approach is slow

Trying arrow positions everywhere is far too slow. Shooting at the end of a balloon hits the most others.

The key idea

Sort the balloons by their end. Shoot an arrow at the end of the first balloon that is still whole. Every balloon that starts at or before that point bursts too.

Remember

Sort by end, and shoot at the end. One arrow covers every balloon that starts before it.

Run the animation above on your own input, or watch the 1:11 video explanation of Minimum Number of Arrows to Burst Balloons with a dry run and Java code.

More Intervals problems