Code Implementation

class Solution:
    def findMinArrowShots(self, points):
        if not points:
            return 0
        # Sort balloons by their ending x coordinate
        points.sort(key=lambda x: x[1])
        arrows = 1
        end = points[0][1]
        for x_start, x_end in points[1:]:
            if x_start > end:
                arrows += 1
                end = x_end
        return arrows
      

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) return 0;
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        int arrows = 1;
        int end = points[0][1];
        for (int i = 1; i < points.size(); ++i) {
            if (points[i][0] > end) {
                ++arrows;
                end = points[i][1];
            }
        }
        return arrows;
    }
};
      

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 arrows = 1;
        int end = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > end) {
                arrows++;
                end = points[i][1];
            }
        }
        return arrows;
    }
}
      

var findMinArrowShots = function(points) {
    if (!points.length) return 0;
    points.sort((a, b) => a[1] - b[1]);
    let arrows = 1;
    let end = points[0][1];
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > end) {
            arrows++;
            end = points[i][1];
        }
    }
    return arrows;
};
      

Problem Description

Thought Process

Solution Approach

• Step 1: Sort the Balloons
  Sort the list of balloons (intervals) by their ending x-coordinate (x_end). This helps us efficiently find the minimal set of non-overlapping intervals.
• Step 2: Initialize Counters
  Start with one arrow (since at least one balloon exists), and set a variable to track the end of the first interval.
• Step 3: Iterate Through Balloons
  For each balloon, check if its start position is after the end position of the last burst group. If so, it means this balloon does not overlap with the previous group, and a new arrow is needed.
• Step 4: Update Arrow Placement
  When a new arrow is needed, update your tracking variable to the end of the current balloon's interval.
• Step 5: Return the Arrow Count
  After iterating through all balloons, the arrow count will represent the minimum number of arrows required.

This greedy approach works because, by always shooting at the earliest possible end, you maximize the number of balloons burst with each arrow, ensuring optimality.

Example Walkthrough

• First, sort the intervals by end: [[1,6],[2,8],[7,12],[10,16]]
• Start with one arrow at position 6 (end of first interval).
• The second balloon [2,8] starts at 2 (before 6), so it overlaps—no new arrow needed.
• The third balloon [7,12] starts at 7 (after 6), so it does not overlap—shoot a new arrow at 12.
• The fourth balloon [10,16] starts at 10 (before 12), so it overlaps—no new arrow needed.

Result: 2 arrows are needed—one at x=6 (covering the first two balloons), and one at x=12 (covering the last two).

Time and Space Complexity

• Brute-force Approach: Checking every possible x-coordinate or every pair of balloons is O(n²) or worse, which is infeasible for large inputs.
• Optimized Greedy Approach:
  • Time Complexity: O(n log n), due to sorting the intervals.
  • Space Complexity: O(1) additional space (excluding the space used for sorting, which may be O(n) depending on the language).

The greedy solution is efficient and scalable for large input sizes.

Summary