Course4all
Join us on telegram
Home/dsa/Greedy/Minimum Number of Arrows to Burst Balloons

Minimum Number of Arrows to Burst Balloons

Master this topic with zero to advance depth.

Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end. There is no limit to the number of arrows that can be shot.

Return the minimum number of arrows that must be shot to burst all balloons.

Visual Representation

Points: [[10,16], [2,8], [1,6], [7,12]] Sort by end points: [1, 6], [2, 8], [7, 12], [10, 16] Arrow 1: Shoot at x=6. Bursts [1,6] and [2,8]. Arrow 2: Shoot at x=12. Bursts [7,12] and [10,16]. Total: 2 arrows.
Medium

Examples

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

One arrow at 6 bursts [1,6] and [2,8]. Another arrow at 12 bursts [7,12] and [10,16].

Approach 1

Level I: Greedy Simulation (Brute Force)

Intuition

If we don't know the optimal sorting trick, a natural brute-force thought is: 'Let's find the coordinate that bursts the maximum number of balloons right now, shoot an arrow there, remove the burst balloons, and repeat until no balloons are left.' The candidate coordinates to shoot at are simply the start and end points of the remaining balloons.

Thought Process

  1. Maintain a list of remaining balloons.
  2. While the list is not empty, iterate through all start and end points of the remaining balloons.
  3. For each point, count how many balloons it intersects. Find the point that yields the maximum count.
  4. Increment arrows, filter out the burst balloons, and repeat.
⏱ O(N^3)💾 O(N)

Detailed Dry Run

points = [[1,6],[2,8],[7,12]]

  1. Points: 1,6,2,8,7,12. Count 6: bursts [1,6],[2,8] (2).
  2. Max burst is 2 at x=6. arrows=1. Remaining: [[7,12]]
  3. Repeat for [[7,12]]: best point 12. arrows=2. Empty.
java
import java.util.*;

public class Main {
    public static int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        List<int[]> remaining = new ArrayList<>(Arrays.asList(points));
        int arrows = 0;
        
        while (!remaining.isEmpty()) {
            long bestPoint = 0;
            int maxBurst = 0;
            
            for (int[] p : remaining) {
                long[] candidates = {p[0], p[1]};
                for (long cand : candidates) {
                    int count = 0;
                    for (int[] b : remaining) {
                        if (cand >= b[0] && cand <= b[1]) count++;
                    }
                    if (count > maxBurst) {
                        maxBurst = count;
                        bestPoint = cand;
                    }
                }
            }
            
            arrows++;
            List<int[]> nextRound = new ArrayList<>();
            for (int[] b : remaining) {
                if (bestPoint < b[0] || bestPoint > b[1]) {
                    nextRound.add(b);
                }
            }
            remaining = nextRound;
        }
        return arrows;
    }
}
Approach 2

Level II: Greedy (Sort by Start & Find Overlap)

Intuition

If we sort by start point, we can maintain a 'current intersection' range. Every new balloon must overlap with this intersection. If it doesn't, we shoot an arrow and start a new intersection range.

Thought Process

  1. Sort by start point.
  2. Pick the first balloon as the initial intersection [currentStart, currentEnd].
  3. For each subsequent balloon [bStart, bEnd]:
    • If bStart <= currentEnd (they overlap):
      • Narrow the intersection: currentEnd = min(currentEnd, bEnd).
    • Else (no overlap with current intersection):
      • Shoot an arrow!
      • Update currentEnd = bEnd and increment arrows.

Pattern: Intersection Tracking

⏱ O(N log N)💾 O(1)

Detailed Dry Run

pointsSorted = [[1,6],[2,8],[7,12]]

  1. p[0]=[1,6]. currEnd=6, arrows=1.
  2. p[1]=[2,8]. 2 <= 6 (overlap). currEnd = min(6, 8) = 6.
  3. p[2]=[7,12]. 7 > 6 (no overlap). arrows=2, currEnd=12.
java
import java.util.Arrays;

public class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        
        int arrows = 1;
        int currentEnd = points[0][1];
        
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] <= currentEnd) {
                currentEnd = Math.min(currentEnd, points[i][1]);
            } else {
                arrows++;
                currentEnd = points[i][1];
            }
        }
        return arrows;
    }
}
Approach 3

Level III: Optimal Greedy (Sort by End)

Intuition

To minimize arrows, we want each arrow to burst as many balloons as possible. By sorting by the end point, we fix the rightmost boundary for an arrow. If a balloon's start point is within the current arrow's range (i.e., start <= current_arrow_pos), it is burst. Otherwise, we need a new arrow at the new balloon's end point.

Why Sort by End?

Sorting by the end point ensures that the current balloon we are considering is the one that 'expires' soonest. Putting an arrow at its end point is the best greedy choice because it covers this balloon AND has the maximum chance of covering future balloons that start before this end point.

Pattern: Interval Overlap

⏱ O(N log N) due to sorting.💾 O(log N) or O(N) depending on the sorting implementation's recursion stack.

Detailed Dry Run

points = [[10,16], [2,8], [1,6], [7,12]] After Sort: [[1,6], [2,8], [7,12], [10,16]]

StepBalloonRangelastArrowAtarrowsAction
1[1, 6][1, 6]61Shoot at 6 (end of first)
2[2, 8][2, 8]612 <= 6? YES (Burst!)
3[7, 12][7, 12]1227 > 6? YES. Shoot at 12 (end)
4[10, 16][10, 16]12210 <= 12? YES (Burst!)

Visualization:

(1)-------(6) <- Arrow 1 at 6 (2)-----------(8) (7)-------(12) <- Arrow 2 at 12 (10)--------(16)
java
import java.util.Arrays;

public class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        
        // Sort by end points to greedily pick the best shooting position
        // Using Integer.compare to avoid overflow during subtraction
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 1;
        int currentEnd = points[0][1];

        for (int i = 1; i < points.length; i++) {
            // If current balloon starts AFTER our last arrow,
            // we MUST shoot a new arrow.
            if (points[i][0] > currentEnd) {
                arrows++;
                currentEnd = points[i][1];
            }
        }
        return arrows;
    }
}
← Previous QuestionPartition Labels
Next Question →Non-overlapping Intervals