Minimum Number of Arrows to Burst Balloons (LeetCode 452)
Each balloon is a horizontal span [xstart, xend] on the x-axis, and points lists one span per balloon. The height of a balloon is not given.
An arrow flies straight up from a point x on the x-axis. It bursts every balloon whose span contains x, which means xstart <= x <= xend. You can shoot as many arrows as you like, and an arrow never stops. A balloon whose span only touches x with its edge is also burst.
Return the fewest arrows that burst every balloon.
Worked Examples
points = [[10,16],[2,8],[1,6],[7,12]]2[1,6], [2,8], [7,12] and [10,16]. An arrow at 6 bursts [1,6] and [2,8]. The balloon [7,12] starts after 6, so a second arrow goes at 12 and bursts [7,12] and [10,16].points = [[1,2],[3,4],[5,6],[7,8]]4points = [[1,2],[2,3],[3,4],[4,5]]2[1,2] and [2,3] both contain 2, and [3,4] and [4,5] both contain 4. An arrow at 2 and an arrow at 4 burst all four balloons, because a balloon that only touches the arrow is burst.⚖️Formal Constraints & Bounds
1 <= points.length <= 105points[i].length == 2-231 <= xstart < xend <= 231 - 1
Core Insight
Sort by end and shoot at the end of the first balloon that is not yet burst. That position is as far right as the arrow can go and still burst it, so it also bursts every later balloon that has already started. The number of arrows is the number of balloons that needed a new one.
Real-World Scenario & Production Applications
Any job where one action serves everything that is active at one moment: a shuttle that leaves once and takes every group waiting at that time, a maintenance run that serves every job whose allowed time range includes it, one audit that covers every transaction still open at that time. The fewest actions equals the fewest groups of ranges that share a point.
Step-by-Step Execution Trace Table
Example 3, points = [[1,2],[2,3],[3,4],[4,5]] (the touching case, already sorted by end):
[start, end] | arrow_x before | Check arrow_x is None or start > arrow_x | arrows after | arrow_x after |
|---|---|---|---|---|
[1,2] | None | arrow_x is None: yes, shoot | 1 | 2 |
[2,3] | 2 | 2 > 2: no, already hit | 1 | 2 |
[3,4] | 2 | 3 > 2: yes, shoot | 2 | 4 |
[4,5] | 4 | 4 > 4: no, already hit | 2 | 4 |
| 1 | You never need to place arrows freely, only to count the groups of balloons that can share one arrow: sort by `end`, so the balloon that ends first is always the next one to hit. |
| 2 | An arrow at the `end` of that balloon is as far right as it can go and still hit it, so it also hits every later balloon that has already started: keep `arrow_x`, the position of the last arrow. |
| 3 | Start `arrows = 0` and `arrow_x = None`, loop `for start, end in points` once, and shoot a new arrow at `end` whenever the balloon is not yet hit. |
| 4 | The trap: a balloon that only touches the last arrow is hit, so the test for a new arrow is `start > arrow_x`, never `start >= arrow_x`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every balloon is an interval [start, end] on a line. An arrow at position x hits every balloon with start <= x <= end. You need the fewest arrows so that every balloon is hit. This is the same setup as Interval Scheduling with a different question: you count the groups of balloons that share one arrow, not the balloons to remove.
Sort the balloons by end. The balloon that ends first must be hit by some arrow, and that arrow sits at or before its end. Moving the arrow right, up to exactly that end, loses nothing. Every balloon it hit started at or before the old position, so it also starts at or before the new one. Every balloon ends at or after that end, so the new position is still inside all of them. So shoot at the end of the first balloon, skip every balloon that starts at or before arrow_x, and shoot again at the end of the first balloon that starts after it.
🚌 The Analogy: Departure Times for an Airport Shuttle
Each tour group waits at the airport from a start time to an end time. A shuttle that leaves at time x takes every group that is waiting at x. You want the fewest departures. Look at the group whose waiting time ends first. A shuttle must leave before that time ends, and the latest possible departure is exactly that end time. That departure also takes every other group that is already waiting. Ignore all the groups it takes, and repeat with the next group whose waiting time ends first.
🔑 Why It Works
Two facts give the result. First, an arrow at the end of the first balloon hits every balloon that an arrow at any other position hitting the first balloon would hit, so the choice never has to be undone. Second, every balloon that needs a new arrow starts after the previous arrow, and that arrow sits at the end of an earlier balloon in the sorted order. So the balloons that cause a new arrow do not share any point with each other, and no single arrow can hit two of them. The count is therefore both reachable and the smallest possible. The sort costs O(N log N), and the scan costs O(N).
Using
left >= last_rightbecause Interval Scheduling does: in Non-overlapping Intervals (LC 435) two intervals that touch can both stay. A pair chain needsright < left, so[[1,2],[2,3]]has the answer 1, and>=returns 2.Sorting by
leftinstead ofright: one long pair at the front blocks the short pairs inside it. On[[1,6],[2,3],[4,5]]the answer is 2 ([2,3]then[4,5]), and a left-sorted scan returns 1.Starting
last_rightat0: the values can be negative. On[[-5,-1]]the pair starts below 0, so it is skipped and the code returns 0 instead of 1. UseNone.Reaching for a longest-chain DP first: comparing every pair with every earlier pair is correct, and costs about 500,000 comparisons at 1000 pairs. The sort-and-scan gives the same answer in
O(N log N), because only the end of the last chosen pair matters.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The fewest arrows so that every balloon is burst": choose the fewest points that touch every interval. When the question is how many groups of intervals can share one point, sort by end and shoot at the end of the first interval not yet hit. That is the signal for End-Time Groups.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule per balloon: if arrow_x is None or start > arrow_x, add one to arrows and set arrow_x = end; otherwise the balloon is already hit.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
start > arrow_x, notstart >= arrow_x: a balloon that starts exactly atarrow_xis hit by it. On[[1,2],[2,3],[3,4],[4,5]]the>=version returns 4 instead of 2.Sort by end, not by start: on
[[1,6],[2,3],[4,5]]the start order puts[1,6]first, the arrow goes at 6, and[2,3]and[4,5]are counted as hit, so the code returns 1 instead of 2.arrow_x = None, not0: coordinates can be negative, so on[[-5,-1]]a start value of0marks the balloon as hit and the code returns 0 instead of 1.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use End-Time Groups. I need the fewest points that touch every balloon, so I sort the balloons by their end coordinate. The balloon that ends first must be hit by some arrow, and the best place for that arrow is exactly its end. It is as far right as the arrow can go and still hit that balloon, so it also hits every later balloon that has already started. I keep arrow_x, the position of the last arrow, and walk the balloons once. A balloon that starts at or before arrow_x is already hit. A balloon that starts after arrow_x needs a new arrow at its own end. The trap is the comparison: a balloon that only touches arrow_x is hit, so the test is strictly greater, not greater or equal. That is the opposite of Interval Scheduling, where intervals that touch do not overlap. Sorting is
O(N log N)time, and beyond the sort I keep two numbers, so the extra space isO(1).
Complexity & Mathematical Proof
O(N log N)
Look at the code: points.sort(key=lambda p: p[1]) takes O(N log N). The loop for start, end in points visits each balloon once and does one comparison and at most two assignments, a constant amount of work: O(N). The sort dominates, so the total is O(N log N).
O(N) Auxiliary
Look at memory: the sort with a key builds N keys, and Python's sort may use up to O(N) more, so O(N). Beyond the sort, the code keeps only arrows and arrow_x: O(1).
T(N) = O(N log N) + O(N) = O(N log N)
Derivation Progression
O(N log N) key=lambda p: p[1]
Puts the balloon that ends first in front, so each new arrow can go at the end of the first balloon it must hit.
N iterations of O(1)
for start, end in points compares start with arrow_x and, when a new arrow is needed, updates two numbers.
O(N log N)
The sort dominates the linear pass.
Variable Definitions
Number of balloons, len(points)
Position of the last arrow that was shot
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N) sort keys and buffer; O(1) (arrows, arrow_x) beyond the sort
O(1): one integer
Boundary Best / Worst Cases
: the balloons already arrive sorted by end, and Python's sort then needs one pass
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the minimum number of arrows to burst all balloons", "the fewest points that touch every interval". It is the sort of Interval Scheduling with a different question: count the groups of intervals that share a point. At production scale it is covering: one action that serves everything active at one moment.
and coordinates from to . The sort costs and the scan . In Java or C++ compare the coordinates with < and >: a subtraction such as a - b can overflow a 32-bit integer.
Intervals that arrive online in any order cannot use the end-sorted scan: an interval that arrives late may need an arrow that was already placed in the wrong spot. Collect the intervals per time window, sort each batch by end, and run the scan on the batch.
Core Algorithmic State Invariants
- Why the End of the First Balloon Is Safe
An arrow that bursts the balloon with the smallest end sits at x <= end. Every other balloon ends at or after that end, so moving the arrow right to end keeps every balloon it burst and can only add more. So placing the first arrow exactly at that end is never worse.
- Arrows Equal the Largest Set of Balloons That Share No Point
The balloons that cause a new arrow start after the previous arrow, which sits at the end of an earlier balloon in the sorted order. So they share no point with each other, and each one needs its own arrow. In Example 1 the balloons [1,6] and [10,16] are such a set, and the answer is 2.
- Compare Coordinates, Do Not Subtract Them
Coordinates reach -231 and 231 - 1. In Java or C++ a subtraction in a sort comparator such as a[1] - b[1] can overflow a 32-bit integer and order the balloons wrongly. Compare with < and >, or use Integer.compare.
Minimum Number of Arrows to Burst Balloons (LeetCode 452)
Each balloon is a horizontal span [xstart, xend] on the x-axis, and points lists one span per balloon. The height of a balloon is not given.
An arrow flies straight up from a point x on the x-axis. It bursts every balloon whose span contains x, which means xstart <= x <= xend. You can shoot as many arrows as you like, and an arrow never stops. A balloon whose span only touches x with its edge is also burst.
Return the fewest arrows that burst every balloon.
Worked Examples
points = [[10,16],[2,8],[1,6],[7,12]]2[1,6], [2,8], [7,12] and [10,16]. An arrow at 6 bursts [1,6] and [2,8]. The balloon [7,12] starts after 6, so a second arrow goes at 12 and bursts [7,12] and [10,16].points = [[1,2],[3,4],[5,6],[7,8]]4points = [[1,2],[2,3],[3,4],[4,5]]2[1,2] and [2,3] both contain 2, and [3,4] and [4,5] both contain 4. An arrow at 2 and an arrow at 4 burst all four balloons, because a balloon that only touches the arrow is burst.⚖️Formal Constraints & Bounds
1 <= points.length <= 105points[i].length == 2-231 <= xstart < xend <= 231 - 1
Core Insight
Sort by end and shoot at the end of the first balloon that is not yet burst. That position is as far right as the arrow can go and still burst it, so it also bursts every later balloon that has already started. The number of arrows is the number of balloons that needed a new one.
Real-World Scenario & Production Applications
Any job where one action serves everything that is active at one moment: a shuttle that leaves once and takes every group waiting at that time, a maintenance run that serves every job whose allowed time range includes it, one audit that covers every transaction still open at that time. The fewest actions equals the fewest groups of ranges that share a point.
Step-by-Step Execution Trace Table
Example 3, points = [[1,2],[2,3],[3,4],[4,5]] (the touching case, already sorted by end):
[start, end] | arrow_x before | Check arrow_x is None or start > arrow_x | arrows after | arrow_x after |
|---|---|---|---|---|
[1,2] | None | arrow_x is None: yes, shoot | 1 | 2 |
[2,3] | 2 | 2 > 2: no, already hit | 1 | 2 |
[3,4] | 2 | 3 > 2: yes, shoot | 2 | 4 |
[4,5] | 4 | 4 > 4: no, already hit | 2 | 4 |
| 1 | You never need to place arrows freely, only to count the groups of balloons that can share one arrow: sort by `end`, so the balloon that ends first is always the next one to hit. |
| 2 | An arrow at the `end` of that balloon is as far right as it can go and still hit it, so it also hits every later balloon that has already started: keep `arrow_x`, the position of the last arrow. |
| 3 | Start `arrows = 0` and `arrow_x = None`, loop `for start, end in points` once, and shoot a new arrow at `end` whenever the balloon is not yet hit. |
| 4 | The trap: a balloon that only touches the last arrow is hit, so the test for a new arrow is `start > arrow_x`, never `start >= arrow_x`. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every balloon is an interval [start, end] on a line. An arrow at position x hits every balloon with start <= x <= end. You need the fewest arrows so that every balloon is hit. This is the same setup as Interval Scheduling with a different question: you count the groups of balloons that share one arrow, not the balloons to remove.
Sort the balloons by end. The balloon that ends first must be hit by some arrow, and that arrow sits at or before its end. Moving the arrow right, up to exactly that end, loses nothing. Every balloon it hit started at or before the old position, so it also starts at or before the new one. Every balloon ends at or after that end, so the new position is still inside all of them. So shoot at the end of the first balloon, skip every balloon that starts at or before arrow_x, and shoot again at the end of the first balloon that starts after it.
🚌 The Analogy: Departure Times for an Airport Shuttle
Each tour group waits at the airport from a start time to an end time. A shuttle that leaves at time x takes every group that is waiting at x. You want the fewest departures. Look at the group whose waiting time ends first. A shuttle must leave before that time ends, and the latest possible departure is exactly that end time. That departure also takes every other group that is already waiting. Ignore all the groups it takes, and repeat with the next group whose waiting time ends first.
🔑 Why It Works
Two facts give the result. First, an arrow at the end of the first balloon hits every balloon that an arrow at any other position hitting the first balloon would hit, so the choice never has to be undone. Second, every balloon that needs a new arrow starts after the previous arrow, and that arrow sits at the end of an earlier balloon in the sorted order. So the balloons that cause a new arrow do not share any point with each other, and no single arrow can hit two of them. The count is therefore both reachable and the smallest possible. The sort costs O(N log N), and the scan costs O(N).
Using
left >= last_rightbecause Interval Scheduling does: in Non-overlapping Intervals (LC 435) two intervals that touch can both stay. A pair chain needsright < left, so[[1,2],[2,3]]has the answer 1, and>=returns 2.Sorting by
leftinstead ofright: one long pair at the front blocks the short pairs inside it. On[[1,6],[2,3],[4,5]]the answer is 2 ([2,3]then[4,5]), and a left-sorted scan returns 1.Starting
last_rightat0: the values can be negative. On[[-5,-1]]the pair starts below 0, so it is skipped and the code returns 0 instead of 1. UseNone.Reaching for a longest-chain DP first: comparing every pair with every earlier pair is correct, and costs about 500,000 comparisons at 1000 pairs. The sort-and-scan gives the same answer in
O(N log N), because only the end of the last chosen pair matters.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The fewest arrows so that every balloon is burst": choose the fewest points that touch every interval. When the question is how many groups of intervals can share one point, sort by end and shoot at the end of the first interval not yet hit. That is the signal for End-Time Groups.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule per balloon: if arrow_x is None or start > arrow_x, add one to arrows and set arrow_x = end; otherwise the balloon is already hit.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
start > arrow_x, notstart >= arrow_x: a balloon that starts exactly atarrow_xis hit by it. On[[1,2],[2,3],[3,4],[4,5]]the>=version returns 4 instead of 2.Sort by end, not by start: on
[[1,6],[2,3],[4,5]]the start order puts[1,6]first, the arrow goes at 6, and[2,3]and[4,5]are counted as hit, so the code returns 1 instead of 2.arrow_x = None, not0: coordinates can be negative, so on[[-5,-1]]a start value of0marks the balloon as hit and the code returns 0 instead of 1.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use End-Time Groups. I need the fewest points that touch every balloon, so I sort the balloons by their end coordinate. The balloon that ends first must be hit by some arrow, and the best place for that arrow is exactly its end. It is as far right as the arrow can go and still hit that balloon, so it also hits every later balloon that has already started. I keep arrow_x, the position of the last arrow, and walk the balloons once. A balloon that starts at or before arrow_x is already hit. A balloon that starts after arrow_x needs a new arrow at its own end. The trap is the comparison: a balloon that only touches arrow_x is hit, so the test is strictly greater, not greater or equal. That is the opposite of Interval Scheduling, where intervals that touch do not overlap. Sorting is
O(N log N)time, and beyond the sort I keep two numbers, so the extra space isO(1).
Complexity & Mathematical Proof
O(N log N)
Look at the code: points.sort(key=lambda p: p[1]) takes O(N log N). The loop for start, end in points visits each balloon once and does one comparison and at most two assignments, a constant amount of work: O(N). The sort dominates, so the total is O(N log N).
O(N) Auxiliary
Look at memory: the sort with a key builds N keys, and Python's sort may use up to O(N) more, so O(N). Beyond the sort, the code keeps only arrows and arrow_x: O(1).
T(N) = O(N log N) + O(N) = O(N log N)
Derivation Progression
O(N log N) key=lambda p: p[1]
Puts the balloon that ends first in front, so each new arrow can go at the end of the first balloon it must hit.
N iterations of O(1)
for start, end in points compares start with arrow_x and, when a new arrow is needed, updates two numbers.
O(N log N)
The sort dominates the linear pass.
Variable Definitions
Number of balloons, len(points)
Position of the last arrow that was shot
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N) sort keys and buffer; O(1) (arrows, arrow_x) beyond the sort
O(1): one integer
Boundary Best / Worst Cases
: the balloons already arrive sorted by end, and Python's sort then needs one pass
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the minimum number of arrows to burst all balloons", "the fewest points that touch every interval". It is the sort of Interval Scheduling with a different question: count the groups of intervals that share a point. At production scale it is covering: one action that serves everything active at one moment.
and coordinates from to . The sort costs and the scan . In Java or C++ compare the coordinates with < and >: a subtraction such as a - b can overflow a 32-bit integer.
Intervals that arrive online in any order cannot use the end-sorted scan: an interval that arrives late may need an arrow that was already placed in the wrong spot. Collect the intervals per time window, sort each batch by end, and run the scan on the batch.
Core Algorithmic State Invariants
- Why the End of the First Balloon Is Safe
An arrow that bursts the balloon with the smallest end sits at x <= end. Every other balloon ends at or after that end, so moving the arrow right to end keeps every balloon it burst and can only add more. So placing the first arrow exactly at that end is never worse.
- Arrows Equal the Largest Set of Balloons That Share No Point
The balloons that cause a new arrow start after the previous arrow, which sits at the end of an earlier balloon in the sorted order. So they share no point with each other, and each one needs its own arrow. In Example 1 the balloons [1,6] and [10,16] are such a set, and the answer is 2.
- Compare Coordinates, Do Not Subtract Them
Coordinates reach -231 and 231 - 1. In Java or C++ a subtraction in a sort comparator such as a[1] - b[1] can overflow a 32-bit integer and order the balloons wrongly. Compare with < and >, or use Integer.compare.