Minimum Number of Arrows to Burst Balloons

Difficulty: Medium
Topics: Array, Greedy, Sorting
Link: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/

Problem Description

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:


Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:


Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:


Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

Solution

1. Problem Deconstruction (500+ words)

Technical Reformulation: We are given a collection of intervals [xstart, xend] representing balloons’ horizontal positions. Arrows shot vertically from the x-axis can burst multiple balloons if their x-coordinates fall within the balloons’ intervals. The objective is to find the minimum cardinality set of x-coordinates such that every interval contains at least one of these x-coordinates. This is equivalent to finding the minimum number of points that pierce all intervals, known as the “interval point cover” problem.

Beginner-Friendly Version: Imagine balloons stuck on a wall at different horizontal positions. You have arrows that shoot straight up. An arrow can pop multiple balloons if they’re aligned vertically. Your goal is to pop all balloons using the fewest arrows possible by choosing smart shooting positions along the bottom of the wall.

Mathematical Formulation: Let $B = \{[s_i, e_i]\}_{i=1}^n$ be a set of intervals. Find the smallest set $P = \{p_1, p_2, ..., p_k\}$ of points such that for every interval $[s_i, e_i]$ , there exists some $p_j \in P$ with $s_i \leq p_j \leq e_i$ .

Constraint Analysis:

1 <= points.length <= 10^5: Rules out O(n²) solutions. Requires O(n log n) or better.
points[i].length == 2: Consistent input format, no need to handle variable-length subarrays.
-2^31 <= xstart < xend <= 2^31 - 1: Large range prevents coordinate compression. Integer overflow possible if using 32-bit integers.
Hidden edge cases: Single balloon, nested intervals, disjoint intervals, intervals sharing endpoints.

2. Intuition Scaffolding

Real-World Metaphor: Imagine scheduling meetings in rooms where each balloon represents a meeting time slot. Arrows represent room allocations. We want to minimize rooms needed for all meetings.

Gaming Analogy: In a tower defense game, balloons move along fixed horizontal paths. We need to place the fewest towers (that shoot vertically) to hit all balloon paths.

Math Analogy: Finding the chromatic number of an interval graph where edges represent overlapping intervals.

Common Pitfalls:

Shooting at every balloon’s start: Fails for overlapping balloons
Greedy by balloon width: Narrow balloons might be covered by others
Sorting by start position only: May miss optimal grouping
Ignoring endpoint equality: Critical for intervals that share endpoints
Not considering negative numbers: Sorting and comparison must handle negatives

3. Approach Encyclopedia

Brute Force Approach:

def findMinArrowShots(points):
    if not points: return 0
    
    # Generate all possible arrow positions
    all_positions = set()
    for start, end in points:
        all_positions.add(start)
        all_positions.add(end)
    
    positions = sorted(all_positions)
    min_arrows = float('inf')
    
    # Try all subsets of positions (exponential)
    def can_cover(arrows):
        for start, end in points:
            covered = False
            for arrow in arrows:
                if start <= arrow <= end:
                    covered = True
                    break
            if not covered:
                return False
        return True
    
    # This is impractical but shows the problem nature
    # Actual implementation would use bitmask but still infeasible
    return "Brute force is infeasible for n=10^5"

Complexity: O(2^m × n) where m is number of distinct positions (up to 2×10^5) - completely infeasible.

Optimized Greedy Approach:

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

Arrow 1 at x=6: bursts [1,6],[2,8]
Arrow 2 at x=12: bursts [7,12],[10,16]

Visualization:

Balloons:     [1------6]
              [2--------8]
                         [7-----12]
                            [10-----16]
Arrows:        ^(6)           ^(12)

Optimal Greedy Algorithm:

def findMinArrowShots(points):
    if not points:
        return 0
    
    # Sort by ending position
    points.sort(key=lambda x: x[1])
    
    arrows = 0
    current_arrow = float('-inf')
    
    for start, end in points:
        # If current arrow can't burst this balloon
        if current_arrow < start:
            arrows += 1
            current_arrow = end  # Shoot at the end of this balloon
    
    return arrows

Complexity Proof:

Sorting: O(n log n) comparisons
Single pass: O(n) iterations
Space: O(1) excluding sort space (O(log n) for sort recursion stack)
Total: O(n log n) time, O(1) space

4. Code Deep Dive

def findMinArrowShots(points):
    if not points:
        return 0  # Handle empty input
    
    # Sort intervals by their ending coordinate
    # Why end? Because we want to place arrows as far right as possible
    # to maximize the number of balloons we can burst
    points.sort(key=lambda x: x[1])
    
    arrows = 0  # Count of arrows needed
    current_arrow = float('-inf')  # Position of last arrow shot
    
    # Process each balloon in sorted order
    for start, end in points:
        # If the current arrow cannot burst this balloon
        # (current_arrow < start means arrow is left of balloon)
        if current_arrow < start:
            arrows += 1  # We need a new arrow
            current_arrow = end  # Place it at the balloon's end
            
            # Visualize: 
            # Balloon: [start-------end]
            # Arrow:              ^(end)
            # This arrow will burst all balloons starting before 'end'
    
    return arrows

Edge Case Handling:

Example 1: [[10,16],[2,8],[1,6],[7,12]]
- Sorted: [[1,6],[2,8],[7,12],[10,16]]
- Arrow 1 at 6 covers [1,6],[2,8]
- Arrow 2 at 12 covers [7,12],[10,16]
Example 3: [[1,2],[2,3],[3,4],[4,5]]
- Sorted: [[1,2],[2,3],[3,4],[4,5]]
- Arrow 1 at 2 covers [1,2],[2,3]
- Arrow 2 at 4 covers [3,4],[4,5]

5. Complexity War Room

Hardware-Aware Analysis:

With n=10^5, sorting uses ~O(n log n) ≈ 1.6×10^6 operations
Memory: ~800KB for storing intervals (2×10^5 integers × 4 bytes)
Fits comfortably in L2/L3 cache of modern processors

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(2^m × n)	O(m)	5/10	❌ Impossible
Sort by Start	O(n log n)	O(1)	8/10	✅ Good
Sort by End (Optimal)	O(n log n)	O(1)	9/10	✅ Excellent

6. Pro Mode Extras

Variants Section:

Weighted Intervals: Each balloon has a weight, maximize total weight burst with k arrows
Multi-dimensional: Balloons exist in 2D space, arrows shot from any direction
Limited Arrows: Given maximum k arrows, maximize balloons burst
LC 435 Non-overlapping Intervals: Remove minimum intervals to make non-overlapping

Interview Cheat Sheet:

First Mention: “This is an interval scheduling problem solvable with greedy”
Key Insight: “Sort by end position and place arrows at endpoints”
Complexity: “O(n log n) time, O(1) space excluding sort”
Testing: Always test with shared endpoints and single element
Edge Cases: Empty input, single balloon, all balloons overlapping

Alternative Implementation (Sort by Start):

def findMinArrowShots(points):
    if not points: return 0
    
    points.sort(key=lambda x: x[0])  # Sort by start
    arrows = 0
    current_end = float('-inf')
    
    for start, end in points:
        if start > current_end:
            arrows += 1
            current_end = end
        else:
            current_end = min(current_end, end)
    
    return arrows

Both approaches yield the same result but the end-sorting version is more intuitive for this specific problem.

#452 - Minimum Number of Arrows to Burst Balloons