Abstract / Summary

Find the fewest arrows needed to burst all balloons by shooting each arrow at overlapping balloons.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Greedy
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic interval-covering problem: given a collection of horizontal line segments (represented as [start, end] pairs), determine the minimum number of vertical arrows required to intersect every segment. The algorithm follows a greedy strategy that selects arrow positions based on the earliest finishing interval, thereby guaranteeing an optimal count.

Key Steps

The first decisive operation is sorting the input intervals by their right endpoint. This ordering enables the greedy choice of arrow positions.

points.sort(key = lambda x : x[1])   # sort by x_end

After sorting, two variables are initialized. pos holds the coordinate of the most recent arrow, starting at negative infinity so that the first interval is always considered uncovered. shots counts the arrows that have been fired.

pos = float("-inf")
shots = 0

The core loop iterates over each interval in the sorted list. For each interval p, the algorithm checks whether the current arrow position lies to the left of the interval’s start. If it does, the interval is not covered, prompting the placement of a new arrow at the interval’s end and incrementing the shot counter.

for p in points:
    if pos < p[0]:
        shots += 1
        pos = p[1]

Finally, the accumulated count of arrows is returned.

return shots

Edge Cases Handled

When the input list is empty, the sorting step produces an empty sequence, the loop body never executes, and the function returns 0, correctly indicating that no arrows are needed.

A single interval, regardless of its coordinates, triggers the condition pos < p[0] because pos starts at negative infinity. Consequently, one arrow is placed at the interval’s end, yielding the correct result of 1.

Intervals that share the same end coordinate are grouped together after sorting. The first such interval causes an arrow to be placed at that common end, and subsequent intervals with start points not exceeding this end are automatically covered, avoiding unnecessary additional arrows.

The algorithm also accommodates intervals with negative coordinates or very large integer values because the comparison operations are purely arithmetic and do not rely on any fixed bounds.

Overlapping intervals of varying lengths are correctly managed: the earliest finishing interval determines the arrow position, and any later interval whose start lies before or at that position is considered intersected, ensuring minimal arrow usage.

Performance Optimizations

Sorting by the right endpoint is a deliberate optimization. By processing intervals in order of increasing end, the algorithm guarantees that each newly placed arrow is positioned as far to the left as possible while still covering the current interval. This choice minimizes the chance of future intervals requiring additional arrows.

Using float("-inf") for the initial arrow position eliminates the need for a separate conditional check for the first interval, streamlining the loop logic.

The loop performs a single pass over the sorted list, updating only two scalar variables. This in-place update pattern reduces memory overhead and avoids auxiliary data structures.

Overall, the combination of a single sort operation followed by a linear scan yields an efficient solution that scales well with the size of the input.

Imagine you have a long line of colorful balloons floating in the sky. Some are low, some are high, and they all overlap in different ways. You want to pop every single one of them using the fewest number of arrows possible.

First, imagine looking at the balloons and lining them up based on where they end on the right side. This makes it really easy to see which ones are the closest.

Now, imagine holding an imaginary arrow. You walk along the balloons, and the moment you see a balloon that is starting after your last arrow already hit everything it could, you know it is time to shoot a new arrow. You aim that new arrow right where that balloon ends so it can pop as many other overlapping balloons as possible at the same time.

You keep doing this, walking past the balloons and shooting a new arrow only when you reach a space where there are no more balloons trapped by your previous shot. By the time you reach the end of the line, you have used the smallest number of arrows to get every single balloon. That total number of shots is the answer.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#				Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	BigEggStudy				C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	everthis					JS
	fpdjsns	C++
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	pruthvikp		Python
	ruoru						Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	wisdompeak	C++
	yuanliu666							Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
pruthvikp	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality