Minimum Arrows to Burst Balloons — Greedy Interval Scheduling [LC 452]

Problem Statement#

Each balloon is represented by [x_start, x_end] indicating where it spans on a wall. An arrow shot from position x bursts all balloons where x_start <= x <= x_end. Find the minimum number of arrows needed to burst all balloons.

Constraints:

• 1 <= points.length <= 10^5
• -2^31 <= x_start < x_end <= 2^31 - 1

Input:  points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2

Input:  points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4

Why This Problem Matters#

LeetCode 452 is a staple greedy interview problem at Amazon, Google, and Microsoft. It belongs to the interval scheduling family — problems where you sort by one endpoint and greedily make decisions. The exact same structure appears in Meeting Rooms, Non-overlapping Intervals (LC 435), and Jump Game II.

The problem tests whether you can identify the right sort order (by end coordinate, not start) and articulate the greedy invariant: always shoot at the rightmost possible point that still hits the current cluster. This deferred shooting strategy maximizes how many subsequent balloons each arrow can reach.

The Core Insight#

Sort by end coordinate. After sorting:

• Shoot the first arrow at the end coordinate of the first balloon (arrow = points[0][1])
• For each subsequent balloon, if its start is beyond the current arrow position, the arrow misses — shoot a new arrow at this balloon's end coordinate
• Otherwise, this balloon is hit by the current arrow — no action needed

Why sort by end, not start? Sorting by end ensures that when we shoot at the end of the current balloon, we maximize overlap with future balloons. If we sorted by start, we might place an arrow too far left and miss balloons that start slightly later.

Greedy invariant: Place each arrow as far right as possible (at the end of the leftmost unresolved balloon after sorting). This maximizes the chance of hitting subsequent balloons.

Visual Dry Run#

points = [[10,16],[2,8],[1,6],[7,12]]

Sorted by end: [[1,6],[2,8],[7,12],[10,16]]

Result: 2 arrows

Solution (Optimal)#

class Solution:
    def findMinArrowShots(self, points):
        points.sort(key=lambda x: x[1])  # sort by end coordinate
        arrows = 1
        arrow_pos = points[0][1]
        for start, end in points[1:]:
            if start > arrow_pos:         # current arrow misses this balloon
                arrows += 1
                arrow_pos = end           # shoot new arrow at this balloon's end
        return arrows

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

Time: O(n log n) — dominated by sorting Space: O(1) — no auxiliary data structures beyond sorting

Common Mistakes#

• Sorting by start instead of end — placing arrows too early misses opportunities to hit overlapping balloons
• Using >= instead of > for the miss condition — balloons touching at a single point can be hit by one arrow
• Initializing arrows to 0 without handling the first balloon separately — start with 1 arrow at the first balloon's end
• Integer overflow with large coordinates in some languages — use appropriate integer types
• Trying to track intersection intervals explicitly — unnecessary, arrow position alone suffices

Interview Tips#

• Start by explaining the sort choice: "sort by end so we can greedily place each arrow as far right as possible"
• Draw the balloon intervals on a number line and show the arrow positions visually
• Explain the greedy invariant: each arrow is at the maximum right position that still hits the most recent unresolved balloon
• Compare with Non-overlapping Intervals (LC 435): both sort by end, both count based on overlaps — very similar logic
• Handle the edge case: empty input returns 0 (the for loop doesn't trigger the first arrow)

Follow-up Questions#

• How is this related to Non-overlapping Intervals (LC 435)? (Both sort by end, both count non-overlapping groups; 435 removes intervals, 452 shoots arrows — same greedy)
• What if an arrow can only burst balloons within a range (not infinite reach)? (More complex interval placement — greedy may not apply directly)
• What if balloons can be burst in a specific order? (Ordering constraint changes the problem; use dynamic programming)
• How would you find the actual arrow positions, not just the count? (Track arrow_pos each time you increment arrows)
• What if touching at one point doesn't count as an overlap? (Change > to >= in the miss condition)

Key Takeaways#

• LeetCode 452 is asked at Amazon, Google, and Microsoft — classic greedy interval scheduling
• Sort by end coordinate (not start) — places each arrow as far right as possible, maximizing future balloon hits
• When a balloon's start exceeds the current arrow position, shoot a new arrow at this balloon's end
• Time O(n log n) for sorting, Space O(1) — optimal for this problem class
• Touching at one point counts as a hit — use strict > for the miss condition
• This is structurally identical to Non-overlapping Intervals (LC 435) — both are "maximum non-overlapping groups" problems
• The greedy invariant: always defer each arrow as far right as possible to maximize its reach over future balloons