# Minimum Number of Arrows to Burst Balloons

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

**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**:**

- 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 overlaps -
- 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].

- 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**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**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 = {{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 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!**

Comments

## No comments yet

## Be the first to share what you think