LeetCode 452 - Minimum Number of Arrows to Burst Balloons

LeetCode Problem 452

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

This problem is asking us to determine the minimum number of vertical arrows required to burst all balloons represented as intervals along the x-axis. Each balloon is defined by its start and end x-coordinates, [xstart, xend]. An arrow shot at position x bursts any balloon whose interval contains x. The arrows travel infinitely upward, so only the horizontal overlap matters.

The input is a list of integer pairs representing the balloon intervals. The output is a single integer representing the minimum number of arrows needed. Constraints indicate that the number of balloons can be large, up to 10^5, and the x-coordinates can span a wide range from -2^31 to 2^31-1. This means any solution must be efficient in both time and space.

Edge cases include: balloons with the same start and end, completely overlapping balloons, non-overlapping balloons, and a single balloon. The problem guarantees that xstart < xend for each balloon, so there are no zero-length intervals.

Approaches

The brute-force approach would involve iterating through all balloons and trying all possible arrow positions. One could select an arrow position for the first balloon, remove all balloons it bursts, and repeat until all balloons are gone. While correct, this approach is infeasible for large input sizes because it would involve nested iteration over potentially 10^5 balloons, giving a time complexity on the order of O(n²), which is too slow.

The key insight for an optimal solution comes from noticing that the problem can be solved greedily. If we sort balloons by their ending x-coordinate, we can always shoot an arrow at the end of the first balloon and it will burst all balloons that overlap with this point. We then skip all the balloons that are already burst and repeat. This works because shooting at the end of a balloon maximizes overlap with subsequent balloons, minimizing the total number of arrows.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Try all positions and count overlaps iteratively
Optimal	O(n log n)	O(1)	Sort intervals by end, greedily shoot arrow at interval ends

Algorithm Walkthrough

1. Check if the points array is empty. If so, return 0 because no arrows are needed.
2. Sort the balloon intervals by their ending x-coordinate. This ensures that we always consider the earliest finishing balloon first.
3. Initialize a counter for arrows to 1, since at least one arrow is needed for the first balloon.
4. Initialize a variable arrow_pos to the ending x-coordinate of the first balloon. This represents the x-position of the current arrow.
5. Iterate through the sorted list of balloons starting from the second balloon. For each balloon:

a. If the balloon's start x-coordinate is greater than arrow_pos, it means this balloon is not overlapped by the current arrow.

b. Increment the arrow counter and update arrow_pos to the end of the current balloon.

c. If the balloon's start is less than or equal to arrow_pos, it is already covered by the current arrow, so do nothing. 6. After iterating through all balloons, return the arrow counter.

Why it works: Sorting by end coordinate and always placing an arrow at the end ensures that each arrow covers as many overlapping balloons as possible. This greedy choice guarantees the minimum number of arrows because delaying the arrow would only require an additional arrow later.

Python Solution

from typing import List

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

The code first checks if the input is empty. It then sorts the balloons by their ending coordinates to facilitate the greedy approach. arrows starts at 1 because the first balloon needs at least one arrow. As we iterate, any balloon not overlapped by the current arrow triggers a new arrow, updating arrow_pos.

Go Solution

import "sort"

func findMinArrowShots(points [][]int) int {
    if len(points) == 0 {
        return 0
    }

    sort.Slice(points, func(i, j int) bool {
        return points[i][1] < points[j][1]
    })

    arrows := 1
    arrowPos := points[0][1]

    for _, p := range points[1:] {
        if p[0] > arrowPos {
            arrows++
            arrowPos = p[1]
        }
    }

    return arrows
}

In Go, we handle sorting with sort.Slice and explicitly manage array slicing. The logic is the same as Python. Go requires careful handling of slices and avoids nil checks as we only check the length.

Worked Examples

Example 1

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

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

Balloon	arrow_pos	arrows
[1,6]	6	1
[2,8]	6	1 (covered)
[7,12]	12	2 (new arrow)
[10,16]	12	2 (covered)

Output: 2

Example 2

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

Sorted by end: [[1,2],[3,4],[5,6],[7,8]]

Each balloon does not overlap, so a new arrow is needed for each. Output: 4

Example 3

Input: [[1,2],[2,3],[3,4],[4,5]]

Sorted by end: [[1,2],[2,3],[3,4],[4,5]]

Arrows shot at 2 and 4. Output: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime; iteration is O(n)
Space	O(1)	In-place sorting; only a few variables used

The algorithm is efficient enough for n up to 10^5. Sorting ensures we only need one pass through the intervals to place arrows.

Test Cases

# Basic examples
assert Solution().findMinArrowShots([[10,16],[2,8],[1,6],[7,12]]) == 2  # overlapping intervals
assert Solution().findMinArrowShots([[1,2],[3,4],[5,6],[7,8]]) == 4  # non-overlapping intervals
assert Solution().findMinArrowShots([[1,2],[2,3],[3,4],[4,5]]) == 2  # sequential overlapping

# Edge cases
assert Solution().findMinArrowShots([]) == 0  # empty input
assert Solution().findMinArrowShots([[1,2]]) == 1  # single balloon
assert Solution().findMinArrowShots([[1,10],[2,9],[3,8],[4,7]]) == 1  # fully nested intervals

# Large intervals
assert Solution().findMinArrowShots([[1, 1000000000],[2,3],[4,5]]) == 2  # one big and two small

# Negative coordinates
assert Solution().findMinArrowShots([[-10,-1],[-5,0],[1,2]]) == 2

Test	Why
overlapping intervals	verifies greedy placement
non-overlapping intervals	checks separate arrow handling
sequential overlapping	ensures consecutive overlaps handled
empty input	checks edge case handling
single balloon	minimum case
fully nested intervals	tests greedy choice correctness
large intervals	checks correctness with wide ranges
negative coordinates	validates negative numbers

Edge Cases

One edge case is an empty input list. The implementation returns 0, avoiding unnecessary computation.

Another case is fully nested intervals where one arrow can cover multiple balloons. Sorting by end ensures the arrow is optimally placed at the smallest possible end, covering all nested balloons.

A third edge case involves balloons with large ranges or negative coordinates. Sorting still works correctly due to integer comparison, and no overflow occurs because Python handles arbitrary integers and Go uses 64-bit integers implicitly within constraints.

This solution is robust to a variety of input patterns, ensuring correctness and efficiency.