Minimum Number of Arrows to Burst Balloons
Problem
Given a list of points where each point represents the start and end coordinates of a balloon on a horizontal axis, return the minimum number of arrows required to burst all balloons, where an arrow can burst all balloons it passes through.
- 1 ≤ points.length ≤ 10⁵
- points[i].length == 2
- −2³¹ ≤ start_i ≤ end_i ≤ 2³¹ - 1
Example
points = [[10,16],[2,8],[1,6],[7,12]]2Sorting balloons by their end coordinate yields [[1,6],[2,8],[7,12],[10,16]]. The first arrow is shot at position 6, bursting balloons [1,6] and [2,8]. The second arrow is shot at position 12, bursting balloons [7,12] and [10,16]. This greedy choice of shooting at the earliest finishing balloon's end coordinate minimizes the total arrows needed.
Approach
Straightforward Solution
A brute-force approach would check every balloon against every other balloon to find overlaps, resulting in O(n^2) time complexity, which is infeasible for large inputs.
Core Observation
The problem reduces to covering intervals with the minimum number of points (arrows). The key insight is that shooting an arrow at the end of the earliest finishing balloon covers as many overlapping balloons as possible. Because an arrow can be placed anywhere within a balloon’s interval, placing it as late as possible (at the end) maximizes the chance that the same arrow will also intersect future balloons that start later but still overlap that position.
Path to Optimal
Sorting balloons by their end coordinate allows a greedy strategy: always shoot an arrow at the end of the first balloon, then skip all balloons that overlap with this arrow. This reduces the problem to a linear scan after sorting, achieving O(n log n) time due to sorting.
Optimal Approach
PreviewSort the balloons by their end coordinate. Initialize the arrow count to 1 and set the arrow position to the end of the first balloon…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n log n)
Sorting the list of balloons by their end coordinate takes O(n log n). The subsequent single pass through the sorted list takes O(n), resulting in overall O(n log n) time.
Space
O(1)
The algorithm uses a constant amount of extra space for counters and pointers, excluding the input array which is sorted in-place.
Pattern Spotlight
Greedy Algorithms (Interval Scheduling)
When covering intervals with points, always pick the earliest finishing interval's end as the point to cover maximum intervals, then skip all intervals overlapping this point before moving to the next uncovered interval.
Solution
| 1 | class Solution: |
| 2 | def findMinArrowShots(self, points: List[List[int]]) -> int: |
| 3 | |
| 4 | points.sort(key=lambda x: x[1]) |
| 5 | |
| 6 | arrows = 1 |
| 7 | arrow_pos = points[0][1] |
| 8 | |
| 9 | for start, end in points: |
| 10 | if start > arrow_pos: |
| 11 | arrows += 1 |
| 12 | arrow_pos = end |
| 13 | |
| 14 | return arrows |
Step-by-Step Solution
Sort Balloons by Their End Coordinates to Enable Greedy Coverage
| 4 | points.sort(key=lambda x: x[1]) |
Objective
To order balloons so that the earliest finishing balloon is considered first, enabling a greedy strategy to minimize arrows.
Key Insight
Sorting by end coordinate ensures that when an arrow is shot at the end of the first balloon, it covers all balloons overlapping that point. This ordering is crucial because it allows the algorithm to make a locally optimal choice that leads to a globally optimal solution.
Interview Quick-Check
Core Logic
Sorting by end coordinate is the foundation of the greedy interval scheduling approach, enabling linear-time coverage after sorting.
Common Pitfalls & Bugs
Sorting by start coordinate instead of end coordinate can lead to suboptimal arrow placement and incorrect results.
Initialize Arrow Count and Position Based on First Balloon
To set the initial arrow count and position to cover the first balloon and any overlapping balloons.
Iterate Through Balloons to Count Additional Arrows Needed
To scan through the sorted balloons and increment arrow count when a balloon is not covered by the current arrow position.
Return the Total Number of Arrows Required
To output the minimum number of arrows needed to burst all balloons after processing all intervals.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
points.sort(key=lambda x: x[1])Sort the list of balloons by their end coordinate in ascending order.
Sorting by end coordinate enables the greedy strategy to always pick the earliest finishing balloon first, which maximizes the number of balloons burst by a single arrow.
if start > arrow_pos:Check if the current balloon starts after the last arrow position, indicating it is not covered.
This condition identifies when a new arrow is needed because the current arrow cannot burst this balloon due to non-overlapping intervals.
arrow_pos = endUpdate the arrow position to the end of the current balloon for future coverage.
Resetting the arrow position to the current balloon's end maximizes coverage of subsequent overlapping balloons, maintaining the greedy strategy.
Full line-by-line criticality + rationale for all 8 lines available on Pro.
Test Your Understanding
Why does shooting an arrow at the end coordinate of the earliest finishing balloon guarantee a minimal number of arrows?
See the answer with Pro.
Related Problems
Greedy Algorithms pattern
Don't just read it. Drill it.
Reconstruct Minimum Number of Arrows to Burst Balloons from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Minimum Number of Arrows to Burst Balloons drill