452. Minimum Number of Arrows to Burst Balloons - Explanation

Problem Link

1. Greedy (Sort By Start Value)

Intuition

Think of each balloon as a horizontal range on a number line. If two balloons overlap, a single arrow can pop both. The key insight is that by sorting balloons by their starting position, we can process them left to right and greedily merge overlapping intervals.

When we encounter a new balloon, we check if it overlaps with the previous group. If it does, we shrink the overlap region by taking the minimum of the end values. If not, we need a new arrow. We start by assuming each balloon needs its own arrow, then subtract one for each overlap we find.

Algorithm

1. Sort the intervals by their starting position.
2. Initialize res as the total number of balloons and track the previous interval's end.
3. For each subsequent balloon:
   • If it overlaps with the previous group (its start is at or before the tracked end), decrement res and update the tracked end to be the minimum of both ends.
   • Otherwise, start a new group by updating the tracked end to this balloon's end.
4. Return res.

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort()
        res, prevEnd = len(points), points[0][1]

        for i in range(1, len(points)):
            curr = points[i]
            if curr[0] <= prevEnd:
                res -= 1
                prevEnd = min(curr[1], prevEnd)
            else:
                prevEnd = curr[1]

        return res

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

---

2. Greedy (Sort By End Value)

Intuition

Sorting by end position offers a cleaner greedy approach. By shooting an arrow at the end of the first balloon, we maximize the chance of hitting subsequent balloons. Each balloon that starts after our current arrow position requires a new arrow.

This is a classic interval scheduling pattern: always pick the earliest finishing interval first. When we shoot at the end of a balloon, any other balloon that overlaps must have started before or at that point.

Algorithm

1. Sort the balloons by their ending position.
2. Start with one arrow at the end of the first balloon.
3. For each subsequent balloon:
   • If it starts after the current arrow position, shoot a new arrow at this balloon's end and increment res.
   • Otherwise, the current arrow already covers this balloon.
4. Return the total arrow count.

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[1])
        res, prevEnd = 1, points[0][1]

        for i in range(1, len(points)):
            if points[i][0] > prevEnd:
                prevEnd = points[i][1]
                res += 1

        return res

Time & Space Complexity

• Time complexity: $O(n \log n)$
• Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

---

Common Pitfalls

Using Subtraction for Comparator with Large Values

When sorting intervals with coordinates that can be very large (up to 2^31 - 1) or very small (down to -2^31), using a[0] - b[0] as a comparator can cause integer overflow. For example, comparing [-2147483648, 0] with [2147483647, 0] would overflow. Always use Integer.compare(a[0], b[0]) in Java or explicit comparison operators like a[0] < b[0] in other languages.

Not Updating the Overlap Region Correctly

When merging overlapping balloons, you must shrink the overlap region by taking the minimum of the end values, not the maximum. If balloon A ends at 6 and balloon B ends at 4, the arrow must be shot at or before position 4 to hit both. Forgetting to update prevEnd = min(curr[1], prevEnd) will cause incorrect counts when a later balloon extends beyond the current overlap region.

Confusing Inclusive vs Exclusive Overlap Checks

The problem states that balloons touching at a single point can be burst by one arrow. This means the overlap check should be curr[0] <= prevEnd (inclusive), not curr[0] < prevEnd. Missing this edge case will count extra arrows for balloons that just touch at their boundaries.