Minimum Number of Arrows to Burst Balloons

Med

#0439Time: 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`.3 companies

Patterns

Greedy

Algorithms

Sorting

Data structures

Array

Companies

Flipkart Goldman Sachs Instacart

Prompt

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] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end. 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 x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end. 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 <= 10⁵
points[i].length == 2
-2³¹ <= x_start < x_end <= 2³¹ - 1

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

The algorithm works as follows:

We start with a list of all balloons and an arrow count of zero.
As long as there are balloons left to be burst, we increment the arrow count.
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.
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.
After shooting an arrow at this position, we iterate through all remaining balloons and remove those that are burst by this arrow.
We repeat this process until no balloons are left.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int findMinArrowShots(int[][] points) {6        if (points.length == 0) {7            return 0;8        }9 10        List<int[]> remainingBalloons = new ArrayList<>();11        for (int[] p : points) {12            remainingBalloons.add(p);13        }14 15        int arrows = 0;16        while (!remainingBalloons.isEmpty()) {17            arrows++;18            19            // Find the balloon with the minimum end point20            int minEnd = Integer.MAX_VALUE;21            for (int i = 0; i < remainingBalloons.size(); i++) {22                if (remainingBalloons.get(i)[1] < minEnd) {23                    minEnd = remainingBalloons.get(i)[1];24                }25            }26            27            int arrowPos = minEnd;28            29            // Remove all balloons burst by this arrow30            List<int[]> nextRemaining = new ArrayList<>();31            for (int[] balloon : remainingBalloons) {32                // If the balloon starts after the arrow position, it's not burst33                if (balloon[0] > arrowPos) {34                    nextRemaining.add(balloon);35                }36            }37            remainingBalloons = nextRemaining;38        }39        40        return arrows;41    }42}

Complexity

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

Trade-offs

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.

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.

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.

Walkthrough

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

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

1import java.util.Arrays;2import java.util.Comparator;3 4class Solution {5    public int findMinArrowShots(int[][] points) {6        if (points.length == 0) {7            return 0;8        }9 10        // Sort by end points. 11        // Note: Using Integer.compare to avoid potential overflow with subtraction12        // for large start/end values, as specified in the constraints.13        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));14 15        int arrows = 1;16        int arrowPos = points[0][1];17 18        for (int i = 1; i < points.length; i++) {19            // If the current balloon's start is after the last arrow position20            if (points[i][0] > arrowPos) {21                // We need a new arrow22                arrows++;23                // Place the new arrow at the end of the current balloon24                arrowPos = points[i][1];25            }26        }27 28        return arrows;29    }30}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1public class Solution {2    public int FindMinArrowShots(int[][] points) {3        Array.Sort(points, (a, b) => a[1] < b[1] ? -1 : a[1] > b[1] ? 1 : 0);4        int ans = 0;5        long last = long.MinValue;6        foreach(var point in points) {7            if (point[0] > last) {8                ++ans;9                last = point[1];10            }11        }12        return ans;13    }14}

1class Solution {2public3  int findMinArrowShots(int[][] points) {4    Arrays.sort(points, Comparator.comparingInt(a->a[1]));5    int ans = 0;6    long last = -(1L << 60);7    for (var p : points) {8      int a = p[0], b = p[1];9      if (a > last) {10        ++ans;11        last = b;12      }13    }14    return ans;15  }16}

1class Solution:2    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

1class Solution {2public:3  int findMinArrowShots(vector<vector<int>> &points) {4    sort(points.begin(), points.end(),5         [](vector<int> &a, vector<int> &b) { return a[1] < b[1]; });6    int ans = 0;7    long long last = -(1LL << 60);8    for (auto &p : points) {9      int a = p[0], b = p[1];10      if (a > last) {11        ++ans;12        last = b;13      }14    }15    return ans;16  }17};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem