Solving LeetCode Medium 452. Minimum Number of Arrows to Burst Balloons (JavaScript)

Let’s burst some bubbles bay-beees!

Let’s just jump right in and get to solving this medium difficulty LeetCode!

452. Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

1 <= points.length <= 105

points[i].length == 2

-231 <= xstart < xend <= 231 - 1

https://unsplash.com/photos/FU5uVjZSMMw

So we’re basically playing the balloon burst game at carnivals, but we’re throwing our dart or shooting our arrow along the vertical plane to get as many overlapping balloons in one shot as possible. We have unlimited arrows, but we don’t want to be wasteful, so we’re looking for the trajectories that will require the fewest arrows to be shot.

The first thing I want to do is go ahead and assign a variable to keep count of the number of arrows required, and since we know we need at least one arrow we can go ahead and assign it to one. Next, we want to sort our points array. I decided to sort by the endpoints.

Now that we’ve sorted our array of arrays it’s easier to see how we want to go about determining our overlaps, and therefore the number of arrows.

Visualization of start and endpoints of each balloon stacked vertically to see how to optimize our arrows.

So we’re all sorted by endpoints and have built out a visualization so we can see how to best compare balloon starts and ends to find our paths. So we’ll want to hold our current endpoint in a variable that we’ll reassign as we move through, then we’ll jump into our loop where we’ll compare our endPoint to our current start point or, points[i][0]. If endPoint is less than the start point then we’ll add one to our arrow count, and then we’ll reset our endpoint.

And that’s it. This one’s pretty fast, and once you visualize it, either in your head, or written out it’s pretty clear what you’re looking for to find your solution! Thanks for checking out my blog. Keep coming back for more fun with algorithms y’all!