Minimum Number of Arrows to Burst Balloons — LeetCode 452 Greedy

Problem Statement#

Each balloon spans a horizontal interval. An arrow shot vertically at x bursts every balloon whose interval contains x. Find the minimum number of arrows to burst all balloons.

Constraints:

• 1 <= points.length <= 10^5
• points[i].length == 2
• -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#

Burst Balloons (LeetCode 452) is a top-50 frequency problem at Meta, Amazon, and Google. It is the cousin of Non-Overlapping Intervals — same sort-by-end skeleton, slightly different invariant. Recruiters use it to verify that you do not just memorize one template but understand when overlap definitions shift.

The trap: sorting by end with naive integer comparison can overflow because endpoints span 2^31. JavaScript subtraction-based comparators silently fail. Top candidates use explicit comparison.

This problem trains you for richer interval problems like Meeting Rooms II and Maximum CPU Load. The cluster-counting mental model recurs in DBSCAN-like clustering interviews and even in compiler register allocation.

The Core Insight#

Greedy choice: shoot the arrow at the smallest end among unburst balloons. Every balloon whose start is at or before this end shares the cluster and is burst. Then advance past all of them.

Note: touching at endpoints DOES count as overlap here (problem says contains is inclusive). So the comparison is start <= prev_end, contrast with LeetCode 435 which uses >=.

Visual Dry Run#

Solution (Optimal)#

class Solution:
    def findMinArrowShots(self, points):
        if not points:
            return 0
        points.sort(key=lambda p: p[1])
        arrows = 1
        prev_end = points[0][1]
        for start, end in points[1:]:
            if start > prev_end:
                arrows += 1
                prev_end = end
        return arrows

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

Time: O(n log n) — sort dominates Space: O(1) extra

Common Mistakes#

• Using (a, b) => a[1] - b[1] in JavaScript — overflows for endpoints near 2^31
• Sorting by start — fails on [[10,16],[2,8],[1,6],[7,12]]
• Using >= instead of > — incorrect because touching endpoints share a single arrow
• Forgetting the empty-array edge case
• Shooting at the start instead of the end — start can advance, end is the safe binding point

Interview Tips#

• Mention the integer-overflow pitfall in JavaScript explicitly
• Compare and contrast with LeetCode 435 to show you understand the inclusive vs exclusive boundary
• Sketch a number line and draw clusters before coding

Follow-up Questions#

• What if arrows can be shot at any angle? Hint: this becomes a hitting-set problem (NP-hard generally)
• What if balloons move over time? Hint: sweep line with events
• 2D balloons (rectangles) — minimum vertical lines to hit all? Hint: project to one axis
• Each balloon has a cost to leave alive — minimize cost? Hint: weighted interval cover, DP
• How to parallelize for 10^9 balloons? Hint: bucket by region and merge

Key Takeaways#

• LeetCode 452 is solved by sort-by-end greedy in O(n log n)
• Use start > prev_end because touching balloons share an arrow
• Always use explicit comparator in JavaScript to avoid 2^31 overflow
• Same exchange argument as Non-Overlapping Intervals
• Each cluster of mutually overlapping balloons needs exactly one arrow
• prev_end becomes the binding constraint, not the current balloon's start
• Output equals number of clusters formed during the sweep