Compile Ready
Module 2 · Interval Greedy

Minimum Number of Arrows to Burst Balloons

MediumProblem 4 of 21 9 min read ~20 min to solve LeetCode
GreedyIntervalsSortingActivity Selection
Asked atAmazonGoogleMicrosoftAdobeUber

Problem Statement

There are balloons represented by horizontal intervals points[i] = [xStart, xEnd]. An arrow shot vertically at coordinate x bursts every balloon where xStart <= x <= xEnd. Return the minimum number of arrows needed to burst all balloons.

Input

An integer matrix points, where each row is the inclusive horizontal span of 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 **6** to burst **[1,6]** and **[2,8]**, and another at **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: Endpoint hits count. An arrow at **2** bursts the first two balloons, and an arrow at **4** bursts the last two.

Learning Objectives

  • Model one arrow as choosing a point shared by a group of overlapping intervals.
  • Apply the earliest-ending greedy rule to minimize selected points.
  • Use an exchange argument to justify shooting at the current smallest end.
  • Handle inclusive endpoints and large coordinate values safely.

Intuition

The greedy insight is to ask where the first arrow should go. If we sort balloons by right endpoint, the balloon that ends earliest must be burst soon. Shooting at its right endpoint is the safest possible choice: it bursts that balloon and remains as far right as possible, giving the same arrow the best chance to hit upcoming balloons.

The tempting wrong idea is to shoot near the start of an overlap or to sort by start and keep widening a group. That can waste reach. The earliest end is the deadline; placing the arrow exactly at that deadline satisfies the current balloon while preserving maximum compatibility with later balloons.

Common mistakes

  • ×Sorting by start and choosing arrows too early inside an overlap group.
  • ×Using **start >= arrowPosition** to start a new arrow; because endpoints are inclusive, only **start > arrowPosition** requires a new arrow.
  • ×Updating the arrow position when a balloon is already burst by the current arrow.
  • ×Subtracting coordinates in the comparator, which can overflow for 32-bit endpoint values.

Algorithm Explanation

Greedy strategy

Sort balloons by increasing end coordinate. Shoot the first arrow at the end of the earliest-ending balloon. Every later balloon whose start is at or before that arrow position is already burst. When a balloon starts after the arrow position, shoot a new arrow at that balloon's end.

Why it works

The earliest-ending unburst balloon imposes the tightest deadline on the next arrow. Any valid solution must place an arrow somewhere within that balloon. Choosing its end is never worse than choosing an earlier point, because the end is still inside the balloon and can only make the arrow more likely to hit future balloons that start later.

Proof of correctness

Consider an optimal solution for the sorted balloons. Look at the earliest-ending balloon not yet burst. The optimal solution must use some arrow position inside that balloon. Move that arrow to the balloon's end. This exchange still bursts the earliest-ending balloon. It also does not lose any previously considered balloon in the current group, because their starts are at or before this end and their ends are no smaller than the earliest end by sorting. Moving right to the earliest end can only help with future balloons. Therefore there is an optimal solution that shoots exactly where the greedy algorithm shoots. After removing every balloon burst by that arrow, the same argument applies to the remaining balloons. Thus the greedy arrow count is minimum.

Algorithm

  1. Sort points by end coordinate, using start as a tie-breaker.
  2. Shoot the first arrow at the end of the first balloon and set arrows = 1.
  3. Scan the remaining balloons in sorted order.
  4. If the balloon start is at or before arrowPosition, it is already burst.
  5. If the balloon start is greater than arrowPosition, shoot a new arrow at its end and increment arrows.
  6. Return arrows.

Solutions

Solution: Sort by end and place arrows at deadlines

Each arrow is placed at the right endpoint of the earliest-ending unburst balloon. That point is the latest safe position for the current balloon and maximizes the chance of covering later overlapping balloons.

Step-by-step

  1. Sort balloons by end coordinate using Integer.compare to avoid overflow.
  2. Place the first arrow at the first balloon end.
  3. For each next balloon, check whether its start is covered by the current arrow.
  4. If it is covered, do nothing because the same arrow bursts it.
  5. If it starts after the arrow, create a new arrow at this balloon's end.
Time

O(n log n)

Space

O(1)

Sorting dominates. The scan keeps only the current arrow position and count.

Java implementation

Loading…

Dry Run

Sample input

points = [[10,16],[2,8],[1,6],[7,12]]. Sort by balloon end, then track the current arrow position and arrow count.

stepballoon after end-sortcurrent arrow beforedecisioncurrent arrow afterarrows
1[1,6]noneShoot the first arrow at the earliest end 6.61
2[2,8]62 <= 6, so this balloon is burst by the same arrow.61
3[7,12]67 > 6, so shoot a new arrow at 12.122
4[10,16]1210 <= 12, so the second arrow also bursts this balloon.122

Two arrows are enough: one at 6 for the first overlap group and one at 12 for the second group.

Interview Tips

This problem is the point-cover version of interval scheduling. Say that the earliest end is a deadline, and shooting at that deadline is the exchange-safe choice. Be precise about inclusive endpoints: a balloon starting exactly at the arrow position is already burst, so a new arrow is needed only when start > arrowPosition.

Likely follow-ups

  • How would the solution change if arrow hits were not inclusive at endpoints?
  • How would you return the actual arrow positions?
  • What if each arrow had a limited vertical range and could not hit every balloon at that x-coordinate?
  • How would you handle balloons being added dynamically over time?

Similar Problems

Non-overlapping Intervals
MediumUses the same earliest-ending exchange argument.
Meeting Rooms II
MediumAnother interval sweep that counts resources needed for overlaps.
Maximum Events That Can Be Attended
MediumChooses the earliest ending available event to preserve future options.
Car Fleet
MediumGroups intervals of influence with a greedy sweep from one side.

Key Takeaways

  • One arrow is a point chosen inside as many overlapping intervals as possible.
  • The earliest-ending unburst balloon determines the next arrow position.
  • Shooting at that end is safe because it satisfies the current deadline and preserves future reach.
  • Inclusive endpoints mean **start == arrowPosition** is covered.
Reusable template: Sort intervals by end, choose a point at the earliest end, skip every interval containing that point, and repeat when the next interval starts after it.