Problem Description

You have balloons attached to a wall represented as a 2D plane. Each balloon is given as an interval [x_start, x_end] representing its horizontal span along the x-axis. The balloons extend vertically (we don't know their exact y-coordinates), but we know their horizontal coverage.

You can shoot arrows vertically upward from any position along the x-axis. When an arrow is shot from position x, it travels straight up infinitely and bursts any balloon whose horizontal range includes x. In other words, a balloon with range [x_start, x_end] gets burst if the arrow is shot from any position x where x_start ≤ x ≤ x_end.

The goal is to find the minimum number of arrows needed to burst all balloons.

Key Points:

• Each balloon is represented as [x_start, x_end]
• An arrow shot at position x bursts all balloons where x_start ≤ x ≤ x_end
• Arrows travel vertically upward and can burst multiple balloons if they overlap at that x-position
• You need to determine the smallest number of arrows required to burst every balloon

Solution Explanation:

The solution uses a greedy approach with interval scheduling:

1. Sort balloons by their end points - This allows us to process balloons in order of where they end
2. Track the last arrow position - Initialize with negative infinity
3. For each balloon:
   • If the balloon's start is greater than the last arrow position, we need a new arrow
   • Place the new arrow at the balloon's end position (optimal placement to potentially hit more balloons)
   • Increment the arrow count
4. Return the total number of arrows used

The key insight is that by sorting by end points and placing arrows at the rightmost position of each balloon group, we maximize the chance of hitting overlapping balloons with a single arrow.

Intuition

Think of this problem as trying to find the minimum number of points that can "cover" all intervals. When multiple balloons overlap at some x-coordinate, a single arrow at that position can burst all of them. So we're looking for the smallest set of x-coordinates where each balloon is hit by at least one arrow.

The key realization is that this is an interval scheduling problem. We want to group overlapping intervals together and shoot one arrow per group.

Why sort by end points? Consider what happens when we process balloons in order of their ending positions:

• When we encounter a balloon that doesn't overlap with our last arrow position, we must shoot a new arrow
• Where should we place this new arrow? At the balloon's end point
• Why the end point? Because it gives us the best chance to hit other balloons that might start before this end point

For example, if we have balloons [1,6] and [2,8]:

• If we place an arrow at position 6 (end of first balloon), it hits both
• If we place it at position 1 (start of first balloon), it only hits the first one

The greedy choice is always to place the arrow as far right as possible (at the end point) while still hitting the current balloon. This maximizes our coverage for balloons that haven't been processed yet.

By sorting by end points and greedily placing arrows, we ensure that:

1. Each arrow is placed optimally to potentially hit future balloons
2. We only shoot a new arrow when absolutely necessary (when a balloon starts after our last arrow)
3. The total number of arrows is minimized

This approach works because once we've decided to shoot an arrow at a certain position, we never need to reconsider that decision - the greedy choice is always optimal.

Solution Approach

Let's walk through the implementation step by step:

1. Sort the balloons by their end points:

sorted(points, key=lambda x: x[1])

This sorts the points array based on each balloon's ending position (x[1]). This ordering is crucial for the greedy algorithm to work correctly.

2. Initialize tracking variables:

ans, last = 0, -inf

• ans: Counts the number of arrows needed
• last: Tracks the position of the last arrow shot (initialized to negative infinity to ensure the first balloon always requires an arrow)

3. Process each balloon in sorted order:

for a, b in sorted(points, key=lambda x: x[1]):

For each balloon, a represents the start position and b represents the end position.

4. Check if a new arrow is needed:

if a > last:
    ans += 1
    last = b

• If the current balloon's start position a is greater than the last arrow position last, this balloon isn't hit by any previous arrow
• We need a new arrow: increment ans
• Place the new arrow at the current balloon's end position b (update last = b)

Why this works:

• When a > last, there's no overlap between the current balloon and the position of the last arrow
• By placing the arrow at position b (the balloon's end), we ensure:
  • The current balloon is burst
  • Any future balloon that overlaps with position b can also be burst by this arrow
  • We maximize the coverage to the right

Time Complexity: O(n log n) due to sorting, where n is the number of balloons

Space Complexity: O(1) if we don't count the sorting space, as we only use a constant amount of extra variables

The algorithm processes each balloon exactly once after sorting, making it efficient and optimal for this problem.

Example Walkthrough

Let's walk through a concrete example with balloons: [[10,16], [2,8], [1,6], [7,12]]

Step 1: Sort by end points After sorting by end points (second element of each interval):

• [1,6] (ends at 6)
• [2,8] (ends at 8)
• [7,12] (ends at 12)
• [10,16] (ends at 16)

Step 2: Process each balloon

Initialize: ans = 0, last = -∞

Process balloon [1,6]:

• Start position 1 > -∞? Yes
• Need a new arrow!
• Shoot arrow at position 6 (the balloon's end)
• Update: ans = 1, last = 6

Process balloon [2,8]:

• Start position 2 > 6? No (2 ≤ 6)
• This balloon is already hit by the arrow at position 6!
• No new arrow needed
• Keep: ans = 1, last = 6

Process balloon [7,12]:

• Start position 7 > 6? Yes
• Need a new arrow!
• Shoot arrow at position 12 (the balloon's end)
• Update: ans = 2, last = 12

Process balloon [10,16]:

• Start position 10 > 12? No (10 ≤ 12)
• This balloon is already hit by the arrow at position 12!
• No new arrow needed
• Keep: ans = 2, last = 12

Result: We need 2 arrows minimum

• Arrow 1 at position 6: bursts balloons [1,6] and [2,8]
• Arrow 2 at position 12: bursts balloons [7,12] and [10,16]

The key insight: By sorting by end points and placing arrows at the rightmost position of each non-overlapping group, we maximize the number of balloons each arrow can burst.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the number of balloons (length of points array).

• The sorting operation sorted(points, key=lambda x: x[1]) dominates the time complexity, requiring O(n log n) time to sort all intervals by their end points.
• The subsequent for loop iterates through the sorted list once, performing constant-time operations (comparison and assignment) for each element, which takes O(n) time.
• Therefore, the overall time complexity is O(n log n) + O(n) = O(n log n).

Space Complexity: O(n) or O(1) depending on the sorting algorithm implementation.

• The sorted() function in Python creates a new sorted list, which requires O(n) additional space to store the sorted intervals.
• If we consider the space used by the sorting algorithm itself, Python's Timsort typically uses O(n) space in the worst case.
• The variables ans and last use constant space O(1).
• Therefore, the overall space complexity is O(n).

Note: If the code were modified to use points.sort(key=lambda x: x[1]) instead of sorted(), which sorts in-place, the space complexity could be reduced to O(1) auxiliary space (excluding the space needed for the sorting algorithm's internal operations).

Common Pitfalls

1. Sorting by Start Position Instead of End Position

A common mistake is sorting balloons by their start position rather than their end position. This breaks the greedy algorithm's correctness.

Incorrect approach:

sorted_points = sorted(points, key=lambda x: x[0])  # Wrong!

Why it fails: Consider balloons: [[1,6], [2,8], [7,12], [10,16]]

• Sorting by start: [[1,6], [2,8], [7,12], [10,16]]
• After processing [1,6], arrow at position 6
• [2,8] overlaps, no new arrow needed
• [7,12] doesn't overlap with position 6, new arrow at 12
• [10,16] overlaps with 12, no new arrow needed
• Result: 2 arrows

But the optimal solution needs only 2 arrows at positions 6 and 16, which the end-sort approach correctly finds.

Solution: Always sort by end position x[1] to ensure the greedy choice remains optimal.

2. Integer Overflow with Initial Arrow Position

Using a small initial value like 0 or -1 for last_arrow_position can cause incorrect results when balloon coordinates include negative numbers.

Incorrect initialization:

last_arrow_position = 0  # Wrong if balloons can have negative coordinates!

Example failure: For balloons [[-10, -5], [-3, 2]], initializing to 0 would incorrectly assume the first balloon is already burst.

Solution: Use float('-inf') to guarantee the first balloon always requires a new arrow:

last_arrow_position = float('-inf')

3. Incorrect Overlap Check

Using >= instead of > when checking if a new arrow is needed leads to unnecessary arrows.

Incorrect check:

if start >= last_arrow_position:  # Wrong! This shoots unnecessary arrows
    arrow_count += 1

Why it's wrong: If a balloon starts exactly at the last arrow position, that arrow already bursts it. Using >= would shoot an extra unnecessary arrow.

Solution: Use strict inequality:

if start > last_arrow_position:
    arrow_count += 1

4. Not Handling Edge Cases

Forgetting to handle special cases like empty input or single balloon.

Missing edge case handling:

def findMinArrowShots(self, points):
    # Directly sorting without checking
    sorted_points = sorted(points, key=lambda x: x[1])
    # ... rest of code

Solution: Add validation (though most LeetCode problems guarantee non-empty input):

if not points:
    return 0

5. Placing Arrow at Wrong Position

Placing the arrow at the balloon's start position instead of end position reduces the chance of hitting future overlapping balloons.

Suboptimal placement:

if start > last_arrow_position:
    arrow_count += 1
    last_arrow_position = start  # Wrong! Less optimal

Why it matters: Placing the arrow at the end position maximizes the rightward coverage, increasing the probability of bursting future balloons that might overlap.

Solution: Always update to the end position:

last_arrow_position = end