Minimum Arrows to Burst Balloons Greedy DSA Solution - Study Chapter | QuizMaker

Minimum Arrows to Burst Balloons explained with endpoint brute force, optimized interval-end greedy, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 13: Greedy Algorithms

Learning Outcome

After this lesson, you should be able to group overlapping intervals by shooting at the earliest possible end.

Problem Statement

Given balloon intervals, return the minimum number of arrows needed to burst all balloons.

Input	Output	Why
`points = [[10,16],[2,8],[1,6],[7,12]]`	`2`	One arrow can burst [1,6] and [2,8], and another can burst [7,12] and [10,16].

Brute Force Approach

Try many possible arrow positions and test which balloons they burst. This is unnecessary.

Optimized Approach

Sort by end. Shoot an arrow at the current earliest end, and start a new arrow only when the next interval starts after that end.

Exact Pseudocode

sort points by end
arrows = 0
arrowEnd = -infinity
for point in points:
  if point.start > arrowEnd:
    arrows += 1
    arrowEnd = point.end
return arrows

Reference Code

class Solution:
    def findMinArrowShots(self, points):
        points.sort(key=lambda x: x[1])
        arrows = 0
        arrow_end = float("-inf")

        for start, end in points:
            if start > arrow_end:
                arrows += 1
                arrow_end = end

        return arrows

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });

        int arrows = 0;
        long long arrowEnd = LLONG_MIN;
        for (auto& point : points) {
            if (point[0] > arrowEnd) {
                arrows++;
                arrowEnd = point[1];
            }
        }

        return arrows;
    }
};

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

        int arrows = 0;
        long arrowEnd = Long.MIN_VALUE;
        for (int[] point : points) {
            if (point[0] > arrowEnd) {
                arrows++;
                arrowEnd = point[1];
            }
        }

        return arrows;
    }
}

Sample Dry Run

Step	State	Result
Sort by end	[1,6], [2,8], [7,12], [10,16]	Earliest end first
First arrow	Shoot at 6	Bursts [1,6] and [2,8]
Next start 7	7 > 6	Need second arrow at 12
[10,16]	10 <= 12	Same second arrow works

Complexity

Measure	Value	Reason
Time	O(n log n)	Sorting dominates the runtime.
Space	O(1)	Only arrow count and current arrow end are stored.

Edge Cases

Intervals sharing an endpoint can be burst by the same arrow.
An empty list returns 0.
Use strict start > arrowEnd to start a new arrow.

Interview Checklist

Sort by end coordinate.
Shoot at the earliest end of the current group.
Start a new arrow only when the next start is greater than arrowEnd.

FAQs

Why shoot at the end?

The earliest end keeps the arrow inside the current balloon while maximizing chance to hit future balloons.

Why use > and not >=?

If a balloon starts exactly at arrowEnd, the arrow at that coordinate still bursts it.

What is the core pattern?

Interval-end greedy grouping.