MediumNeetCode150ArrayGreedySorting
Minimum Number of Arrows to Burst Balloons
Find minimum arrows to burst all balloons.
Examples
Input
points = [[10,16],[2,8],[1,6],[7,12]]
Output
2
Arrow at x=6 bursts [2,8] and [1,6], arrow at x=11 bursts [10,16] and [7,12].
Constraints
- •
1 <= points.length <= 10^4 - •
points[i].length == 2 - •
-2^31 <= xstart < xend <= 2^31-1
Approaches
Try all combinations.
CodeT: O(n^2) | S: O(1)
Sort by end point.
CodeT: O(n log n) | S: O(1) after sort
Same approach.
CodeT: O(n log n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Try all combinations. |
| Sort + Greedy | O(n log n) | O(1) after sort | Sort by end point. |
| Greedy Optimized | O(n log n) | O(1) | Same approach. |
Brute Force
T: O(n^2)S: O(1)
Try all combinations.
Sort + Greedy
T: O(n log n)S: O(1) after sort
Sort by end point.
Greedy Optimized
T: O(n log n)S: O(1)
Same approach.
Common Mistakes
Wrong sort key
Off-by-one in overlap check
Not counting arrows correctly