What pattern does Minimum Number of Arrows to Burst Balloons use?

The Pattern: Greedy Algorithms (Interval Scheduling) The Heuristic: When covering intervals with points, always pick the earliest finishing interval's end as the point to cover maximum intervals, then skip all intervals overlapping this point before moving to the next uncovered interval.

Minimum Number of Arrows to Burst Balloons

Q: What is the time complexity of Minimum Number of Arrows to Burst Balloons?

O(n log n). Sorting the list of balloons by their end coordinate takes O(n log n). The subsequent single pass through the sorted list takes O(n), resulting in overall O(n log n) time.

Problem

Given a list of points where each point represents the start and end coordinates of a balloon on a horizontal axis, return the minimum number of arrows required to burst all balloons, where an arrow can burst all balloons it passes through.

1 ≤ points.length ≤ 10⁵
points[i].length == 2
−2³¹ ≤ start_i ≤ end_i ≤ 2³¹ - 1

Example

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

Output: 2

Sorting balloons by their end coordinate yields [[1,6],[2,8],[7,12],[10,16]]. The first arrow is shot at position 6, bursting balloons [1,6] and [2,8]. The second arrow is shot at position 12, bursting balloons [7,12] and [10,16]. This greedy choice of shooting at the earliest finishing balloon's end coordinate minimizes the total arrows needed.

Approach

Straightforward Solution

A brute-force approach would check every balloon against every other balloon to find overlaps, resulting in O(n^2) time complexity, which is infeasible for large inputs.

Core Observation

The problem reduces to covering intervals with the minimum number of points (arrows). The key insight is that shooting an arrow at the end of the earliest finishing balloon covers as many overlapping balloons as possible. Because an arrow can be placed anywhere within a balloon’s interval, placing it as late as possible (at the end) maximizes the chance that the same arrow will also intersect future balloons that start later but still overlap that position.

Path to Optimal

Sorting balloons by their end coordinate allows a greedy strategy: always shoot an arrow at the end of the first balloon, then skip all balloons that overlap with this arrow. This reduces the problem to a linear scan after sorting, achieving O(n log n) time due to sorting.

Optimal Approach

Sort the balloons by their end coordinate. Initialize the arrow count to 1 and set the arrow position to the end of the first balloon. Iterate through the balloons; if a balloon starts after the current arrow position, increment the arrow count and update the arrow position to this balloon's end. This ensures each arrow bursts the maximum number of overlapping balloons.

Time

O(n log n)

Sorting the list of balloons by their end coordinate takes O(n log n). The subsequent single pass through the sorted list takes O(n), resulting in overall O(n log n) time.

Space

O(1)

The algorithm uses a constant amount of extra space for counters and pointers, excluding the input array which is sorted in-place.

Solution

1class Solution:
  def findMinArrowShots(self, points: List[List[int]]) -> int:
      
      points.sort(key=lambda x: x[1])
      
      arrows = 1
      arrow_pos = points[0][1]
8
      for start, end in points:
          if start > arrow_pos:
              arrows += 1
              arrow_pos = end
13
      return arrows

Step-by-Step Solution

1

Sort Balloons by Their End Coordinates to Enable Greedy Coverage

4	`points.sort(key=lambda x: x[1])`

Objective

To order balloons so that the earliest finishing balloon is considered first, enabling a greedy strategy to minimize arrows.

Key Insight

Sorting by end coordinate ensures that when an arrow is shot at the end of the first balloon, it covers all balloons overlapping that point. This ordering is crucial because it allows the algorithm to make a locally optimal choice that leads to a globally optimal solution.

Interview Quick-Check

Core Logic

Sorting by end coordinate is the foundation of the greedy interval scheduling approach, enabling linear-time coverage after sorting.

Common Pitfalls & Bugs

Sorting by start coordinate instead of end coordinate can lead to suboptimal arrow placement and incorrect results.

2

Initialize Arrow Count and Position Based on First Balloon

6arrows = 1
7arrow_pos = points[0][1]

Objective

To set the initial arrow count and position to cover the first balloon and any overlapping balloons.

Key Insight

Starting with one arrow at the end of the first balloon ensures that the algorithm begins with a valid coverage point. This initial setup is critical because it establishes the baseline for comparing subsequent balloons and deciding when additional arrows are needed.

Interview Quick-Check

Core Logic

Initializing arrow count to 1 and arrow position to the first balloon's end sets the stage for greedy coverage of overlapping balloons.

State & Boundaries

The first balloon must be covered, so starting with one arrow is necessary.

3

Iterate Through Balloons to Count Additional Arrows Needed

9for start, end in points:
  if start > arrow_pos:
      arrows += 1
      arrow_pos = end

Objective

To scan through the sorted balloons and increment arrow count when a balloon is not covered by the current arrow position.

Key Insight

By comparing each balloon's start coordinate with the current arrow position, the algorithm detects when a balloon lies outside the coverage of the last arrow. At that point, it increments the arrow count and updates the arrow position to the new balloon's end, ensuring minimal arrows are used to cover all balloons.

Interview Quick-Check

Core Logic

The key decision is to shoot a new arrow only when a balloon starts after the current arrow position, guaranteeing minimal arrow usage.

Common Pitfalls & Bugs

Failing to update the arrow position when shooting a new arrow leads to incorrect coverage and overcounting arrows.

State & Boundaries

The loop must consider all balloons to ensure complete coverage.

4

Return the Total Number of Arrows Required

14	`return arrows`

Objective

To output the minimum number of arrows needed to burst all balloons after processing all intervals.

Key Insight

After iterating through all balloons and updating arrow counts as needed, the final arrow count represents the minimal number of arrows required. Returning this value completes the solution.

Interview Quick-Check

Core Logic

Returning the arrow count after processing all balloons provides the minimal number of arrows needed.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 4 Critical

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

Sort the list of balloons by their end coordinate in ascending order.

Sorting by end coordinate enables the greedy strategy to always pick the earliest finishing balloon first, which maximizes the number of balloons burst by a single arrow.

Line 10 Critical

if start > arrow_pos:

Check if the current balloon starts after the last arrow position, indicating it is not covered.

This condition identifies when a new arrow is needed because the current arrow cannot burst this balloon due to non-overlapping intervals.

Line 12 Critical

arrow_pos = end

Update the arrow position to the end of the current balloon for future coverage.

Resetting the arrow position to the current balloon's end maximizes coverage of subsequent overlapping balloons, maintaining the greedy strategy.

Line 7 Core

arrow_pos = points[0][1]

Set the initial arrow position to the end coordinate of the first balloon.

Placing the arrow at the first balloon's end ensures it bursts that balloon and any overlapping balloons, forming the foundation of the greedy coverage.

Line 11 Core

arrows += 1

Increment the arrow count as a new arrow is required for the current balloon.

Increasing the arrow count reflects the necessity to cover a balloon that lies outside the coverage of previous arrows, ensuring correctness.

Line 6 Core

arrows = 1

Initialize the arrow count to 1, assuming at least one arrow is needed.

Starting with one arrow accounts for the first balloon and sets the baseline for counting additional arrows only when necessary.

Line 14 Core

return arrows

Return the total number of arrows needed to burst all balloons.

After processing all balloons, this value represents the minimal number of arrows required, completing the solution.

Line 9 Standard

for start, end in points:

Iterate through each balloon's start and end coordinates.

This loop examines every balloon to determine if it is covered by the current arrow or requires a new arrow.

Test Your Understanding

Why does shooting an arrow at the end coordinate of the earliest finishing balloon guarantee a minimal number of arrows?

Because shooting at the earliest finishing balloon's end covers all balloons overlapping that point, allowing the algorithm to burst the maximum number of balloons with a single arrow before moving on to the next uncovered balloon.

Don't just read it. Drill it.

Reconstruct Minimum Number of Arrows to Burst Balloons from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Number of Arrows to Burst Balloons drill

or drill a free problem

1	`class Solution:`
2	`def findMinArrowShots(self, points: List[List[int]]) -> int:`
3
4	`points.sort(key=lambda x: x[1])`
5
6	`arrows = 1`
7	`arrow_pos = points[0][1]`
8
9	`for start, end in points:`
10	`if start > arrow_pos:`
11	`arrows += 1`
12	`arrow_pos = end`
13
14	`return arrows`

9	`for start, end in points:`
10	`if start > arrow_pos:`
11	`arrows += 1`
12	`arrow_pos = end`

Problem

Example

Approach

Solution

Step-by-Step Solution

Sort Balloons by Their End Coordinates to Enable Greedy Coverage

Initialize Arrow Count and Position Based on First Balloon

Iterate Through Balloons to Count Additional Arrows Needed

Return the Total Number of Arrows Required

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.