452. Minimum Number of Arrows to Burst Balloons

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

1. 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.
2. 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.
3. 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. Update current_shot_x to the end of the current interval and increment the counter res.
4. 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;
};