Minimum Number of Arrows to Burst Balloons - Solution
Solutions and explanations

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0

        points.sort()   # Sort by start point
        arrows = 1
        prev_overlap_end = points[0][1] # Tracks the rightmost boundary of the current overlapping balloon group
        for start, end in points[1:]:
            if start <= prev_overlap_end:   # Overlap detected, so update overlap window
                prev_overlap_end = min(prev_overlap_end, end)
            else:       # No overlap, so we need another arrow for the new group
                arrows += 1
                prev_overlap_end = end
        return arrows

Complexity Analysis

Here, n represents the number of balloons in the input array.

  • Time Complexity: O(n log n), dominated by the sorting step.
  • Space Complexity: O(1) or O(n) depending on whether sorting is done in place or not.