Minimum Number Of Arrows To Burst Balloons - Leetcode Solution

Problem Statement:

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter, and hence the x-coordinates of start and end of the diameter suffice. The start is always smaller than the end.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps traveling up infinitely.

Given an array points where points[i] = [xstart, xend], return the minimum number of arrows that must be shot to burst all balloons.

Solution:

Let's begin with simple Greedy Algorithm - We can choose the balloon with the smallest end coordinate. In this way, we can always shoot one arrow to burst the balloons that have common end. We repeat this process until the no balloons left. In this way we will calculate minimum number of arrows to burst balloons. Let's implement this approach.

Algorithm:

1. Sort the balloons in ascending order based on the end coordinates.
2. Set the end of the first balloon to be the end of the previous balloon.
3. If the current balloon starts before the previous end, then it overlaps with the previous balloon and we don’t need to shoot another arrow for it. Update the end to be the minimum of the two ends.
4. If the current balloon starts after the previous balloon, then we need to shoot another arrow and update the end to be the end of the current balloon.
5. Return the number of arrows used.

Here is the implementation in Python:

def findMinArrowShots(points):
    if len(points) == 0:
        return 0

    # sort the balloons by end coordinate
    points.sort(key = lambda x: x[1])

    # initialize variables
    arrows = 1
    end = points[0][1]

    # iterate through the balloons
    for i in range(1, len(points)):
        # if it overlaps
        if points[i][0] <= end:
            end = min(end, points[i][1])
        else:
            # if it doesn't overlap
            arrows += 1
            end = points[i][1]

    return arrows

Time Complexity:

Sorting takes O(nlogn) and we iterate through the balloons once, therefore, the time complexity is O(nlogn).

Space Complexity:

We do not use any extra data structure, so the space complexity is O(1).

Note:

This approach is a greedy algorithm that finds the optimal solution at each step, so it is guaranteed to be the minimum.

This algorithm can be easily memorized as well.

1