Minimum Number of Arrows to Burst Balloons

Yukti Kumari
Last Updated: May 13, 2022

Introduction

In this article, we will solve the problem to find the Minimum Number of Arrows to Burst Balloons using a greedy algorithm followed by its implementation in C++ and analysis of the space and time complexity of the solution.

Let’s get started with the problem statement.

Problem Statement

There are some spherical balloons taped onto a flat wall that represents the XY plane. The balloons are represented as 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 if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps travelling 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 - 

Points array - [[1,3],[2,7],[2,9],[8,10],[9,12],[11,13],[12,15]]

Let’s try to visualize the balloons at the given coordinates - 

 

You can see that many balloons overlap.

What are we looking for?

  • We need to get the minimum number of arrows to burst all the balloons.
  • So, our goal is to burst as many balloons as possible with a single arrow.
  • Hence, the problem boils down to greedily finding the balloons such that they overlap.

Approach

In order to find the balloons that are overlapping, first, we will sort the points array according to the end coordinates.

Recommendation:  Please solve it on “CodeStudio”, before moving on to the solution.

The steps of solving the problem are as follows:

  1. Sort the points array in ascending order according to points[i][1], i.e., ending coordinate of the balloons.
  2. Declare a variable: currentEnd. And initialize it with the end of the first balloon.
  3. Declare a variable count to store the number of arrows we need to burst all balloons and initialize it with 1 since we need at least one arrow to burst the first balloon.
  4. Iterate over the points array. 
  5. Check if the i’th Balloon overlaps with the previous balloon by checking if points[i][0] <= currentEnd. 
    1. If it overlaps - 
      1. Then the i’th balloon can be burst by the same arrow.
  6. If it does not overlap - 
    1. Increase the count by 1 as the previous arrow can not burst it.
    2. For this new arrow, update the currentEnd as points[i][1].
  7. Finally, return the count. 

Dry Run

  • Points array initially - [[1,3],[9,12],[2,7],[2,9],[11,13],[8,10],[12,15]]

Array after sorting - [[1,3],[2,7],[2,9],[8,10],[9,12],[11,13],[12,15]]

  • At index=0, we have count=1 and currentEnd = 3.
  • At index=1, points[1][0] = 2 and currentEnd = 3. Since,points[1][0]<currentEnd, so it can be burst by the same arrow.
  • At index=2, points[2][0] = 2 and currentEnd = 3. Since,points[2][0]<currentEnd, so it can be burst by the same arrow.
  • At index=3, points[3][0] = 8 and currentEnd = 3. 

Since, points[3][0] currentEnd, so the same arrow can not burst it. Increase the count by 1 making count=1+1 =2, and update currentEnd points[3][1] = 10.

  • At index=4, points[4][0] = 9 and currentEnd = 10. 

Since, points[4][0] currentEnd, so the same arrow can burst it.

  • At index=5, points[5][0] = 11 and currentEnd = 10. 

Since, points[5][0] currentEnd, so it can not be burst by the same arrow. Increase count and update currentEnd making count=2+1=3 and currentEnd points[5][1] = 13.

  • At index=6, points[6][0] = 12 and currentEnd = 13. 

Since, points[6][0] currentEnd, so the same arrow can burst it.

  • We have reached the end of the points array. So, return the value of the minimum number of arrows which is count=3. 
    • The first arrow is shot at x=3.
    • Second Arrow is shot at x = 10.
    • Third Arrow is shot at x = 13.


Let’s see the code for the greedy approach discussed in the next section.

C++ Implementation

/*C++ code to find the Minimum Number of Arrows to Burst Balloons using greedy approach*/
#include <bits/stdc++.h>
using namespace std;
bool compare(vector<int> &p1, vector<int> &p2)
{

    return p1[1] < p2[1];
}
int minArrows(vector<vector<int>> &points)
{
    //sort the array according to ending coordinates
    sort(points.begin(), points.end(), compare);

    //end is the end of first balloon
    int end = points[0][1];

    // we need at least 1 arrow to burst the first balloon
    int ans = 1;

    //iterate over other balloons
    for (int i = 1; i < points.size(); i++)
    {
        if (points[i][0] <= end)
        {
            continue;
        }
        else
        {

            //else we know that the current balloon does not coincide with other balloons
            //so we set end to the current balloon and increase the ans by one
            end = points[i][1];
            ans++;
        }
    }
    return ans;
}

int main()
{
    vector<vector<int>> points = {{1016}, {28}, {16}, {712}};
    cout << "The Minimum Number of Arrows to Burst Balloons= " << minArrows(points) << endl;
}

 

 

Output

The Minimum Number of Arrows to Burst Balloons= 2

Time Complexity - O(NlogN)

The sorting of the points array takes O(NlogN) time, and iterating over the points array to find overlapping balloons takes linear time. Hence total time complexity is - O(NlogN) + O(n) which is ultimately O(NlogN).

Space Complexity - O(1)

We don't use any extra space, so it has constant space complexity.

Frequently Asked Questions

  1. What is a greedy algorithm?
    As the name suggests, the greedy algorithm selects the best available option at any moment. So, it obtains locally optimal solutions, which are not always globally optimal also.
     
  2. Where can I read more blogs on greedy algorithms?
    To read more blogs on greedy algorithms, visit here.

Key Takeaways

In this article, we saw the greedy approach of finding the Minimum Number of Arrows to Burst Balloons. There are many problems based on finding the overlapping intervals, which can be solved by greedy algorithms. 

Follow up questions that you can solve using the same technique - 

You must check out Greedy Algorithms to better understand when and how to use greedy algorithms. Also, it is always good to know more and more algorithms as it makes your problem-solving skills sharper. So, do check out Algorithms.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on CodeStudio now!
 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think