Compile Ready
Module 4 · Greedy Interval Pattern

Minimum Number of Arrows to Burst Balloons

MediumProblem 7 of 12 9 min read ~25 min to solve LeetCode
IntervalsSortingGreedySweep Line
Asked atAmazonGoogleMicrosoftMetaBloomberg

Problem Statement

You are given an array points where points[i] = [xstart, xend] represents the horizontal diameter of one balloon. An arrow shot vertically at coordinate x bursts every balloon whose interval contains x. Return the minimum number of arrows needed to burst all balloons.

Input

An integer matrix points, where each row is the inclusive horizontal range [xstart, xend] covered by one balloon.

Output

An integer: the minimum number of vertical arrows required to burst every balloon.

Constraints

  • •1 <= points.length <= 10^5
  • •points[i].length == 2
  • •-2^31 <= xstart < xend <= 2^31 - 1

Examples

Example 1

Input: 
points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: Shoot one arrow at **x = 6** to burst **[1,6]** and **[2,8]**, then one arrow at **x = 12** to burst **[7,12]** and **[10,16]**.

Example 2

Input: 
points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: No two balloons overlap, so each balloon needs its own arrow.

Example 3

Input: 
points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The intervals touch at endpoints. One arrow at **x = 2** bursts the first two balloons, and one arrow at **x = 4** bursts the last two.

Learning Objectives

  • Recognise balloon bursting as choosing points that stab intervals.
  • Sort intervals by end coordinate to make the safest earliest arrow choice.
  • Prove why shooting at the first ending balloon does not lose optimality.
  • Use overflow-safe comparators when endpoints can be near integer limits.

Intuition

Pattern Recognition

The signal is minimum arrows, burst all balloons, and each balloon is an interval on the x-axis. This is not a merge problem; we do not need the union of ranges. We need the fewest points such that every interval contains at least one chosen point. That is the interval stabbing pattern.

The trap is sorting by start and committing too early. The interval that ends first creates the tightest deadline: if we do not shoot by its end, it can never be burst later. So we sort by end, shoot at that end, and let the same arrow cover every later balloon whose start is still at or before that coordinate.

Why greedy works / proof sketch

Look at the remaining balloon with the smallest end r. Any valid solution must place some arrow inside it, at a coordinate x <= r. If that arrow also bursts another remaining balloon, that other balloon has start <= x <= r and end >= r because r is the smallest end among remaining intervals. Therefore moving the arrow to exactly r still bursts every balloon the old arrow burst. There is an optimal solution whose first arrow is at r, so the greedy choice is safe. After removing all balloons hit by that arrow, the same argument applies to the suffix.

Common mistakes

  • ×Sorting by start time and shooting at the first start, which can choose an arrow too far left.
  • ×Using subtractive comparator arithmetic and overflowing on extreme endpoints.
  • ×Starting a new arrow when **start == arrowX**, even though endpoints are inclusive.
  • ×Updating the arrow position while processing an overlapping balloon; the arrow should stay at the earliest end already chosen.

Algorithm Explanation

Key idea

Sort balloons by their right endpoint. The first balloon in that order must be hit no later than its end, so shoot an arrow exactly there. Every following balloon with start <= arrowX is also burst by that arrow. The first balloon with start > arrowX cannot be hit by the current arrow, so it starts a new group and we shoot at its end. Use Integer.compare(a[1], b[1]) for the sort because coordinates can be near Integer.MAX_VALUE or Integer.MIN_VALUE.

Interval walkthrough

Use points = [[10,16],[2,8],[1,6],[7,12]]. Sorted by end, the number line order is [1,6], [2,8], [7,12], [10,16]. Draw the first two as overlapping over coordinate 6: 1 ---- 6 ---- 8. Shoot at 6, so both [1,6] and [2,8] disappear. The next start is 7, which is to the right of 6, so draw the next cluster 7 ---- 12 ---- 16. Shoot at 12, and both [7,12] and [10,16] are hit. Two clusters mean two arrows.

Algorithm

  1. Sort points by end coordinate ascending with Integer.compare.
  2. Initialise arrows = 1 and arrowX to the end of the first sorted balloon.
  3. Scan the remaining balloons in sorted order.
  4. If points[i][0] <= arrowX, the current arrow bursts this balloon, so skip it.
  5. If points[i][0] > arrowX, shoot a new arrow at points[i][1] and increment arrows.
  6. Return arrows after the scan.

Solutions

Solution: Sort by end and shoot greedily

When to prefer this:

Use this canonical solution whenever the problem asks for the fewest points, arrows, or markers needed to cover intervals.

Sort by each balloon end coordinate. The first ending balloon forces the next arrow position, and placing the arrow at that end keeps it as far right as possible while still hitting the forced balloon.

Step-by-step

  1. Sort points by end ascending using Integer.compare.
  2. Place the first arrow at the first sorted balloon end.
  3. For each next balloon, compare its start with the current arrow coordinate.
  4. If the start is less than or equal to the arrow coordinate, the balloon is already burst.
  5. Otherwise, count a new arrow and place it at this balloon end.
  6. Return the number of arrows placed.
Time

O(n log n)

Space

O(n)

Sorting dominates the scan. Java sorts object arrays with temporary storage; the greedy scan itself is O(1) extra space.

Java implementation

Loading…

Dry Run

Sample input

points = [[10,16],[2,8],[1,6],[7,12]]. After sorting by end: [[1,6],[2,8],[7,12],[10,16]].

sorted balloonarrow beforetestactionarrows
[1,6]nonefirst balloonshoot at 61
[2,8]62 <= 6same arrow bursts it1
[7,12]67 > 6shoot new arrow at 122
[10,16]1210 <= 12same arrow bursts it2

Every skipped balloon contains the current arrow coordinate. The scan creates exactly two non-overlapping arrow groups, so the answer is 2.

Interview Tips

State the greedy invariant clearly: arrowX is the end of the earliest-ending unburst balloon, and all skipped balloons contain that coordinate. Mention endpoint inclusivity, because start == arrowX is still a burst. Also call out the comparator: use Integer.compare(a[1], b[1]), never subtraction, because the problem allows extreme integer coordinates.

Likely follow-ups

  • How would you return the actual arrow coordinates instead of only the count?
  • What changes if balloon endpoints are open intervals instead of inclusive intervals?
  • How would you solve it if balloons arrived as a stream and you could not sort first?
  • How would the strategy change if each arrow had a width instead of being a single coordinate?

Similar Problems

Non-overlapping Intervals
MediumAlso sorts by end to make the interval that leaves the most room the keeper.
Remove Covered Intervals
MediumAnother greedy sweep where the sort key decides what can be safely discarded.
Merge Intervals
MediumUses overlap checks after sorting, but merges ranges instead of stabbing them with points.
Partition Labels
MediumA greedy range-closing problem where each chosen boundary is forced by the farthest requirement.

Key Takeaways

  • Minimum arrows is an interval stabbing problem, not a merge-output problem.
  • Sorting by end exposes the earliest deadline among remaining balloons.
  • Shooting at that end is safe by an exchange argument and maximises reuse of the arrow.
  • Inclusive endpoints mean **start <= arrowX** is covered by the current arrow.
Reusable template: Interval stabbing greedy: sort by end, choose the earliest finishing interval end as the next point, and skip every interval containing that point.