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.
ProblemStatement
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 x 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.
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 “Coding Ninjas Studio”, before moving on to the solution.
The steps of solving the problem are as follows:
Sort the points array in ascending order according to points[i][1], i.e., ending coordinate of the balloons.
Declare a variable: currentEnd. And initialize it with the end of the first balloon.
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.
Iterate over the points array.
Check if the i’th Balloon overlaps with the previous balloon by checking if points[i][0] <= currentEnd.
If it overlaps -
Then the i’th balloon can be burst by the same arrow.
If it does not overlap -
Increase the count by 1 as the previous arrow can not burst it.
For this new arrow, update the currentEnd as points[i][1].
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] = 11and 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] = 12and 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> usingnamespacestd; boolcompare(vector<int> &p1, vector<int> &p2) {
return p1[1] < p2[1]; } intminArrows(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; }
intmain() { vector<vector<int>> points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}}; 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
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.
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 Algorithmsto 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 outAlgorithms.
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series onCoding Ninjas Studionow!
38+ registered 