1.
Introduction-
2.
Solution Approach
3.
Algorithm -
4.
C++ code:
5.
Algorithm Complexity:
5.1.
Time Complexity: O(N log(N))
5.2.
Space Complexity: O(1)
6.
FAQs
7.
Key takeaways-
Last Updated: Mar 27, 2024

# Find Minimum Number of Arrows Needed to Burst all Balloons

Riya

## Introduction-

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 ith 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.

Let's understand the problem with an example:

Suppose, the total number of balloons is 5

i.e. N = 5

and the x coordinates of balloons are given by:

balloons[][] = { {1, 6}, {11, 17}, {16, 21}, {3, 8}, {7, 19} }

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.

Also see, Euclid GCD Algorithm

## Solution Approach

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

## 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

1. 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.

Also Read - Strong number in c

## Key takeaways-

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.

Live masterclass