Minimum Number of Arrows to Burst Balloons — Solution
Minimum Number of Arrows to Burst Balloons solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Number of Arrows to Burst Balloons is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Intervals
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Balloon i spans the horizontal interval [x_start, x_end]. An arrow shot straight up at x bursts every balloon whose interval contains x, endpoints included, and travels infinitely upwards.
Return the minimum number of arrows needed to burst all the balloons.
Example 1
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: Shoot at x = 6 and x = 12.
Example 2
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: Nothing overlaps.
Example 3
Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: Shoot at x = 2 and x = 4.
Constraints
1 <= points.length <= 100000points[i].length == 2-1000000000 <= x_start <= x_end <= 1000000000
Hints for Minimum Number of Arrows to Burst Balloons
Hint 1
Sort the balloons by their right endpoint.
Hint 2
Always shoot at the right endpoint of the earliest-ending balloon still unburst.
Hint 3
Every balloon whose start is at most that position is burst by the same arrow.
How to solve Minimum Number of Arrows to Burst Balloons
The classic interval-stabbing greedy. Sorting by right endpoint and always shooting at the earliest end bursts as many balloons as any single arrow can, without ever forcing an extra arrow later.
Approach
- Sort by right endpoint ascending.
- Shoot at the first balloon's right endpoint and remember it as
end. - Scan on: a balloon starting at or before
endis already burst; otherwise fire a new arrow at its right endpoint and updateend.
Why it works
Exchange argument: in any optimal solution, the arrow that bursts the earliest-ending balloon can be moved to that balloon's right endpoint without losing any balloon it already hit — every balloon it hit starts at or before that point and ends at or after it. Repeating the argument turns any optimal solution into the greedy one, so the greedy is optimal.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Sorting by the left endpoint needs a different rule and is easy to get wrong.
- Endpoints count as hits, so the test is
start > end, strictly. - Subtracting coordinates in a comparator can overflow a 32-bit
int; compare rather than subtract.
Reference solution
Python
from typing import List
def findMinArrowShots(points: List[List[int]]) -> int:
p = sorted(points, key=lambda iv: iv[1])
arrows, end = 1, p[0][1]
for start, finish in p[1:]:
if start > end:
arrows += 1
end = finish
return arrowsJava
public static int findMinArrowShots(int[][] points) {
int[][] p = points.clone();
Arrays.sort(p, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 1, end = p[0][1];
for (int i = 1; i < p.length; i++) {
if (p[i][0] > end) {
arrows++;
end = p[i][1];
}
}
return arrows;
}C++
int findMinArrowShots(vector<vector<int>>& points) {
vector<vector<int>> p = points;
sort(p.begin(), p.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
int arrows = 1, end = p[0][1];
for (int i = 1; i < (int) p.size(); i++) {
if (p[i][0] > end) {
arrows++;
end = p[i][1];
}
}
return arrows;
}JavaScript
var findMinArrowShots = function(points) {
var p = points.slice().sort(function(a, b) {
return a[1] < b[1] ? -1 : (a[1] > b[1] ? 1 : 0);
});
var arrows = 1, end = p[0][1];
for (var i = 1; i < p.length; i++) {
if (p[i][0] > end) { arrows++; end = p[i][1]; }
}
return arrows;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms