Leetcode 150 - Minimum Number of Arrows to Burst Balloons
Here is two solution for problem “Minimum Number of Arrows to Burst Balloons”
1. Input, Output, Contrains
- Input
-
points: list of N intervals, where each interval is [start, end] and 1 ≤ start ≤ end ≤ 10^9 (general case).
-
Example: points = [[2,6],[1,3],[7,10],[2,4]]
- Output
- Integer: minimum number of arrows required so that each interval contains at least one arrow (an arrow shot at x bursts every interval that satisfies start ≤ x ≤ end).
- Constraints
-
General constraints for the typical problem: 1 ≤ N ≤ 10^5 (or larger depending on problem source)
-
Special-case constraint for the O(N) solution below: [1, 1024].
2. Dry run ideas
2.1. Solution O(NlogN)
input = [2,4], [1,6], [2,8], [10,11], [7,12]
- Step 1: Fire in 4
[2,4] ✅
Any later interval whose range includes 4.
Check next intervals:
- Step 2: Find in 11
2.2. Solution O(N) - Counting Sort
end Bucket contents
4 [(2,4)]
6 [(1,6)]
8 [(2,8)]
11 [(10,11)]
12 [(7,12)]
others []
arrows = 0
arrow_pos = None
🧮 end = 4 → bucket = [(2,4)]
Current arrow_pos: None
Interval: [2,4]
Since arrow_pos is None, we need a new arrow → shoot at e = 4
arrows = 1
arrow_pos = 4
Now, any interval containing x = 4 is burst.
🧮 end = 6 → bucket = [(1,6)]
Current arrow_pos = 4
Interval [1,6] → check if already covered:
s ≤ arrow_pos ≤ e → 1 ≤ 4 ≤ 6 ✅
→ Already burst → skip
🧮 end = 8 → bucket = [(2,8)]
arrow_pos = 4
s ≤ arrow_pos ≤ e → 2 ≤ 4 ≤ 8 ✅
→ Already burst → skip
🧮 end = 11 → bucket = [(10,11)]
arrow_pos = 4
s ≤ arrow_pos ≤ e → 10 ≤ 4 ≤ 11 ❌
→ Not covered → new arrow needed.
Shoot arrow at e = 11
arrows = 2
arrow_pos = 11
🧮 end = 12 → bucket = [(7,12)]
arrow_pos = 11
s ≤ arrow_pos ≤ e → 7 ≤ 11 ≤ 12 ✅
→ Already burst → skip
🧮 end = 13 → 1024 → all empty → skip
3. Solution O(NlogN)
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
# sort by interval end
points.sort(key=lambda x: x[1])
arrows = 1
arrow_pos = points[0][1] # shoot at end of first interval
for s, e in points[1:]:
if s <= arrow_pos <= e:
continue
# need another arrow at this interval's end
arrows += 1
arrow_pos = e
return arrows
4. Solution O(N + 1024) in range [1,1024]
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
R = 1024
if not points:
return 0
ends_buckets = [[] for _ in range(R + 1)]
for s, e in points:
ends_buckets[e].append((s, e))
arrows = 0
current_arrow_pos = None
for end in range(1, R + 1):
for s, e in ends_buckets[end]:
if current_arrow_pos is None or s > current_arrow_pos:
arrows += 1
current_arrow_pos = e
return arrows
5. Merge Interval Greedy O(N + 1024)
def merge_intervals_small_range(intervals, R=1024):
covered = [0] * (R + 2) # +2 for boundary safety
# Mark coverage
for s, e in intervals:
covered[s] += 1
covered[e + 1] -= 1 # difference array trick
# Compute prefix sum to know covered regions
for i in range(1, R + 2):
covered[i] += covered[i - 1]
merged = []
in_interval = False
start = -1
# Sweep line
for i in range(1, R + 2):
if not in_interval and covered[i] > 0:
# start of new interval
start = i
in_interval = True
elif in_interval and covered[i] == 0:
# end of interval
merged.append([start, i - 1])
in_interval = False
return merged
i coverage[i] state
1 0 outside
2 1 inside (start new [2, …])
3 2 still inside
4 2 still inside
5 1 still inside
6 1 still inside
7 0 end interval → [2,6]
8 1 start new [8,…]
9 2 still inside
10 2 still inside
11 1 still inside
12 1 still inside
13 0 end interval → [8,12]
Last Updated On October 14, 2025