Minimum Number of Arrows to Burst Balloons solution and explanation
Google
9 more videos on this problem
Minimum Number of Arrows to Burst Balloons - Leetcode 452 - PythonNeetCodeIO · 12:26 · 32K views
Minimum Number of Arrows to Burst Balloons | Leetcode 452 | Google | codestorywithMIKcodestorywithMIK · 23:40 · 19K views
Minimum Number of Arrows to Burst Balloons 🔥| Leetcode 452 | Greedy | SortingAyushi Sharma · 11:05 · 9K views
452. Minimum Number of Arrows to Burst Balloons | Delete overlapping intervalsAryan Mittal · 15:53 · 4K views
Minimum Number of Arrows to Burst Balloons | LeetCode 452Programming Tutorials · 10:54 · 4K views
[Java] Leetcode 452. Minimum Number of Arrows to Burst Balloons [Greedy #2]Eric Programming · 9:24 · 1K views
Minimum Number of Arrows to Burst Balloons - LeetCode 452 - Python #leetcode #leetcode75 #greedyDeepti Talesra · 9:18 · 1K views
Minimum Number of Arrows to Burst Balloons leetcode 452 videoEasyLeetcode · 10:41 · 707 views
Minimum Number of Arrows to Burst Balloons - Intervals - Two Solutions - Python - Leetcode 452CheatCode Ninja · 8:02 · 599 views
LeetCode Problem 452: Minimum Number of Arrows to Burst BalloonsAlex does LeetCode · 2:04 · 453 views
The problem
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 - 1
Approach overview
Problem 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 1: Greedy Approach Using Sorting by End Points
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.
def find_min_arrows(points):
if not points:
return 0
points.sort(key=lambda x: x[1])
arrows = 1
end = points[0][1]
for x_start, x_end in points:
if x_start > end:
arrows += 1
end = x_end
return arrows
points = [[10, 16], [2, 8], [1, 6], [7, 12]]
print(find_min_arrows(points))import java.util.Arrays;
public class MinimumArrows {
public static int findMinArrows(int[][] points) {
if (points.length == 0) return 0;
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 1;
int end = points[0][1];
for (int[] point : points) {
if (point[0] > end) {
arrows++;
end = point[1];
}
}
return arrows;
}
public static void main(String[] args) {
int[][] points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
System.out.println(findMinArrows(points));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int findMinArrows(vector<vector<int>>& points) {
if (points.empty()) return 0;
sort(points.begin(), points.end(), [](vector<int>& a, vector<int>& b) {
return a[1] < b[1];
});
int arrows = 1;
int end = points[0][1];
for (const auto& p : points) {
if (p[0] > end) {
++arrows;
end = p[1];
}
}
return arrows;
}
int main() {
vector<vector<int>> points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
cout << findMinArrows(points) << endl;
return 0;
}function findMinArrows(points) {
if (points.length === 0) return 0;
points.sort((a, b) => a[1] - b[1]);
let arrows = 1;
let end = points[0][1];
for (let [start, endVal] of points) {
if (start > end) {
arrows++;
end = endVal;
}
}
return arrows;
}
const points = [[10, 16], [2, 8], [1, 6], [7, 12]];
console.log(findMinArrows(points));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return ((int*)a)[1] - ((int*)b)[1];
}
int findMinArrows(int** points, int pointsSize, int* pointsColSize){
if (pointsSize == 0) return 0;
qsort(points, pointsSize, sizeof(int*), compare);
int arrows = 1;
int end = points[0][1];
for (int i = 1; i < pointsSize; i++) {
if (points[i][0] > end) {
arrows++;
end = points[i][1];
}
}
return arrows;
}
int main() {
int pointsColSize[] = {2, 2, 2, 2};
int* points[] = {(int[]){10, 16}, (int[]){2, 8}, (int[]){1, 6}, (int[]){7, 12}};
int result = findMinArrows(points, 4, pointsColSize);
printf("%d\n", result);
return 0;
}using System;
public class MinimumArrows {
public static int FindMinArrows(int[][] points) {
if (points.Length == 0) return 0;
Array.Sort(points, (a, b) => a[1].CompareTo(b[1]));
int arrows = 1;
int end = points[0][1];
foreach (var point in points) {
if (point[0] > end) {
arrows++;
end = point[1];
}
}
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));
}
}In Python, this solution is implemented by sorting the input array using Python’s default sort function, sorted by the end of each interval.
The loop over sorted balloons checks whether each start point is greater than the ongoing `end`. If true, the 'end' is updated and another arrow is counted, indicating a new position for the next arrow shot after covering the current point.
Time Complexity: O(n log n), since Python's sort method is O(n log n).
Space Complexity: O(n) due to the sorting layer (additional memory overhead).
Approach 2: Interval Scheduling Maximization
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.
def find_min_arrows(points):
if not points:
return 0
points.sort()
arrows = 1
last_end = points[0][1]
for x_start, x_end in points:
if x_start <= last_end:
last_end = min(last_end, x_end)
else:
arrows += 1
last_end = x_end
return arrows
points = [[10, 16], [2, 8], [1, 6], [7, 12]]
print(find_min_arrows(points))import java.util.Arrays;
public class MinimumArrows {
public static int findMinArrows(int[][] points) {
if (points.length == 0) return 0;
Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
int arrows = 1;
int lastEnd = points[0][1];
for (int[] point : points) {
if (point[0] <= lastEnd) {
lastEnd = Math.min(lastEnd, point[1]);
} else {
arrows++;
lastEnd = point[1];
}
}
return arrows;
}
public static void main(String[] args) {
int[][] points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
System.out.println(findMinArrows(points));
}
}#include <iostream>
#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;
}function findMinArrows(points) {
if (points.length === 0) return 0;
points.sort((a, b) => a[0] - b[0]);
let arrows = 1;
let lastEnd = points[0][1];
for (let [start, endVal] of points) {
if (start <= lastEnd) {
lastEnd = Math.min(lastEnd, endVal);
} else {
arrows++;
lastEnd = endVal;
}
}
return arrows;
}
const points = [[10, 16], [2, 8], [1, 6], [7, 12]];
console.log(findMinArrows(points));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return ((int*)a)[0] - ((int*)b)[0];
}
int findMinArrows(int** points, int pointsSize, int* pointsColSize){
if (pointsSize == 0) return 0;
qsort(points, pointsSize, sizeof(int*), compare);
int arrows = 1;
int lastEnd = points[0][1];
for (int i = 1; i < pointsSize; i++) {
if (points[i][0] <= lastEnd) {
lastEnd = (lastEnd < points[i][1]) ? lastEnd : points[i][1];
} else {
arrows++;
lastEnd = points[i][1];
}
}
return arrows;
}
int main() {
int pointsColSize[] = {2, 2, 2, 2};
int* points[] = {(int[]){10, 16}, (int[]){2, 8}, (int[]){1, 6}, (int[]){7, 12}};
int result = findMinArrows(points, 4, pointsColSize);
printf("%d\n", result);
return 0;
}using System;
public class MinimumArrows {
public static int FindMinArrows(int[][] points) {
if (points.Length == 0) return 0;
Array.Sort(points, (a, b) => a[0].CompareTo(b[0]));
int arrows = 1;
int lastEnd = points[0][1];
foreach (var point in points) {
if (point[0] <= lastEnd) {
lastEnd = Math.Min(lastEnd, point[1]);
} else {
arrows++;
lastEnd = point[1];
}
}
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));
}
}Python’s list-method sort facilitates this solution style by initial ordering on start points establishing an easy visual series.
The greediest overlaps stored by the `last_end` facilitates arrow accounting and minimizes overlapping discernment errors.
Time Complexity: O(n log n) for using built-in sorting.
Space Complexity: O(n) from inbuilt sort entailing list copying.
Approach 3: Default Approach
function findMinArrowShots(points: number[][]): number {
points.sort((a, b) => a[1] - b[1]);
let ans = 0;
let last = -Infinity;
for (const [a, b] of points) {
if (last < a) {
ans++;
last = b;
}
}
return ans;
}func findMinArrowShots(points [][]int) (ans int) {
sort.Slice(points, func(i, j int) bool { return points[i][1] < points[j][1] })
last := -(1 << 60)
for _, p := range points {
a, b := p[0], p[1]
if a > last {
ans++
last = b
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach Using Sorting by End Points | Time Complexity: O(n log n), since Python's sort method is O(n log n). |
| Interval Scheduling Maximization | Time Complexity: O(n log n) for using built-in sorting. |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Number of Arrows to Burst Balloons easy or hard?
The problem is classified as Medium difficulty on LeetCode. The implementation is short, but recognizing the greedy insight of sorting by interval end points and placing arrows optimally requires familiarity with interval scheduling patterns.
Minimum Number of Arrows to Burst Balloons Python/Java solution
Implement the greedy approach by sorting the intervals by their end coordinate. Then iterate through the list while tracking the current arrow position and incrementing the arrow count whenever a new non-overlapping interval appears. This logic is identical across Python, Java, C++, and other languages.
How to solve Minimum Number of Arrows to Burst Balloons in O(n)?
Achieving strict O(n) time is not practical in the general case because the intervals need to be ordered by end position. The optimal strategy sorts intervals first, giving O(n log n) time. If the intervals were already sorted by end coordinate, the greedy scan would run in O(n).
What is the best approach for Minimum Number of Arrows to Burst Balloons?
The best approach is a greedy strategy that sorts balloons by their ending coordinate. Shoot an arrow at the end of the first interval and continue scanning. If the next balloon starts after the arrow position, fire a new arrow. This method runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Minimum Number of Arrows to Burst Balloons asked at Google/Amazon/Meta?
Interval greedy problems similar to this one frequently appear in interviews at companies like Amazon, Google, and Meta. The question tests understanding of interval scheduling, greedy choice properties, and sorting-based optimization patterns.
What data structure is used in Minimum Number of Arrows to Burst Balloons?
The problem primarily uses arrays to store intervals and relies on sorting and greedy traversal. No advanced data structures are required. The algorithm keeps track of the current arrow position while iterating through the sorted intervals.
What is the time complexity of Minimum Number of Arrows to Burst Balloons?
The optimal solution runs in O(n log n) time because the intervals must be sorted by their end coordinates. After sorting, a single linear scan determines how many arrows are required, which adds O(n). Space complexity is O(1) if sorting is done in-place.