Minimum Number of Arrows to Burst Balloons

Medium Intervals Basics Original on LeetCode

Reported atBarclaysPhonePe

Minimum Number of Arrows to Burst Balloons is a medium intervals problem solved with the basics pattern. The best approach, optimal (sort by end, one sweep), runs in O(n log n) time and O(log n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from greedy with explicit marking up.

Problem

Balloons are stuck to a flat wall. Each balloon is described by points[i] = [start, end], the horizontal range it covers; heights do not matter.

An arrow shot straight up from position x bursts every balloon with start <= x <= end, and keeps flying after hitting one. Return the minimum number of arrows needed to burst all the balloons.

Examples

Example 1

Input
points = [[3, 9], [1, 4], [7, 12], [10, 15]]
Output
2
Why
An arrow at x = 4 bursts [3, 9] and [1, 4]; an arrow at x = 12 bursts [7, 12] and [10, 15].

Example 2

Input
points = [[1, 2], [4, 5], [7, 8]]
Output
3
Why
No two balloons share a point, so each needs its own arrow.

Example 3

Input
points = [[2, 6], [6, 9], [0, 2]]
Output
2
Why
Touching ends count: x = 2 hits [2, 6] and [0, 2], and x = 6 or 9 takes the last one.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Greedy with explicit markingO(n²)O(n)
Optimal (sort by end, one sweep)O(n log n)O(log n)

1Greedy with explicit marking

TimeO(n²)Each arrow triggers a full scan of all n balloons, and there can be up to n arrows.
SpaceO(n)A burst flag per balloon.

Sort by end point. Take the first balloon that is still intact, shoot at its end, and scan all balloons to mark every one that contains that x as burst. Repeat until all are burst.

  1. Sort balloons by end point.
  2. For each balloon in order that is not burst yet: arrows++, x = its end.
  3. Scan every balloon and mark it burst if start <= x <= end.
class Solution {
    public int findMinArrowShots(int[][] points) {
        int n = points.length;
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        boolean[] burst = new boolean[n];
        int arrows = 0;
        for (int i = 0; i < n; i++) {
            if (burst[i]) continue;
            arrows++;
            long x = points[i][1];
            for (int j = 0; j < n; j++)
                if (!burst[j] && points[j][0] <= x && x <= points[j][1]) burst[j] = true;
        }
        return arrows;
    }
}

2Optimal (sort by end, one sweep)

TimeO(n log n)The sort dominates; the sweep is linear.
SpaceO(log n)Only the sort's stack; two variables for the sweep.

After sorting by end point, keep the position of the last arrow. A balloon that starts at or before that position is already burst; one that starts after it needs a new arrow, placed at its own end.

  1. Sort by end point (compare with Integer.compare, not subtraction).
  2. arrows = 1, pos = end of the first balloon.
  3. For each next balloon: if start > pos, arrows++ and pos = its end.
class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        int arrows = 1;
        int pos = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > pos) {
                arrows++;
                pos = points[i][1];
            }
        }
        return arrows;
    }
}

Edge cases to test

  • A single balloon: one arrow
  • Balloons that only touch at an endpoint share an arrow
  • One wide balloon containing many narrow disjoint ones
  • Coordinates at the 32-bit limits (subtraction-based comparators overflow)

Hints

Hint 1

Some arrow must hit the balloon that ends first. Where along that balloon is the best place to shoot it?

Hint 2

Shooting at the smallest end point bursts every balloon that starts at or before it, and loses nothing.

Hint 3

Sort by end point and sweep: start a new arrow only when a balloon starts after the current arrow's position.

FAQ

What is the best time complexity for Minimum Number of Arrows to Burst Balloons?

Optimal (sort by end, one sweep) runs in O(n log n) time and O(log n) extra space. The sort dominates; the sweep is linear.

Which pattern does Minimum Number of Arrows to Burst Balloons use?

It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.

Is there a brute force solution for Minimum Number of Arrows to Burst Balloons?

Yes. Greedy with explicit marking takes O(n²) time and O(n) space. Sort by end point.

Which edge cases should I test for Minimum Number of Arrows to Burst Balloons?

A single balloon: one arrow; Balloons that only touch at an endpoint share an arrow; One wide balloon containing many narrow disjoint ones; Coordinates at the 32-bit limits (subtraction-based comparators overflow).