Faangprep Logo
Log inStart free
Browse curriculum

Min Arrows to Burst Balloons

Find the minimum number of arrows to burst overlapping balloons.

MediumSolve on LeetCode

Problem Understanding

You are given an array of balloons where points[i] = [start, end] represents a balloon. An arrow can be shot up vertically at any x. A balloon is popped if start <= x <= end. An arrow can pop infinite overlapping balloons. Find the minimum number of arrows needed to pop all balloons.

Example:

  • Input: [[10,16],[2,8],[1,6],[7,12]]
  • Output: 2
  • Explanation: Shoot one arrow at x=6 (bursts [2,8], [1,6]). Shoot another at x=11 (bursts [10,16], [7,12]).

Algorithm Strategy

This is a Greedy problem similar to Non-overlapping Intervals. We want to shoot an arrow that pops as many balloons as possible. The best spot is the end of the earliest finishing balloon because that maximizes the chance to catch subsequent balloons.

  1. Sort: Sort balloons by their end coordinate.
  2. Iterate:
    • Initialize arrows = 1. Set endPos to the end of the first balloon.
    • For each subsequent balloon: If its start is greater than endPos, it means the current arrow missed it. We must shoot a new arrow. Increment arrows and update endPos to this new balloon's end.
    • Else (overlap), the current arrow also pops this balloon. Do nothing.

Interactive Visualization

Visualize how sorting by end position allows a greedy arrow shot.

Dry Run

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

Step Balloon Current Arrow Pos Action
Init Sort - [[1,6], [2,8], [7,12], [10,16]]
1 [1,6] 6 First balloon. Arrow at 6. Count = 1.
2 [2,8] 6 2 <= 6. Popped!
3 [7,12] 6 7 > 6. Missed! New Arrow at 12. Count = 2.
4 [10,16] 12 10 <= 12. Popped!
Final - - Answer: 2

Edge Cases & Common Mistakes

  • Touch: [1,2], [2,3]. Arrow at 2 bursts both. start <= end condition holds.
  • Single Balloon: 1 Arrow.
  • Negative Coordinates: Logic remains same.

Solution

Greedy approach O(N log N).

Min Arrows to Burst Balloons Code
1var findMinArrowShots = function(points) {
2    if (!points.length) return 0;
3    points.sort((a, b) => a[1] - b[1]);
4    
5    let arrows = 1;
6    let end = points[0][1];
7    
8    for (let i = 1; i < points.length; i++) {
9        if (points[i][0] > end) {
10            arrows++;
11            end = points[i][1];
12        }
13    }
14    return arrows;
15};
Previous

Meeting Rooms II

The approach, step by step

  1. Sort by end

    Sort the balloons by their end coordinate.

  2. Shoot the first arrow

    Shoot at the first balloon’s end and count one arrow.

  3. Shoot only when missed

    For each later balloon, shoot a new arrow at its end only if it starts after the current arrow.

Frequently asked questions

Why shoot each arrow at a balloon’s end?

The balloon that ends first must be hit at or before its end. Shooting exactly at its end still bursts it and reaches as far right as possible, so it bursts every other balloon an earlier position would.

When is a new arrow needed?

After sorting by end, a balloon needs a new arrow only when it starts after the current arrow’s position. A balloon that starts exactly at the arrow is burst.

How is this related to Non-overlapping Intervals?

Both sort by end and sweep greedily. The arrow count equals the largest set of balloons in which no two share a point.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description