Minimum Number of Arrows to Burst Balloons

Medium
842.

Minimum Number of Arrows to Burst Balloons

Minimum Number of Arrows to Burst Balloons is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Flipkart interviews.

Balloon i spans the horizontal interval [x_start, x_end]. An arrow shot straight up at x bursts every balloon whose interval contains x, endpoints included, and travels infinitely upwards.

Return the minimum number of arrows needed to burst all the balloons.

Example 1

Input
points = [[10,16],[2,8],[1,6],[7,12]]
Output
2
Explanation
Shoot at x = 6 and x = 12.

Example 2

Input
points = [[1,2],[3,4],[5,6],[7,8]]
Output
4
Explanation
Nothing overlaps.

Example 3

Input
points = [[1,2],[2,3],[3,4],[4,5]]
Output
2
Explanation
Shoot at x = 2 and x = 4.

Constraints

  • 1 <= points.length <= 100000
  • points[i].length == 2
  • -1000000000 <= x_start <= x_end <= 1000000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function(points) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Arrows to Burst Balloons — Solution

Minimum Number of Arrows to Burst Balloons solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Arrows to Burst Balloons is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Flipkart interviews.

Problem statement

Balloon i spans the horizontal interval [x_start, x_end]. An arrow shot straight up at x bursts every balloon whose interval contains x, endpoints included, and travels infinitely upwards.

Return the minimum number of arrows needed to burst all the balloons.

Example 1

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: Shoot at x = 6 and x = 12.

Example 2

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: Nothing overlaps.

Example 3

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: Shoot at x = 2 and x = 4.

Constraints

  • 1 <= points.length <= 100000
  • points[i].length == 2
  • -1000000000 <= x_start <= x_end <= 1000000000

Hints for Minimum Number of Arrows to Burst Balloons

  1. Hint 1

    Sort the balloons by their right endpoint.

  2. Hint 2

    Always shoot at the right endpoint of the earliest-ending balloon still unburst.

  3. Hint 3

    Every balloon whose start is at most that position is burst by the same arrow.

How to solve Minimum Number of Arrows to Burst Balloons

The classic interval-stabbing greedy. Sorting by right endpoint and always shooting at the earliest end bursts as many balloons as any single arrow can, without ever forcing an extra arrow later.

Approach

  1. Sort by right endpoint ascending.
  2. Shoot at the first balloon's right endpoint and remember it as end.
  3. Scan on: a balloon starting at or before end is already burst; otherwise fire a new arrow at its right endpoint and update end.

Why it works

Exchange argument: in any optimal solution, the arrow that bursts the earliest-ending balloon can be moved to that balloon's right endpoint without losing any balloon it already hit — every balloon it hit starts at or before that point and ends at or after it. Repeating the argument turns any optimal solution into the greedy one, so the greedy is optimal.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Sorting by the left endpoint needs a different rule and is easy to get wrong.
  • Endpoints count as hits, so the test is start > end, strictly.
  • Subtracting coordinates in a comparator can overflow a 32-bit int; compare rather than subtract.

Reference solution

Python

from typing import List

def findMinArrowShots(points: List[List[int]]) -> int:
    p = sorted(points, key=lambda iv: iv[1])
    arrows, end = 1, p[0][1]
    for start, finish in p[1:]:
        if start > end:
            arrows += 1
            end = finish
    return arrows

Java

public static int findMinArrowShots(int[][] points) {
    int[][] p = points.clone();
    Arrays.sort(p, (a, b) -> Integer.compare(a[1], b[1]));
    int arrows = 1, end = p[0][1];
    for (int i = 1; i < p.length; i++) {
        if (p[i][0] > end) {
            arrows++;
            end = p[i][1];
        }
    }
    return arrows;
}

C++

int findMinArrowShots(vector<vector<int>>& points) {
    vector<vector<int>> p = points;
    sort(p.begin(), p.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });
    int arrows = 1, end = p[0][1];
    for (int i = 1; i < (int) p.size(); i++) {
        if (p[i][0] > end) {
            arrows++;
            end = p[i][1];
        }
    }
    return arrows;
}

JavaScript

var findMinArrowShots = function(points) {
    var p = points.slice().sort(function(a, b) {
        return a[1] < b[1] ? -1 : (a[1] > b[1] ? 1 : 0);
    });
    var arrows = 1, end = p[0][1];
    for (var i = 1; i < p.length; i++) {
        if (p[i][0] > end) { arrows++; end = p[i][1]; }
    }
    return arrows;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms