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 - 1The key idea behind solving #452 Minimum Number of Arrows to Burst Balloons is recognizing that overlapping balloon intervals can be burst using a single arrow. Each balloon is represented as an interval [start, end], and an arrow shot at position x will burst all balloons whose intervals contain x. This naturally leads to a greedy strategy.
A common approach is to first sort the intervals based on their ending coordinates. By doing this, you can place an arrow at the end of the first balloon and burst as many overlapping balloons as possible. As you iterate through the sorted intervals, you check whether the current balloon overlaps with the last arrow position. If it does not, a new arrow is required.
This greedy choice works because selecting the earliest possible ending position maximizes the chance of covering future intervals. The sorting step dominates the runtime, resulting in an efficient solution suitable for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Sorting (sort by end of intervals) | O(n log n) | O(1) or O(log n) depending on sorting implementation |
NeetCodeIO
This approach involves sorting the balloons by their end points. Once sorted, we shoot an arrow at the end point of the first balloon, and then continue moving through the list, checking if subsequent balloons overlap with the burst of the arrow. If a balloon does not overlap, we need an additional arrow for it.
Time Complexity: O(n log n) due to the sorting step, where n is the number of balloons.
Space Complexity: O(1) if we ignore the space used for sorting.
1using System;
2
3public class MinimumArrows {
4 public static int FindMinArrows(int[][] points) {
5 if (points.Length == 0) return 0;
6 Array.Sort(points, (a, b) => a[1].CompareTo(b[1]));
7 int arrows = 1;
8 int end = points[0][1];
9 foreach (var point in points) {
10 if (point[0] > end) {
11 arrows++;
12 end = point[1];
13 }
14 }
return arrows;
}
public static void Main() {
int[][] points = new int[][] { new int[] {10, 16}, new int[] {2, 8}, new int[] {1, 6}, new int[] {7, 12} };
Console.WriteLine(FindMinArrows(points));
}
}C# implementation uses the Array.Sort method with comparison on the end coordinates of the balloons to arrange them optimally for scanning.
Using a foreach loop, we check whether the start of the current balloon exceeds the last arrow's end location — prompting a new arrow.
This approach is adapted from the interval scheduling maximization pattern, where we attempt to find the maximum number of non-overlapping intervals. By sorting the intervals, we can focus on selecting the maximum number of compatible balloons.
Time Complexity: O(n log n) resulting from sorting operations.
Space Complexity: O(1) when sorting space considerations are minimized.
1#include <vector>
#include <algorithm>
using namespace std;
int findMinArrows(vector<vector<int>>& points) {
if (points.empty()) return 0;
sort(points.begin(), points.end());
int arrows = 1;
int lastEnd = points[0][1];
for (const auto& p : points) {
if (p[0] <= lastEnd) {
lastEnd = min(lastEnd, p[1]);
} else {
++arrows;
lastEnd = p[1];
}
}
return arrows;
}
int main() {
vector<vector<int>> points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
cout << findMinArrows(points) << endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, interval-based greedy problems like this are commonly asked in coding interviews at top tech companies. They test a candidate's understanding of sorting, interval overlap, and greedy decision-making.
The problem mainly relies on arrays to store intervals and sorting algorithms to order them. No complex data structures are required beyond simple iteration and comparison of interval boundaries.
The optimal approach uses a greedy strategy combined with sorting. By sorting balloon intervals based on their end coordinates, you can place arrows at strategic points that burst the maximum number of overlapping balloons.
Sorting helps process balloon intervals in a structured order so you can always choose the earliest ending balloon first. This greedy choice ensures that one arrow can cover as many overlapping intervals as possible.
In C++, sorting based first on starting x coordinates allows us to focus on creating the longest overlapping intervals so we manage arrows efficiently by bandwidth.
The for loop extends using the minimized overlapping principle until the final interval and consequently allows for calculated arrow number.