Leetcode - 452. Minimum Number of Arrows to Burst Balloons

Intuition

The problem requires us to find the minimum number of arrows needed to burst all balloons, given that each balloon is represented as an interval
[start,end].

approach is based on the idea of merging overlapping intervals:

1. If two balloons overlap, they can be burst with a single arrow.
2. If they don’t overlap, a new arrow is required.

To achieve this, you sort the intervals and then iterate through them while merging overlapping balloons.

Approach

Sort the Balloons by Start Position

First, sort the points array in ascending order of start values (a[0] - b[0]).
This ensures that we process balloons from left to right based on where they start.
Initialize a Merged Intervals List (output)

Start with the first balloon as the initial interval in output.
Iterate Through Sorted Balloons

For each balloon in sorted[i]:
Check for Overlap with the Last Balloon in output

• If sorted[i][0] <= output[output.length - 1][1], the balloons overlap.
• Merge them by updating the end of the last interval to Math.min(sorted[i][1], last[1]).
• If No Overlap, Add a New Interval
• If sorted[i][0] > last[1], the balloon doesn’t overlap, so we add a new interval to output. Return the Number of Arrows

The size of output represents the minimum number of arrows required, as each interval in output corresponds to one arrow shot.

Complexity

• Time complexity:𝑂(nlog𝑛)
• Space complexity:O(n)

Code

javascript []
/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function (points) {

    let sorted = points.sort((a, b) => a[0] - b[0]);
    let output = [sorted[0]];
    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i][0] <= output[output.length - 1][1]) { //overlapped
            output[output.length - 1][1] = Math.min(sorted[i][1], output[output.length - 1][1])
        } else {
            output.push(sorted[i]);
        }
    }
    return output.length;

};

Alternate Solution

/**
 * @param {number[][]} points
 * @return {number}
 */
var findMinArrowShots = function (points) {
    if (!points.length) return 0;

    // Sort balloons by their end position instead of start position
    let sorted = points.sort((a, b) => a[1] - b[1]);

    let arrows = 1;  // We need at least one arrow
    let prevEnd = sorted[0][1];  // Track the end of the last burst balloon group

    for (let i = 1; i < sorted.length; i++) {
        if (sorted[i][0] > prevEnd) {  // If there's no overlap, fire a new arrow
            arrows++;
            prevEnd = sorted[i][1];  // Update end to current balloon's end
        }
    }

    return arrows;
};