Minimum Number of Arrows to Burst Balloons

Leetcode Problem 452: Minimum Number of Arrows to Burst Balloons

Problem Summary

Balloons are hung on a wall at various horizontal positions, represented as points[i] = [xStart, xEnd] denoting the horizontal range each balloon spans. An arrow shot vertically at x-coordinate x will burst all balloons where xStart <= x <= xEnd. Find the minimum number of arrows needed to burst all balloons.

Key Insight: An arrow shot at a single x-coordinate can burst multiple balloons that overlap at that point. This is an interval overlap problem where you must find the minimum number of points to cover all intervals.

Visual Example:

Balloons on x-axis:

x:    1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16

      |--[1,6]----|                    (balloon 1)
          |--[2,8]--|                  (balloon 2)
                  |--[7,12]--|          (balloon 3)
                              |--[10,16]--|  (balloon 4)

Optimal arrow shots:
      |--[1,6]----|        Arrow at x=6 bursts balloons 1,2
          (burst)
                  |--[7,12]--|        Arrow at x=11 bursts balloons 3,4
                  (burst)

Minimum arrows needed: 2

Constraints:

• Array contains between 1 and 100,000 balloons
• Each balloon is defined by 2 x-coordinates: [xStart, xEnd], where xStart < xEnd
• X-coordinate values are 32-bit signed integers (ranging from highly negative to highly positive values)
• You must burst every single balloon

Techniques

• Array
• Greedy
• Sorting

Solution

function findMinArrowShots(points: number[][]): number {
    points.sort((a, b) => a[0] - b[0])

    let arrows = 1
    let currentEnd = points[0][1]

    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > currentEnd) {
            arrows++
            currentEnd = points[i][1]
        } else {
            currentEnd = Math.min(points[i][1], currentEnd)
        }
    }

    return arrows
};

console.log(findMinArrowShots([[10,16],[2,8],[1,6],[7,12]])) // 2
console.log(findMinArrowShots([[1,2],[3,4],[5,6],[7,8]])) // 4
console.log(findMinArrowShots([[1,2],[2,3],[3,4],[4,5]])) // 2