Skip to main content
Talentd

Minimum Number of Arrows to Burst Balloons - Solution & Explanation

MediumArrayGreedySorting15 min readAsked at: Amazon, Microsoft, Goldman Sachs +5
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given a list of balloons where each balloon is represented as an interval [start, end] on the x-axis. One arrow shot at position x bursts every balloon whose interval contains x. The task is to compute the minimum number of arrows required to burst all balloons.

Approach 1: Greedy Approach Using Sorting by End Points (O(n log n) time, O(1) space)

This problem behaves like an interval covering problem. Sort the balloons by their end coordinate. Shoot the first arrow at the end of the first interval, then iterate through the sorted intervals. If the next balloon starts after the current arrow position, you need a new arrow and update the arrow position to the current balloon's end. Otherwise, the current arrow already bursts that balloon. The key insight: placing the arrow at the earliest possible end maximizes overlap with future balloons. This greedy strategy works because choosing the smallest end preserves the most room for upcoming intervals.

Sorting dominates the runtime at O(n log n), while the traversal is linear. The algorithm uses constant extra memory O(1) if sorting is done in-place. This approach directly leverages ideas from greedy algorithms, sorting, and interval processing on an array.

Approach 2: Interval Scheduling Maximization (O(n log n) time, O(1) space)

This perspective treats the problem as the classic interval scheduling variant. Instead of selecting the maximum number of non-overlapping intervals, you group overlapping intervals that can be covered by a single arrow. After sorting intervals by end coordinate, iterate through them and maintain the end of the current overlapping group. When a new interval starts beyond the current group end, the previous group requires one arrow and a new group begins. Conceptually, each arrow corresponds to one maximal set of overlapping intervals.

The mechanics are nearly identical to the greedy solution but framed through scheduling theory. Sorting costs O(n log n), and the single pass scan is O(n) with constant auxiliary memory O(1). This interpretation helps when connecting the problem to classic interval scheduling and greedy proofs.

Recommended for interviews: The greedy strategy that sorts intervals by end points is the expected solution. Interviewers look for the insight that placing the arrow at the earliest finishing balloon maximizes coverage of future balloons. Explaining the interval scheduling connection strengthens the reasoning. A brute-force overlap simulation shows understanding, but the O(n log n) greedy solution demonstrates strong algorithmic thinking.

Approach 1: Greedy Approach Using Sorting by End Points

This approach involves sorting the balloons by their end points. Once sorted, we shoot an arrow at the end point of the first balloon, and then continue moving through the list, checking if subsequent balloons overlap with the burst of the arrow. If a balloon does not overlap, we need an additional arrow for it.

This C solution uses standard libraries to sort a list of balloon intervals by their end points, ensuring we minimize the number of arrows used. Sorting ensures that at every step, we maximize the number of balloons burst by a single arrow.

The function compare is used with qsort to sort the intervals by their end points. Then, we maintain an `end` variable to store the position of the last arrow shot. We iterate through the intervals, and for each interval that does not overlap with the current `end`, we shoot a new arrow and update `end`.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to the sorting step, where n is the number of balloons.
Space Complexity: O(1) if we ignore the space used for sorting.

Try this approach in the editor β†’

Approach 2: Interval Scheduling Maximization

This approach is adapted from the interval scheduling maximization pattern, where we attempt to find the maximum number of non-overlapping intervals. By sorting the intervals, we can focus on selecting the maximum number of compatible balloons.

The C implementation sorts balloons by their starting x coordinate to maximize the intervals which can overlap and thus require fewer arrows.

Overlapping intervals are managed by checking the end position of current overlaps. If overlaps occur, the continuation of overlapping checks determines the next 'strongly ending' balloon that indicates a need for a new arrow, thereby ensuring no excess arrows.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) resulting from sorting operations.
Space Complexity: O(1) when sorting space considerations are minimized.

Try this approach in the editor β†’

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Greedy Approach Using Sorting by End Points

Time Complexity: O(n log n) due to the sorting step, where n is the number of balloons.
Space Complexity: O(1) if we ignore the space used for sorting.

Interval Scheduling Maximization

Time Complexity: O(n log n) resulting from sorting operations.
Space Complexity: O(1) when sorting space considerations are minimized.

Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Sorting by End PointsO(n log n)O(1)General case. Standard optimal solution used in interviews.
Interval Scheduling MaximizationO(n log n)O(1)When reasoning using classic interval scheduling theory.

Video Solution

Minimum Number of Arrows to Burst Balloons - Leetcode 452 - Python β€’ NeetCodeIO β€’ 32,174 views views

Watch 9 more video solutions β†’

Frequently Asked Questions

Is Minimum Number of Arrows to Burst Balloons easy or hard?
The problem is classified as Medium difficulty on LeetCode. The implementation is short, but recognizing the greedy insight of sorting by interval end points and placing arrows optimally requires familiarity with interval scheduling patterns.
Minimum Number of Arrows to Burst Balloons Python/Java solution
Implement the greedy approach by sorting the intervals by their end coordinate. Then iterate through the list while tracking the current arrow position and incrementing the arrow count whenever a new non-overlapping interval appears. This logic is identical across Python, Java, C++, and other languages.
How to solve Minimum Number of Arrows to Burst Balloons in O(n)?
Achieving strict O(n) time is not practical in the general case because the intervals need to be ordered by end position. The optimal strategy sorts intervals first, giving O(n log n) time. If the intervals were already sorted by end coordinate, the greedy scan would run in O(n).
What is the best approach for Minimum Number of Arrows to Burst Balloons?
The best approach is a greedy strategy that sorts balloons by their ending coordinate. Shoot an arrow at the end of the first interval and continue scanning. If the next balloon starts after the arrow position, fire a new arrow. This method runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Minimum Number of Arrows to Burst Balloons asked at Google/Amazon/Meta?
Interval greedy problems similar to this one frequently appear in interviews at companies like Amazon, Google, and Meta. The question tests understanding of interval scheduling, greedy choice properties, and sorting-based optimization patterns.
What data structure is used in Minimum Number of Arrows to Burst Balloons?
The problem primarily uses arrays to store intervals and relies on sorting and greedy traversal. No advanced data structures are required. The algorithm keeps track of the current arrow position while iterating through the sorted intervals.
What is the time complexity of Minimum Number of Arrows to Burst Balloons?
The optimal solution runs in O(n log n) time because the intervals must be sorted by their end coordinates. After sorting, a single linear scan determines how many arrows are required, which adds O(n). Space complexity is O(1) if sorting is done in-place.

Ready to solve this problem?

Practice Minimum Number of Arrows to Burst Balloons with our built-in code editor and test cases.

Practice on FleetCode
Previous

Meeting Rooms II

Next

Non-overlapping Intervals