# Minimum Number of Arrows to Burst Balloons
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-arrows-to-burst-balloons
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Instacart](https://scaleengineer.com/companies/instacart)
---
## Problem
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 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 traveling 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 1:**

**Input:** points = [[10,16],[2,8],[1,6],[7,12]]
**Output:** 2
**Explanation:** The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

**Example 2:**

**Input:** points = [[1,2],[3,4],[5,6],[7,8]]
**Output:** 4
**Explanation:** One arrow needs to be shot for each balloon for a total of 4 arrows.

**Example 3:**

**Input:** points = [[1,2],[2,3],[3,4],[4,5]]
**Output:** 2
**Explanation:** The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

**Constraints:**

* `1 <= points.length <= 105`
* `points[i].length == 2`
* `-231 <= xstart < xend <= 231 - 1`

# Approaches
## Iterative Search and Removal
This approach simulates the process without any initial sorting. It repeatedly finds a group of balloons that can be burst with a single arrow, removes them, and increments the arrow count. This process continues until all balloons are burst. While straightforward, its performance is suboptimal because it may re-scan the list of balloons multiple times.
**Time:** O(N^2). In each iteration of the `while` loop, we find the minimum end point which takes `O(K)` time, where `K` is the number of remaining balloons. Then we iterate again to remove burst balloons, which also takes `O(K)`. In the worst case, we remove only one balloon per iteration, leading to `N` iterations. The total time would be roughly `N + (N-1) + ... + 1`, which is `O(N^2)`. · **Space:** O(N). We use a list to store the remaining balloons, which can be up to size `N`.
**Pros:** Conceptually simple to understand.; Does not require initial sorting of the entire array.
**Cons:** Inefficient due to repeated scanning of the balloon list.; Time complexity of `O(N^2)` is too slow for large inputs (`N` up to 10^5) and will likely result in a "Time Limit Exceeded" error.
### Explanation
The algorithm works as follows:
1. We start with a list of all balloons and an arrow count of zero.
2. As long as there are balloons left to be burst, we increment the arrow count.
3. In each step, we need to decide where to shoot an arrow. A good heuristic is to pick a balloon and shoot an arrow at its end point. Why the end point? It gives a good chance to hit other balloons that extend further to the right.
4. We pick the balloon with the smallest end point among the remaining ones. This is a greedy choice to deal with the most "urgent" balloon first.
5. After shooting an arrow at this position, we iterate through all remaining balloons and remove those that are burst by this arrow.
6. We repeat this process until no balloons are left.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }

        List<int[]> remainingBalloons = new ArrayList<>();
        for (int[] p : points) {
            remainingBalloons.add(p);
        }

        int arrows = 0;
        while (!remainingBalloons.isEmpty()) {
            arrows++;
            
            // Find the balloon with the minimum end point
            int minEnd = Integer.MAX_VALUE;
            for (int i = 0; i < remainingBalloons.size(); i++) {
                if (remainingBalloons.get(i)[1] < minEnd) {
                    minEnd = remainingBalloons.get(i)[1];
                }
            }
            
            int arrowPos = minEnd;
            
            // Remove all balloons burst by this arrow
            List<int[]> nextRemaining = new ArrayList<>();
            for (int[] balloon : remainingBalloons) {
                // If the balloon starts after the arrow position, it's not burst
                if (balloon[0] > arrowPos) {
                    nextRemaining.add(balloon);
                }
            }
            remainingBalloons = nextRemaining;
        }
        
        return arrows;
    }
}
```
### Algorithm
- Create a mutable list of balloons from the input array.
- Initialize `arrows = 0`.
- While the list of balloons is not empty:
    - Increment `arrows`.
    - Find the balloon in the list with the minimum end point. Let's say its end point is `arrowPos`.
    - Create a new list to store the balloons that are not burst by this arrow.
    - Iterate through the current list of balloons:
        - If a balloon's start point is greater than `arrowPos`, it's not burst. Add it to the new list.
    - Replace the old list with the new list of remaining balloons.
- Return `arrows`.

## Greedy Approach with Sorting
A much more efficient approach is to use a greedy algorithm. The core idea is to sort the balloons first, which allows us to make a locally optimal choice at each step that leads to a globally optimal solution. By sorting, we can process the balloons in a specific order and decide when to use a new arrow. Sorting by either the start or end points works, but sorting by the end points is often slightly more intuitive to implement.
**Time:** O(N log N). The dominant operation is sorting the `points` array, which takes `O(N log N)` time. The subsequent loop through the array takes `O(N)` time. · **Space:** O(log N) or O(N). This depends on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort which has `O(log N)` space complexity on average for the recursion stack. For objects (like `int[]`), it uses Timsort which has a space complexity of `O(N)` in the worst case.
**Pros:** Highly efficient and optimal solution.; The greedy choice is simple and easy to prove correct.; Passes for large constraints.
**Cons:** Requires modifying the input array by sorting, or using extra space to store a sorted copy.
### Explanation
The problem is to find the minimum number of arrows, which is equivalent to finding the minimum number of points that can hit all intervals. This is a classic interval problem that can be solved greedily.

Let's sort the balloons based on their end coordinates (`x_end`). Why? By sorting by end points, we encounter the balloons that "finish" earliest first. When we consider a balloon, we have to shoot an arrow to burst it. The best greedy choice is to shoot the arrow at its end point. This position is the rightmost possible point to burst the current balloon. Shooting it here maximizes the chance of also bursting other balloons that start before this point and extend beyond it.

**Example Walkthrough:** `points = [[10,16],[2,8],[1,6],[7,12]]`
1. Sort by end points: `[[1,6], [2,8], [7,12], [10,16]]`.
2. `arrows = 1`, `arrowPos = 6` (from `[1,6]`'s end).
3. Balloon `[2,8]`: `start = 2`. `2 <= 6`. It's burst. No change.
4. Balloon `[7,12]`: `start = 7`. `7 > 6`. Not burst.
   - `arrows` becomes 2.
   - `arrowPos` becomes `12` (from `[7,12]`'s end).
5. Balloon `[10,16]`: `start = 10`. `10 <= 12`. It's burst. No change.
6. End of array. Return `arrows = 2`.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) {
            return 0;
        }

        // Sort by end points. 
        // Note: Using Integer.compare to avoid potential overflow with subtraction
        // for large start/end values, as specified in the constraints.
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 1;
        int arrowPos = points[0][1];

        for (int i = 1; i < points.length; i++) {
            // If the current balloon's start is after the last arrow position
            if (points[i][0] > arrowPos) {
                // We need a new arrow
                arrows++;
                // Place the new arrow at the end of the current balloon
                arrowPos = points[i][1];
            }
        }

        return arrows;
    }
}
```
### Algorithm
- Handle the edge case: if the `points` array is empty, return 0.
- Sort the `points` array in ascending order based on the end coordinates (`points[i][1]`).
- Initialize `arrows = 1`, as we need at least one arrow for the first balloon.
- Initialize a variable, `arrowPos`, to the end coordinate of the first balloon (`points[0][1]`). This is where we shoot our first arrow.
- Iterate through the sorted array from the second balloon (`i = 1`).
- For each balloon, check if its start coordinate (`points[i][0]`) is greater than `arrowPos`.
   - If `points[i][0] > arrowPos`, it means the current balloon is not burst by the previous arrow. We need a new arrow.
   - Increment `arrows`.
   - Update `arrowPos` to the end coordinate of the current balloon (`points[i][1]`). This is the position for our new arrow.
   - If `points[i][0] <= arrowPos`, the current balloon is already burst by the arrow at `arrowPos`, so we can move on without doing anything.
- After the loop finishes, `arrows` will hold the minimum number of arrows required. Return `arrows`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int FindMinArrowShots(int[][] points) {
        Array.Sort(points, (a, b) => a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0);
        int ans = 0;
        long last = long.MinValue;
        foreach(var point in points) {
            if (point[0] > last) {
                ++ans;
                last = point[1];
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int findMinArrowShots(int[][] points) {
    Arrays.sort(points, Comparator.comparingInt(a->a[1]));
    int ans = 0;
    long last = -(1L << 60);
    for (var p : points) {
      int a = p[0], b = p[1];
      if (a > last) {
        ++ans;
        last = b;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int: ans, last = 0, - inf for a, b in sorted(points, key=lambda x: x[1]): if a > last: ans += 1 last = b return ans

```

### CPP

```cpp
class Solution {
public:
  int findMinArrowShots(vector<vector<int>> &points) {
    sort(points.begin(), points.end(),
         [](vector<int> &a, vector<int> &b) { return a[1] < b[1]; });
    int ans = 0;
    long long last = -(1LL << 60);
    for (auto &p : points) {
      int a = p[0], b = p[1];
      if (a > last) {
        ++ans;
        last = b;
      }
    }
    return ans;
  }
};

```