This blog will discuss the problem to find the minimum number of arrows needed to burst all balloons.

In this problem, we will be given a 2-dimensional array “balloons[][]” of size ‘N’. Each i^{th }element of the array represents a balloon from ‘balloons[i][0]’ to ‘balloons[i][1]’ on X-coordinate and Y-coordinate doesn’t matter here. We have to burst all the ‘N’ given balloons. To burst balloons, an arrow can be thrown from co-ordinate (x,0). It will go vertically upwards and burst all the balloons satisfying the condition:

balloons[i][0] <= x <= balloons[i][1]

We have to find the minimum number of arrows needed to burst all balloons given in the problem.

If we will throw an arrow from x = 6, it will burst two balloons having starting and ending x coordinates: {1, 6} and {3, 8} because 1 <= x <= 6 and 3 <= x <=8

Next, if we throw an arrow from x = 17, it will burst the remaining three balloons as for x = 17, we have:

11 <= x <= 17, 16 <= x <=21, and 7 <= x <= 19

So, the minimum number of arrows needed to burst all balloons will be 2.

Now that we understand the problem, let's discuss the approach to solve it in the next section.

This section will discuss the approach to find the minimum number of arrows needed to burst all balloons. The approach is based on the Greedy algorithm. We have to burst all the balloons by using a minimum number of arrows, so a simple way is to sort the balloons in the increasing order of their ending x coordinates and throw the first arrow from the ending x coordinate of the first balloon. Now, traverse the balloons from left to right and check if this balloon can be burst with the previous arrow or not. If it can be burst then move to the next balloon, else increase the number of arrows and change the position of the arrow to the ending x coordinate of this balloon.

Algorithm -

Step 1. Create a function"minRequiredArrows()" to find the minimum number of arrows needed to burst all balloons, which takes a 2-dimensional vector storing the starting and ending x-coordinate of balloons as input.

Step 2. Inside the function "minRequiredArrows()," first sort the ‘balloons’ vector in the increasing order of the ending x-coordinates of balloons.

Step 3. Then initialize two variables ‘numArrows’ and ‘arrowPosn’ to store the number of arrows needed and the current position of the arrow respectively.

Step 4. Initialize ‘numArrows = 1’ as at least one arrow will be required and ‘arrowPosn = ending x-coordinate of first balloon’ as we have to burst the first balloon and take the best coordinate greedily at each step.

Step 5. Now iterate through all the remaining balloons and check whether the current balloon can be burst with the current arrow position. If it can burst then move to the next balloon else, increase the number of arrows, and change the position of the arrow greedily with the ending x-coordinate of the current balloon.

Step 6. Finally, return the ‘numArrows’, which is the minimum number of arrows needed to burst all balloons

C++ code:

// C++ code to find the minimum number of arrows needed to burst all balloons
#include <bits/stdc++.h>
using namespace std;
bool comp(vector<int> a, vector<int> b)
{
return b[1] > a[1];
}
// Function to find the minimum number of arrows needed to burst all balloons
int minRequiredArrows(vector<vector<int>> balloons)
{
// Sort the vector of balloons in the increasing order of their end points
sort(balloons.begin(), balloons.end(), comp);
// Initialize number of arrows with 1
int numArrows = 1;
// Initialize the arrow position with the ending x-coordinate of first balloon
int arrowPosn = balloons[0][1];
// Iterate through all the balloons and burst them
for (int i = 1; i < balloons.size(); i++)
{
/*
If current position of arrow is greater than the starting x-coordinate of the balloon,
then the same arrow will burst this balloon, so do nothing and move to the next balloon.
Else increase the number of arrows and change the position of arrow to the ending
x-coordinate of the balloon
*/
if (arrowPosn >= balloons[i][0])
{
continue;
}
else
{
arrowPosn = balloons[i][1];
numArrows++;
}
}
// Return the total number of arrows needed to burst all the balloons
return numArrows;
}
// Main Function
int main()
{
// Number of balloons
int N = 5;
// Declare a vector of vector to store the starting and ending x-coordinate of the balloons
vector<vector<int>> balloons;
// Push the starting and ending x-coordinate of the balloons into the vector
balloons.push_back({1,6});
balloons.push_back({11,17});
balloons.push_back({16,21});
balloons.push_back({3,8});
balloons.push_back({7,19});
// Call the function to find the minimum number of arrows needed to burst all balloons
int minArrows = minRequiredArrows(balloons);
cout<<"The minimum number of arrows needed to burst all balloons are: "<<minArrows<<endl;
return 0;
}

Output:
The minimum number of arrows needed to burst all balloons are: 2

Algorithm Complexity:

Time Complexity: O(N log(N))

In the function "minRequiredArrows()" to find the minimum number of arrows needed to burst all balloons, first, the vector is sorted which takes O(N log(N)) time and then a ‘for loop’ is used to iterate through the vector which takes O(N) time. So, the overall time complexity is O(N log(N)), where 'N' is the total number of balloons.

Space Complexity: O(1)

In the function "minRequiredArrows()" to find the minimum number of arrows needed to burst all balloons, we have used constant space, So, the space complexity is O(1).

FAQs

What is a Greedy Algorithm? Greedy algorithm is a technique to solve the problem by breaking into smaller steps and choosing the best possible solution at each step.

2. In the above approach to solve the problem, why we are changing the arrow position to the ending x coordinate of the balloon on getting a balloon that can’t be burst with the previous array? We are greedily taking the best possible position for the arrow at each step. As we are moving from left to right, so, we are taking the rightmost position of the arrow that can burst the current balloon and can be helpful in bursting the next balloons also as we have to minimize the number of arrows needed.

This article discussed the problem "Find the minimum number of arrows needed to burst all balloons, " the solution approach to this problem, its C++ implementation, and its time and space complexity.

If you want to solve similar problems on data structures and algorithms for practice, you can visit Coding Ninjas Studio.

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.