Watch 10 video solutions for Minimum Number of Arrows to Burst Balloons, a medium level problem involving Array, Greedy, Sorting. This walkthrough by NeetCodeIO has 30,552 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105points[i].length == 2-231 <= xstart < xend <= 231 - 1Problem Overview: You are given a list of balloons where each balloon is represented as an interval [start, end] on the x-axis. One arrow shot at position x bursts every balloon whose interval contains x. The task is to compute the minimum number of arrows required to burst all balloons.
Approach 1: Greedy Approach Using Sorting by End Points (O(n log n) time, O(1) space)
This problem behaves like an interval covering problem. Sort the balloons by their end coordinate. Shoot the first arrow at the end of the first interval, then iterate through the sorted intervals. If the next balloon starts after the current arrow position, you need a new arrow and update the arrow position to the current balloon's end. Otherwise, the current arrow already bursts that balloon. The key insight: placing the arrow at the earliest possible end maximizes overlap with future balloons. This greedy strategy works because choosing the smallest end preserves the most room for upcoming intervals.
Sorting dominates the runtime at O(n log n), while the traversal is linear. The algorithm uses constant extra memory O(1) if sorting is done in-place. This approach directly leverages ideas from greedy algorithms, sorting, and interval processing on an array.
Approach 2: Interval Scheduling Maximization (O(n log n) time, O(1) space)
This perspective treats the problem as the classic interval scheduling variant. Instead of selecting the maximum number of non-overlapping intervals, you group overlapping intervals that can be covered by a single arrow. After sorting intervals by end coordinate, iterate through them and maintain the end of the current overlapping group. When a new interval starts beyond the current group end, the previous group requires one arrow and a new group begins. Conceptually, each arrow corresponds to one maximal set of overlapping intervals.
The mechanics are nearly identical to the greedy solution but framed through scheduling theory. Sorting costs O(n log n), and the single pass scan is O(n) with constant auxiliary memory O(1). This interpretation helps when connecting the problem to classic interval scheduling and greedy proofs.
Recommended for interviews: The greedy strategy that sorts intervals by end points is the expected solution. Interviewers look for the insight that placing the arrow at the earliest finishing balloon maximizes coverage of future balloons. Explaining the interval scheduling connection strengthens the reasoning. A brute-force overlap simulation shows understanding, but the O(n log n) greedy solution demonstrates strong algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Sorting by End Points | O(n log n) | O(1) | General case. Standard optimal solution used in interviews. |
| Interval Scheduling Maximization | O(n log n) | O(1) | When reasoning using classic interval scheduling theory. |