🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires determining the minimum number of vertical arrows needed to burst all the balloons. Each balloon is represented by its horizontal diameter on the x-axis. By shooting an arrow at the end of an interval, we can maximize the number of balloons burst with a single shot, as it ensures covering the largest possible range of overlapping balloons.
Approach
- Sorting: First, sort the list of intervals by their end coordinates. This allows us to efficiently determine the minimum number of arrows by always aiming at the end of the current interval.
- Initialization: Initialize a variable to keep track of the current position of the arrow (
current_shot_x
) set to the end of the first interval. Initialize a counter (res
) to count the number of arrows needed. - Iterate Through Intervals: Loop through the sorted list of intervals:
- For each interval, check if the start of the current interval is greater than
current_shot_x
. If true, it indicates that the current interval is not covered by the current arrow, so we need to shoot a new arrow. Updatecurrent_shot_x
to the end of the current interval and increment the counterres
. - Return Result: The counter
res
now contains the minimum number of arrows needed to burst all balloons.
Complexity
Time Complexity:
O(n log n) due to sorting, where n is the number of intervals. The iteration through the intervals takes linear time O(n).
Space Complexity:
O(1) if we don't count the input array, as no additional space proportional to the input size is used.
Code
C++
class Solution {
public:
int findMinArrowShots(vector>& points) {
if (points.empty()) return 0;
sort(points.begin(), points.end(), [](const vector& a, const vector& b) {
return a[1] < b[1];
});
int currentShotX = points[0][1];
int res = 1;
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > currentShotX) {
currentShotX = points[i][1];
res++;
}
}
return res;
}
};
Python
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x: x[1])
current_shot_x = points[0][1]
res = 1
for i in range(1, len(points)):
if points[i][0] > current_shot_x:
current_shot_x = points[i][1]
res += 1
return res
Java
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) return 0;
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int currentShotX = points[0][1];
int res = 1;
for (int i = 1; i < points.length; i++) {
if (points[i][0] > currentShotX) {
currentShotX = points[i][1];
res++;
}
}
return res;
}
}
JavaScript
var findMinArrowShots = function(points) {
points.sort((a, b) => a[1] - b[1]);
let currentShotX = points[0][1];
let res = 1;
for (let i = 1; i < points.length; i++) {
if (points[i][0] > currentShotX) {
currentShotX = points[i][1];
res++;
}
}
return res;
};