Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogleFacebook

Minimum Number of Arrows to Burst Balloons

Choose your preparation mode4 modes available
📋
Problem

Imagine you have a set of balloons floating along a horizontal line, each balloon occupying a segment. You want to shoot arrows vertically to burst all balloons using as few arrows as possible.

You are given an array points where points[i] = [start_i, end_i] represents the horizontal diameter of a balloon. An arrow can be shot vertically along the x-axis at any point x, bursting all balloons whose diameters intersect x. Return the minimum number of arrows that must be shot to burst all balloons.

1 ≤ points.length ≤ 10^5-2^31 ≤ start_i < end_i ≤ 2^31 - 1
Edge cases: Only one balloon → 1 arrowAll balloons non-overlapping → number of balloons arrowsAll balloons fully overlapping → 1 arrow
</>
IDE
def findMinArrowShots(points: list[list[int]]) -> int:public int findMinArrowShots(int[][] points)int findMinArrowShots(vector<vector<int>>& points)function findMinArrowShots(points)
def findMinArrowShots(points):
    # Write your solution here
    pass
class Solution {
    public int findMinArrowShots(int[][] points) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int findMinArrowShots(vector<vector<int>>& points) {
    // Write your solution here
    return 0;
}
function findMinArrowShots(points) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: 1Sorting intervals by start coordinate instead of end coordinate causes undercounting arrows.✅ Sort intervals by their end coordinate before applying greedy selection.
Wrong: 3Treating touching intervals as overlapping reduces arrow count incorrectly.✅ Use strict inequality (start > last arrow position) to detect overlaps.
Wrong: 0Not handling empty input correctly, returning default zero or crashing.✅ Add explicit check for empty input and return 0 arrows.
Wrong: TLEUsing nested loops for overlap checking causes O(n^2) time complexity.✅ Implement sorting by end coordinate and greedy linear scan for O(n log n) time.
✓
Test Cases
t1_01basic
Input{"points":[[1,6],[2,8],[7,12],[10,16]]}
Expected2

Shoot one arrow at x = 6 to burst balloons [2,8] and [1,6], and another arrow at x = 11 to burst balloons [10,16] and [7,12].

t1_02basic
Input{"points":[[1,2],[3,4],[5,6],[7,8]]}
Expected4

All balloons are non-overlapping, so each requires a separate arrow.

t2_01edge
Input{"points":[]}
Expected0

No balloons means no arrows needed.

t2_02edge
Input{"points":[[5,10]]}
Expected1

Only one balloon requires exactly one arrow.

t2_03edge
Input{"points":[[1,5],[5,10],[10,15]]}
Expected2

Balloons touch at boundaries but do not overlap; each needs separate arrow.

t3_01corner
Input{"points":[[1,10],[2,3],[4,5],[6,7],[8,9]]}
Expected1

All smaller balloons are fully inside the first balloon, so one arrow at end=10 bursts all.

t3_02corner
Input{"points":[[1,2],[2,3],[3,4],[4,5]]}
Expected2

Balloons only touch at boundaries, no overlaps; each needs separate arrow.

t3_03corner
Input{"points":[[-10,-5],[-7,-3],[-6,-1],[-2,0]]}
Expected2

Handles negative coordinates correctly; arrows at -5 and 0 burst all balloons.

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this"}
⏱ Performance - must finish in 2000ms

n=100000, O(n log n) sorting and O(n) greedy must complete within 2 seconds.

Practice

(1/5)
1. Given the following code for inserting an interval, what is the final returned list after calling insert([[1,3],[6,9]], [2,5])?
from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    intervals.append(newInterval)
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])
    return merged
easy
A. [[1,5],[6,9]]
B. [[1,3],[2,5],[6,9]]
C. [[1,3],[6,9],[2,5]]
D. [[1,9]]

Solution

  1. Step 1: Append and sort intervals

    After appending [2,5], intervals become [[1,3],[6,9],[2,5]]. Sorting by start time yields [[1,3],[2,5],[6,9]].
  2. Step 2: Merge overlapping intervals

    Start with merged = [[1,3]]. The next interval [2,5] overlaps since 2 <= 3, so merge to [1,5]. Next interval [6,9] does not overlap, so append it.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Result matches expected merged intervals [OK]
Hint: Sort after insertion, then merge overlapping intervals [OK]
Common Mistakes:
  • Not sorting after insertion leads to wrong order
  • Failing to merge intervals that overlap at boundaries
  • Appending newInterval multiple times
2. Consider the following buggy code for inserting an interval. Which line contains the subtle bug that can cause incorrect output when the input list is empty?
from typing import List

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    intervals.append(newInterval)
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for i in range(1, len(intervals)):
        if intervals[i][0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
        else:
            merged.append(intervals[i])
    return merged
medium
A. Line 5: merged = [intervals[0]]
B. Line 3: intervals.append(newInterval)
C. Line 7: if intervals[i][0] <= merged[-1][1]:
D. Line 9: merged.append(intervals[i])

Solution

  1. Step 1: Consider empty intervals input

    If intervals is empty, after appending newInterval, intervals has length 1.
  2. Step 2: Check initialization of merged

    Line 5 accesses intervals[0] without checking if intervals is empty before append, which is safe here but if input was empty, intervals[0] is newInterval, so no crash.
  3. Step 3: Identify subtle bug

    Actually, no crash here, but if input intervals was empty, sorting and merging still works. The subtle bug is that if intervals was empty and newInterval is appended, the code works, but if the initial intervals list is empty and the code did not append newInterval first, line 5 would crash. So the bug is that the code assumes intervals is non-empty before append, which is not always true.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Accessing intervals[0] without empty check is risky [OK]
Hint: Accessing intervals[0] without empty check causes bug [OK]
Common Mistakes:
  • Not handling empty input intervals list
  • Assuming intervals always non-empty before append
  • Incorrect merging when intervals just touch
3. Examine the following buggy code for interval intersections:
def intervalIntersection(A, B):
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] <= B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result
What is the bug in this code?
medium
A. The condition 'if A[i][1] <= B[j][0]' should use '<' instead of '<=' to correctly detect touching intervals.
B. The pointer increments inside the else block are reversed; they should increment the pointer with the larger endpoint.
C. The overlap condition should check 'start < end' instead of 'start <= end' to avoid zero-length intervals.
D. The code does not handle empty input lists, which can cause runtime errors.

Solution

  1. Step 1: Analyze overlap condition

    Using '<=' excludes intervals that touch at a point (e.g., end == start), missing valid intersections.
  2. Step 2: Correct condition

    Changing to '<' ensures intervals that share a boundary point are considered intersecting.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Inclusive endpoints require '<' not '<=' to detect touching intervals [OK]
Hint: Check boundary conditions carefully for inclusive intervals [OK]
Common Mistakes:
  • Using <= instead of <
  • Reversing pointer increments
  • Ignoring empty inputs
4. The following code attempts to determine if a person can attend all meetings. Identify the line containing the subtle bug that causes incorrect results for intervals that just touch (e.g., [1,5] and [5,10]).
from typing import List

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])
    end = float('-inf')
    for interval in intervals:
        if interval[0] <= end:
            return False
        end = interval[1]
    return True
medium
A. Line 6: if interval[0] <= end:
B. Line 3: intervals.sort(key=lambda x: x[0])
C. Line 5: for interval in intervals:
D. Line 7: end = interval[1]

Solution

  1. Step 1: Understand the overlap condition

    Meetings that just touch (e.g., end=5 and start=5) should not be considered overlapping.
  2. Step 2: Identify the bug

    The condition uses <= which incorrectly treats touching intervals as overlapping. It should use < instead.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Changing <= to < fixes false positives on touching intervals [OK]
Hint: Overlap check must use <, not <= [OK]
Common Mistakes:
  • Using <= causes false overlap detection on touching intervals
5. Suppose the problem changes: intervals can be reused infinitely many times, and you want to count how many intervals contain each point considering unlimited reuse (e.g., intervals repeat periodically). Which modification to the line sweep approach correctly handles this scenario?
hard
A. No change needed; line sweep already counts intervals correctly regardless of reuse.
B. Preprocess intervals to merge overlapping intervals into one, then run line sweep once.
C. Use a segment tree or binary indexed tree to handle repeated intervals efficiently instead of line sweep.
D. Modify events to include multiple copies of intervals explicitly and run line sweep on expanded events.

Solution

  1. Step 1: Understand reuse impact

    Infinite reuse means intervals repeat periodically, so naive line sweep with explicit events cannot handle infinite copies.
  2. Step 2: Recognize data structure need

    Segment trees or binary indexed trees can efficiently query counts over ranges and handle repeated intervals without enumerating all copies.
  3. Step 3: Why other options fail

    No change (A) ignores infinite reuse; merging (B) loses count detail; explicit expansion (D) is infeasible for infinite repeats.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Segment trees handle range queries with repeated intervals efficiently [OK]
Hint: Infinite reuse requires data structures, not event enumeration [OK]
Common Mistakes:
  • Assuming line sweep handles infinite repeats
  • Trying to expand events explicitly
  • Merging intervals loses count accuracy
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard