Coding interview problems › Intervals

📅 Intervals Medium

Minimum Number of Arrows to Burst Balloons

Minimum Arrows to Burst Balloons explained: sort by end and shoot at each group's earliest end, O(n log n) greedy in tested Python, pitfalls and a live visual.

Also searched as: minimum arrows to burst balloons greedy · minimum points to cover all intervals · interval point cover

📅

Try it live Free

Merge Intervals & Meeting Rooms

On the Merge Intervals timeline, look at where intervals overlap: one arrow can burst every balloon that shares a common point, so count how many such stabbing points you need.

Also useful: Sorting Race: Insertion vs Merge vs Quick

Open the playground →

The problem

Each balloon spans a horizontal range [start, end]. An arrow shot straight up at position x bursts every balloon with start <= x <= end. Return the fewest arrows needed to burst all balloons.

Input[[10, 16], [2, 8], [1, 6], [7, 12]]
Output2

Shoot at 6 and at 12.

Input[[1, 2], [2, 3], [3, 4], [4, 5]]
Output2

Touching balloons can share an arrow.

The key insight

Sort balloons by end. The balloon that ends first must be hit by some arrow, and shooting at its end is the best choice, because it is as far right as possible while still hitting it, so it also hits every balloon that has started by then. Skip every balloon that arrow covers and repeat.

Brute force first: Trying arrow positions at every interval endpoint and searching over combinations is exponential.

Step-by-step approach

  1. If there are no balloons, return 0.
  2. Sort balloons by end.
  3. Shoot the first arrow at the first balloon's end and count 1.
  4. For each next balloon, if its start is > the last arrow position, it is not burst: shoot a new arrow at its end and count it.
  5. Return the count.

Python solution

PYTHON 3tested
def find_min_arrow_shots(points):
    arrows, last = 0, float("-inf")
    for start, end in sorted(points, key=lambda p: p[1]):
        if start > last:          # not burst by the last arrow
            arrows += 1
            last = end            # shoot as far right as possible
    return arrows

Complexity

TimeO(n log n)
SpaceO(n)

Sorting by end is O(n log n); the greedy sweep is O(n).

Common mistakes

Frequently asked questions

What is the time and space complexity of Minimum Arrows to Burst Balloons?

O(n log n) time for sorting and O(n) space for the sorted copy; the sweep is linear.

Why shoot at the end of the earliest-ending balloon?

That balloon must be hit by an arrow somewhere in its range. Any point further left hits no extra balloons, because every other balloon ends no earlier, so its end covers at least as many balloons as any other choice.

How is this different from Non-overlapping Intervals?

The greedy is the same, but here balloons that touch at a point share an arrow, so the comparison uses start > last instead of start >= last. The answer equals the size of the largest set of pairwise disjoint balloons.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Intervals Merge Intervals & Meeting Rooms lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.