293. Minimum Number of Arrows to Burst Balloons
🔗 LeetCode Problem: 452. Minimum Number of Arrows to Burst Balloons
📊 Difficulty: Medium
🏷️ Topics: Array, Greedy, Sorting
Problem Statement
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.
Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.
Given the array points, return the minimum number of arrows that must be shot to burst all balloons.
Example 1:
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting balloons [10,16] and [7,12].
Example 2:
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.
Example 3:
Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting balloons [3,4] and [4,5].
Constraints:
- 1 <= points.length <= 10^5
- points[i].length == 2
- -2^31 <= xstart < xend <= 2^31 - 1
🌳 Visual Understanding - The Balloon Problem
The Problem We're Solving:
Balloons on a wall (viewed from front):
Wall (XY-plane):
↑ y-axis
|
| 🎈 🎈 🎈
| [2,8] [10,16] [1,6]
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__> x-axis
0 2 4 6 8 10 12 14 16
Arrows shoot VERTICALLY upward from x-axis:
- Arrow at x=6: Hits balloons [2,8] and [1,6] ✓
- Arrow at x=11: Hits balloons [10,16] and [7,12] ✓
Question: Minimum arrows to burst ALL balloons?
Understanding the Balloon Representation:
Balloon [xstart, xend]:
- Horizontal diameter from xstart to xend
- Arrow at x bursts it if xstart <= x <= xend
Example: Balloon [2, 8]
🎈
[---|----]
2 8
Arrow at x=5: 2 <= 5 <= 8 → BURST! ✓
Arrow at x=1: 1 < 2 → MISS! ✗
Arrow at x=9: 9 > 8 → MISS! ✗
Key Observations:
1. One arrow can burst MULTIPLE balloons
If balloons overlap, one arrow can hit both!
2. Balloons at same x-coordinate can share arrow
[1,6] and [2,8] both cover x=6
One arrow at x=6 hits both!
3. We want MINIMUM arrows
Maximize balloons burst per arrow
4. This is similar to Non-overlapping Intervals!
But instead of removing overlaps,
we GROUP overlapping balloons!
Example Visualization:
Input: [[10,16], [2,8], [1,6], [7,12]]
Timeline view:
[1, 6]
|--------|
[2, 8]
|----------|
[7, 12]
|----------|
[10, 16]
|------------|
Overlapping groups:
Group 1: [1,6], [2,8], [7,12]
All overlap! One arrow can hit all 3!
Best position: x=7 (in all three ranges)
Group 2: [10,16], [7,12]
These overlap! One arrow can hit both!
Best position: x=11 (in both ranges)
But wait... [7,12] is in BOTH groups!
So actually:
Group 1: [1,6], [2,8] → Arrow at x=6
Group 2: [7,12], [10,16] → Arrow at x=11
Total: 2 arrows! ✓
🧠 The AHA Moment - Connection to Interval Problems
The Key Insight:
This problem is VERY similar to Non-overlapping Intervals!
Non-overlapping Intervals (Problem 292):
- Remove minimum to make non-overlapping
- Each removal = 1 interval gone
Minimum Arrows (This problem):
- Group overlapping balloons
- Each group = 1 arrow needed
Connection:
Number of arrows = Number of non-overlapping groups!
Visual Discovery - Why Greedy Works
Think about it step by step:
Step 1: Sort balloons by END position (just like before!)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Why end position?
- Balloons ending early can be grouped with more balloons!
- Same logic as Activity Selection!
Step 2: Process balloons greedily
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
For each balloon:
- Can current arrow hit this balloon?
- YES → Great! Same arrow, no cost!
- NO → Need new arrow!
Example:
[[1,6], [2,8], [7,12], [10,16]]
(sorted by end: [1,6], [2,8], [10,16], [7,12])
Actually after sorting by end:
[[1,6], [2,8], [7,12], [10,16]]
Detailed Example - Building Intuition
Input: [[10,16], [2,8], [1,6], [7,12]]
Sort by END position:
[[1,6], [2,8], [7,12], [10,16]]
end=6 end=8 end=12 end=16
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [1,6]: start=1, end=6
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
First balloon!
Need an arrow to burst it.
Where should we shoot?
- Anywhere in [1, 6] will burst it
- But we want to maximize future balloons hit too!
- Choose END position (6) - why?
Because next balloons are sorted by end
If they overlap with this, they'll overlap at the END!
Decision:
arrows = 1
lastArrowPos = 6 (shoot at the END of current balloon)
Visual:
[1, 6]
|--------|
↑ Arrow at x=6
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [2,8]: start=2, end=8
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Check: Can arrow at x=6 hit this balloon?
Does 2 <= 6 <= 8? YES! ✓
This balloon overlaps with previous!
Same arrow can burst both!
Decision:
arrows = 1 (no new arrow needed)
lastArrowPos = 6 (arrow position unchanged)
Visual:
[1, 6]
|--------|
↑
[2, 8]
|----------|
↑ Same arrow at x=6 hits both!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [7,12]: start=7, end=12
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Check: Can arrow at x=6 hit this balloon?
Does 7 <= 6 <= 12? NO! (6 < 7, arrow is too left)
This balloon does NOT overlap with previous group!
Need a NEW arrow!
Decision:
arrows = 2 (need new arrow)
lastArrowPos = 12 (shoot at END of this balloon)
Visual:
[1, 6] [7, 12]
|--------| |----------|
↑ ↑
Arrow 1 at x=6 Arrow 2 at x=12
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Process [10,16]: start=10, end=16
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Check: Can arrow at x=12 hit this balloon?
Does 10 <= 12 <= 16? YES! ✓
This balloon overlaps with [7,12]!
Same arrow (Arrow 2) can burst both!
Decision:
arrows = 2 (no new arrow needed)
lastArrowPos = 12 (arrow position unchanged)
Visual:
[1, 6] [7, 12]
|--------| |----------|
↑ ↑
[10, 16]
|-------------|
↑ Arrow 2 at x=12 hits both!
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Total arrows: 2
Arrow 1 at x=6: Bursts [1,6] and [2,8]
Arrow 2 at x=12: Bursts [7,12] and [10,16]
All balloons burst with minimum arrows! ✓
The Greedy Property
Why does shooting at END position work?
Key Insight:
We sorted by end position (ascending)
So next balloons have equal or larger end positions
If we shoot at the END of current balloon:
- Current balloon is definitely hit ✓
- Any balloon that OVERLAPS will also be hit ✓
- Balloons that don't overlap won't be hit (need new arrow)
This maximizes balloons hit per arrow!
Why END, not START?
If we shot at START:
- Current balloon hit ✓
- But might miss overlapping balloons that start later!
END is the "latest safe position" for current group!
🟢 Approach: Greedy with Sorting (Optimal)
🎨 Building the Complete Solution
Step 1: Why This is Similar to Non-overlapping Intervals
Non-overlapping Intervals (292):
- Count how many non-overlapping groups exist
- Remove overlaps
Minimum Arrows (293):
- Count how many non-overlapping groups exist
- Each group needs one arrow!
SAME PATTERN! Just different interpretation! 🎯
Step 2: The Algorithm
1. Sort balloons by END position (ascending)
2. Initialize:
arrows = 1 (need at least one arrow)
lastArrowPos = end of first balloon
3. For each balloon:
If balloon.start > lastArrowPos:
- New group! (doesn't overlap with previous)
- Need new arrow
- Update lastArrowPos = balloon.end
Else:
- Same group! (overlaps with previous)
- Current arrow can hit this balloon too
4. Return arrows count
📝 Implementation - Clean and Simple
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
// Sort by END position (ascending)
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 1; // Need at least one arrow
int lastArrowPos = points[0][1]; // Shoot at end of first balloon
for (int i = 1; i < points.length; i++) {
// If current balloon starts after last arrow position
if (points[i][0] > lastArrowPos) {
// Need new arrow!
arrows++;
lastArrowPos = points[i][1]; // Shoot at end of this balloon
}
// Else: current arrow already hits this balloon
}
return arrows;
}
}
🔍 Complete Dry Run
Input: [[10,16], [2,8], [1,6], [7,12]]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Sort by end position
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Before: [[10,16], [2,8], [1,6], [7,12]]
After: [[1,6], [2,8], [7,12], [10,16]]
end=6 end=8 end=12 end=16
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 2: Initialize
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
arrows = 1
lastArrowPos = 6 (end of first balloon [1,6])
Think: "First arrow shoots at x=6"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 3: Process remaining balloons
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=1: [2,8]
start=2, end=8
Check: start (2) > lastArrowPos (6)?
2 > 6? NO (2 <= 6)
Meaning: Arrow at x=6 can hit balloon [2,8]
Because 2 <= 6 <= 8 ✓
Decision: Same arrow! No new arrow needed.
arrows = 1
lastArrowPos = 6 (unchanged)
i=2: [7,12]
start=7, end=12
Check: start (7) > lastArrowPos (6)?
7 > 6? YES! ✓
Meaning: Arrow at x=6 CANNOT hit balloon [7,12]
Because 6 < 7 (arrow is left of balloon)
Decision: Need NEW arrow!
arrows = 2
lastArrowPos = 12 (shoot at end of [7,12])
i=3: [10,16]
start=10, end=16
Check: start (10) > lastArrowPos (12)?
10 > 12? NO (10 <= 12)
Meaning: Arrow at x=12 can hit balloon [10,16]
Because 10 <= 12 <= 16 ✓
Decision: Same arrow! No new arrow needed.
arrows = 2
lastArrowPos = 12 (unchanged)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
arrows = 2 ✓
Arrow positions:
Arrow 1 at x=6: Hits [1,6], [2,8]
Arrow 2 at x=12: Hits [7,12], [10,16]
All balloons burst! ✓
📊 Complexity Analysis
Time Complexity: O(n log n)
Sorting: O(n log n)
Single pass: O(n)
Total: O(n log n)
OPTIMAL! 🎯
Space Complexity: O(1) or O(log n)
No extra space except for sorting
Sorting may use O(log n) recursion stack
⚠️ Important Edge Case - Integer Overflow
The Problem:
Constraints say:
-2^31 <= xstart < xend <= 2^31 - 1
This means values can be at INTEGER limits!
Example:
points = [[-2147483648, 2147483647]]
If we use: (a, b) -> a[1] - b[1]
This could OVERFLOW!
a[1] = 2147483647 (max int)
b[1] = -2147483648 (min int)
a[1] - b[1] = overflow! ⚠️
The Solution:
// ❌ WRONG: Can overflow
Arrays.sort(points, (a, b) -> a[1] - b[1]);
// ✓ CORRECT: Use Integer.compare
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
Why Integer.compare works:
- Handles overflow safely
- Returns -1, 0, or 1 without subtraction
- Always safe for any integer values!
🎯 Key Insights Summary
The Three Critical Points:
1. Same Pattern as Non-overlapping Intervals
Non-overlapping Intervals:
Count non-overlapping groups → remove overlaps
Minimum Arrows:
Count non-overlapping groups → each needs arrow
SAME algorithm, different interpretation! ✓
2. Sort by END Position
Why END?
- Balloons sorted by end
- Shoot at END of current balloon
- Maximizes future balloons that can be hit
- Same logic as Activity Selection!
3. Greedy is Optimal
Each arrow should hit maximum balloons possible
Shooting at END of earliest-ending balloon:
- Hits current balloon ✓
- Hits all overlapping balloons ✓
- Minimizes total arrows needed ✓
🎓 Comparison with Non-overlapping Intervals
┌────────────────────────┬─────────────────────┬──────────────────────┐
│ Aspect │ Non-overlapping │ Minimum Arrows │
├────────────────────────┼─────────────────────┼──────────────────────┤
│ Problem │ Remove overlaps │ Burst balloons │
│ Goal │ Min removals │ Min arrows │
│ Interpretation │ Keep max intervals │ Count groups │
│ Overlap handling │ Remove one │ Use same arrow │
│ Result │ n - maxKept │ numGroups │
│ Algorithm │ Same! │ Same! │
│ Sort by │ End position │ End position │
│ Complexity │ O(n log n) │ O(n log n) │
└────────────────────────┴─────────────────────┴──────────────────────┘
Key Difference:
292: "Remove overlapping ones" → count removals
293: "Group overlapping ones" → count groups
Same greedy algorithm, different perspective! 🎯
⚠️ Common Mistakes
// Mistake 1: Using subtraction for sorting (can overflow!)
Arrays.sort(points, (a, b) -> a[1] - b[1]); // ❌
// ✓ CORRECT:
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
// Mistake 2: Sorting by start instead of end
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0])); // ❌
// ✓ CORRECT:
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
// Mistake 3: Wrong overlap check (using >= instead of >)
if (points[i][0] >= lastArrowPos) { // ❌ Should be >
// ✓ CORRECT:
if (points[i][0] > lastArrowPos) {
// Mistake 4: Not handling empty array
Arrays.sort(points, ...); // ❌ Crashes on empty!
// ✓ CORRECT:
if (points.length == 0) return 0;
📝 Quick Revision Notes
🎯 Core Concept
Problem: Minimum arrows to burst all balloons
Key Insight: Count non-overlapping groups (same as Problem 292!)
Algorithm: 1. Sort by END position 2. For each balloon: - If overlaps with previous → same arrow - If doesn't overlap → new arrow 3. Count arrows
Why It Works: Shooting at END maximizes balloons hit per arrow!
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int findMinArrowShots(int[][] a) {
return greedy(a);
}
private int greedy(int[][] a) {
// Approach: no logic, only observation
// step 1: sort by 2nd index (ascending) alone
// initial: { 10, 16 }, { 2, 8 }, { 1, 6 }, { 7, 12 }
// sorted: { 1, 6 }, { 2, 8 }, { 7, 12 }, { 10, 16 }
// If we draw it on a paper, its very easily intuitive.
Arrays.sort(a, (p1, p2) -> p1[1] - p2[1]);
int n = a.length;
int arrows = 1;
int[] prev = a[0];
for (int i = 1; i < n; i++) {
// step 2: increment arrows only if last interval
// END falls in between the current interval.
// If no overlap, update prev
if (prev[1] >= a[i][0] && prev[1] <= a[i][1]) {
continue;
} else {
arrows++;
prev = a[i];
}
}
return arrows;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(
s.findMinArrowShots(new int[][] { { 10, 16 }, { 2, 8 }, { 1, 6 }, { 7, 12 } }) == 2);
System.out.println(
s.findMinArrowShots(new int[][] { { 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 } }) == 4);
System.out.println(
s.findMinArrowShots(new int[][] { { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 } }) == 2);
}
}
🔑 Key Points
✓ Sort by END position (not start!)
✓ Use Integer.compare (avoid overflow!)
✓ Check start > lastEnd (not >=)
✓ Same pattern as Non-overlapping Intervals
✓ Time: O(n log n), Space: O(1)
✓ Count groups, not removals
🎪 Memory Aid
"Sort by end, shoot to extend!"
"END position, best rendition!"
"Same as 292, just different story!"
"Group the balloons, count theoons!" ✨
🎉 Congratulations!
You've mastered Minimum Number of Arrows to Burst Balloons!
What You Learned:
✅ Interval grouping - Count non-overlapping groups
✅ Same as Problem 292 - Different interpretation
✅ Greedy strategy - Sort by end, shoot at end
✅ Edge cases - Integer overflow handling
✅ Pattern recognition - Activity Selection variant
The Beautiful Connection:
Problem 292: Non-overlapping Intervals
"Keep maximum non-overlapping"
Answer = Total - MaxKept
Problem 293: Minimum Arrows
"Count non-overlapping groups"
Answer = NumberOfGroups
SAME ALGORITHM, DIFFERENT LENS! 🎯
The core insight:
Sort by END position
Process greedily
Count transitions between groups
This pattern appears in MANY problems:
- Meeting rooms
- Task scheduling
- Resource allocation
Master this pattern = Master many problems! ✨
Interview Mastery:
When asked about Minimum Arrows:
1. Recognize pattern: "This is like Non-overlapping Intervals!"
2. Explain connection: "We're counting non-overlapping groups.
Each group needs one arrow."
3. Algorithm: "Sort by end position, shoot at end.
Count how many times we need a new arrow."
4. Code it: Clean O(n log n) solution
5. Edge case: "Use Integer.compare to avoid overflow!"
Shows you recognize patterns across problems! 💯
You've mastered another interval problem with the greedy pattern! 🚀✨🎯