Log inSign up
mediumLeetCodeNot Started

Minimum Number of Arrows to Burst Balloons

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

There are some spherical balloons taped to 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.

An arrow can be shot up vertically from different points along the x-axis. A balloon with [xstart, xend] is burst by an arrow shot at x if xstart <= x <= xend.

There is no limit to the number of balloons an arrow can burst as long as their intervals overlap with the shot position.

Return the minimum number of arrows that must be shot to burst all balloons.

Example 1 · Example 1: Overlapping Balloons:

Input: points = [[10, 16], [2, 8], [1, 6], [7, 12]]
Output: 2
Explanation: Sorted by end: [1, 6], [2, 8], [7, 12], [10, 16].\n- Shoot arrow 1 at x = 6: bursts [1, 6] and [2, 8].\n- Next balloon [7, 12] starts at 7 > 6: Shoot arrow 2 at x = 12: bursts [7, 12] and [10, 16].\nTotal arrows = 2.

Example 2 · Example 2: All Disjoint:

Input: points = [[1, 2], [3, 4], [5, 6], [7, 8]]
Output: 4
Explanation: No balloons overlap. Each balloon requires its own arrow. Total arrows = 4.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the equivalence between interval stabbing and interval scheduling.
  • Handle 32-bit signed integer subtraction overflow safely during sorting.
  • Implement the optimal greedy arrow-shooting algorithm in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Interval stabbing problem (piercing intervals with minimum points).
  • Intervals on 1D line with overlapping burst effect.
  • Requires min shots/points intersecting all intervals.

Algorithmic Decision Tree:

  • Sort by points[i][1] ascending.
  • Whenever points[i][0] > arrowPos: arrows++, arrowPos = points[i][1].

Connected Patterns:

Non-overlapping IntervalsActivity SelectionMeeting Rooms II

1. Recursive Interval Cover Search

Intuition

Sort balloons and recursively evaluate shooting an arrow at each candidate endpoint or trying subsequent intervals.

Algorithm

  1. Step 1: Sort points by end coordinate.
  2. Step 2: Define recursive solve(idx, lastArrow) returning min arrows from idx onwards.
  3. Step 3: If idx == n, return 0.
  4. Step 4: If points[idx][0] <= lastArrow, balloon is already burst -> solve(idx + 1, lastArrow).
  5. Step 5: Otherwise, shoot at points[idx][1] -> 1 + solve(idx + 1, points[idx][1]).
  6. Step 6: Return result.

Enumerate Candidate Shooting Points

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Evaluate coordinate x = 2
Visual state
Values and pointers at this exact step
intervals
B0
[10, 16]
B1
[2, 8]
B2
[1, 6]
↑ arrow
B3
[7, 12]
candidateX2
burstCount2
remaining2
arrows1
Variables at this step
candidateX
2
burstCount
2
remaining
2
arrows
1
Check / comparison
Shoot candidate arrow at coordinate x = 2
Decision / next transition
Bursts B1 [2,8] and B2 [1,6]. B0 and B3 remain unburst.
Why this step matters

Evaluate coordinate x = 2. It pierces balloons spanning through 2, namely [1,6] and [2,8].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int idx, long long lastArrow, const vector<vector<int>>& points) {
9 if (idx == points.size()) return 0;
10 if (points[idx][0] <= lastArrow) {
11 return solve(idx + 1, lastArrow, points);
12 }
13 return 1 + solve(idx + 1, points[idx][1], points);
14 }
15public:
16 int findMinArrowShots(vector<vector<int>>& points) {
17 sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
18 return a[1] < b[1];
19 });
20 return solve(0, -3e18, points);
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<vector<int>> points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
27 cout << "Min Arrows: " << sol.findMinArrowShots(points) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Sort by Start + Interval Intersection Shrinking

Intuition

Sort balloons by start coordinate. Keep track of the current arrow coverage interval [currentStart, currentEnd] by intersecting consecutive intervals.

Algorithm

  1. Step 1: If points is empty, return 0.
  2. Step 2: Sort points ascending by start coordinate points[i][0].
  3. Step 3: Initialize arrows = 1 and currentEnd = points[0][1].
  4. Step 4: For each subsequent balloon i: if points[i][0] <= currentEnd, shrink currentEnd = min(currentEnd, points[i][1]).
  5. Step 5: Else, shoot new arrow: arrows++, currentEnd = points[i][1].
  6. Step 6: Return arrows.

Sort by Start Coordinate & Shrink Overlap Windows

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Sorting groups balloons along the x-axis
Visual state
Values and pointers at this exact step
intervals
B2
[1, 6]
↑ curr
B1
[2, 8]
B3
[7, 12]
B0
[10, 16]
i0
currEnd6
arrows1
Variables at this step
i
0
currEnd
6
arrows
1
Check / comparison
Sort by start coordinate: [1,6], [2,8], [7,12], [10,16]
Decision / next transition
Initialize group 1 with [1, 6]. currEnd = 6, arrows = 1.
Why this step matters

Sorting groups balloons along the x-axis. The first cluster starts with [1,6].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int findMinArrowShots(vector<vector<int>>& points) {
10 if (points.empty()) return 0;
11 sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
12 return a[0] < b[0];
13 });
14
15 int arrows = 1;
16 int currentEnd = points[0][1];
17
18 for (size_t i = 1; i < points.size(); ++i) {
19 if (points[i][0] <= currentEnd) {
20 currentEnd = min(currentEnd, points[i][1]);
21 } else {
22 arrows++;
23 currentEnd = points[i][1];
24 }
25 }
26
27 return arrows;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<vector<int>> points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
34 cout << "Min Arrows (Shrink): " << sol.findMinArrowShots(points) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(1) auxiliary

3. Greedy Sort by End Coordinate

Intuition

Sort balloons in ascending order of their end coordinate. Shoot each arrow at the earliest possible end coordinate to burst maximum subsequent balloons.

Algorithm

  1. Step 1: If points array is empty, return 0.
  2. Step 2: Sort points ascending by points[i][1] using an overflow-safe comparator.
  3. Step 3: Shoot first arrow at arrowPos = points[0][1] and initialize arrows = 1.
  4. Step 4: Iterate from i = 1 to points.length - 1.
  5. Step 5: If points[i][0] > arrowPos, shoot a new arrow: arrows++, arrowPos = points[i][1].
  6. Step 6: Return arrows.

Greedy Sort by End Coordinate

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Shooting at the earliest end guarantees B0 is burst, while giving maximal reach for any subsequent balloon
Visual state
Values and pointers at this exact step
intervals
B0
[1, 6]
↑ arrow
B1
[2, 8]
B2
[7, 12]
B3
[10, 16]
arrowPos6
arrowsCount1
i0
Variables at this step
arrowPos
6
arrowsCount
1
i
0
Check / comparison
Sort by end coordinate: [1,6], [2,8], [7,12], [10,16]
Decision / next transition
Greedy choice: Shoot arrow 1 at earliest end x = points[0][1] = 6.
Why this step matters

Shooting at the earliest end guarantees B0 is burst, while giving maximal reach for any subsequent balloon.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int findMinArrowShots(vector<vector<int>>& points) {
10 if (points.empty()) return 0;
11 sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
12 return a[1] < b[1];
13 });
14
15 int arrows = 1;
16 long long arrowPos = points[0][1];
17
18 for (size_t i = 1; i < points.size(); ++i) {
19 if (points[i][0] > arrowPos) {
20 arrows++;
21 arrowPos = points[i][1];
22 }
23 }
24
25 return arrows;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<vector<int>> points = {{10, 16}, {2, 8}, {1, 6}, {7, 12}};
32 cout << "Min Arrows (Optimal): " << sol.findMinArrowShots(points) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Backtracking Point SelectionO(2^N)O(N)Recursively try choosing between shooting at distinct balloon boundaries and evaluating valid covers.Combinatorial balloon combinations.
2.Better — Sorting by Start + Overlap Intersection ShrinkingO(N log N)O(1) auxiliarySort by start coordinate. Maintain current overlapping interval [start, end]. For each balloon, if it overlaps, narrow the intersection end = min(end, curr.end); otherwise start a new arrow.Sorting operation.
3.Optimal — Greedy Sort by End CoordinateOptimalO(N log N)O(1) auxiliarySort balloons by end coordinate ascending. Shoot the first arrow at points[0][1]. Whenever points[i][0] > arrowPos, shoot a new arrow at points[i][1].Initial sort.
Back to DSA Sheet