Minimum Number of Arrows to Burst Balloons

Minimum Number of Arrows to Burst Balloons - Problem

You are given points where points[i] = [x_start, x_end] represents balloons 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.

Input & Output

Example 1 — Basic Overlapping Case

$ Input: points = [[10,16],[2,8],[1,6],[7,12]]

› Output: 2

💡 Note: After sorting by end position: [[1,6],[2,8],[7,12],[10,16]]. First arrow at position 6 bursts [1,6] and [2,8]. Second arrow at position 12 bursts [7,12] and [10,16].

Example 2 — All Overlapping

$ Input: points = [[1,2],[3,4],[5,6],[7,8]]

› Output: 4

💡 Note: No balloons overlap, so we need one arrow for each balloon: 4 arrows total.

Example 3 — Single Balloon

$ Input: points = [[1,2]]

› Output: 1

💡 Note: Only one balloon, so we need exactly one arrow to burst it.

Constraints

1 ≤ points.length ≤ 10⁵
points[i].length == 2
-2³¹ ≤ x_start < x_end ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Balloons with horizontal ranges [[10,16],[2,8],[1,6],[7,12]]

Process

Sort by end position and greedily place arrows

Output

Minimum arrows needed: 2

Key Takeaway

🎯 Key Insight: Sort balloons by end position, then greedily place arrows at optimal positions to cover maximum overlapping balloons

Asked in

M Microsoft 25 a Amazon 20 G Google 15

The key insight is to use a greedy approach: sort balloons by their end positions, then shoot arrows at the earliest possible position that covers the maximum number of overlapping balloons. Best approach uses greedy with sorting. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - One Arrow Per Balloon	O(1)	O(1)	Shoot one arrow for each balloon without considering overlaps
Greedy with Sorting	O(n log n)	O(1)	Sort balloons by end position and greedily shoot arrows at optimal positions

Brute Force - One Arrow Per Balloon — Algorithm Steps

Count the total number of balloons
Return that count as the number of arrows needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Balloons

Simply count total balloons

Return Count

Return balloon count as arrow count

Result

Inefficient but works

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int points[][2], int n) {
    // Brute force: one arrow per balloon
    return n;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for demonstration
    int points[1000][2];
    int n = 0;
    
    char *ptr = line + 1; // Skip first '['
    while(*ptr && *ptr != ']') {
        if(*ptr == '[') {
            ptr++;
            points[n][0] = atoi(ptr);
            while(*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            points[n][1] = atoi(ptr);
            while(*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ']'
            n++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(points, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Just counting the balloons

✓ Linear Growth

Space Complexity

O(1)

Only using a counter variable

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - One Arrow Per Balloon — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler