Leetcode 452 Minimum Number of Arrows to Burst Balloons

Leetcode 452 Minimum Number of Arrows to Burst Balloons

Minimum Number of Arrows to Burst Balloons – LeetCode

The key of solving this problem is to sort the array first in ascending order based on the end value of each element because we want to get the overlapping part of each balloon. By sorting it this way, we can easily compare the end of one balloon and the start of another one. The other reason we can sort first is the assumption on the arrow will be shot so that the order of the balloon does not matter.

Then what we need to do is to just loop through the array and compare each balloon’s start with the current left most right. If it’s larger, it means there’s no more overlap so we can safely increment the result by 1. Otherwise we keep moving on the next balloon in the array.

Solution

/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function(points) {
    points.sort((a,b) => a[1] - b[1]);
    let currentEnd = points[0][1]
    let result = 1;
    for(let i = 1; i < points.length; i++) {
        let start = points[i][0]
        if(start > currentEnd) {
            result++;
            currentEnd = points[i][1]
        }
    }

    return result;
};

Depending on your sorting algorithm, the time complexity may differ a little bit. This particular solution uses the built in javascript array sorting function and has a time complexity of O(nlogn). Space complexity is O(1) if you don’t count the result array, O(n) if counted.