LeetCode 452: Minimum Number of Arrows to Burst Balloons Solution in Python – A Step-by-Step Guide

What Is LeetCode 452: Minimum Number of Arrows to Burst Balloons?

In LeetCode 452: Minimum Number of Arrows to Burst Balloons, you’re given a list of balloons as intervals points, where each balloon is [x_start, x_end] at some y-height (y is irrelevant for the shot). An arrow fired at x bursts all balloons overlapping that x-coordinate. Your task is to find the minimum number of arrows needed to burst all balloons. For example, with [[10,16], [2,8], [1,6], [7,12]], two arrows suffice by shooting at overlapping regions. It’s like plotting the perfect shots to clear the sky with minimal effort.

Problem Statement

• Input: points (List[List[int]])—list of [x_start, x_end] intervals.
• Output: int—minimum arrows to burst all balloons.
• Rules:
• Arrow at x bursts balloons where x_start ≤ x ≤ x_end.
• Minimize total arrows.

Constraints

• 1 <= points.length <= 10^5.
• points[i].length == 2.
• -2^31 <= x_start < x_end <= 2^31 - 1.

Examples to Get Us Started

• Input: points = [[10,16],[2,8],[1,6],[7,12]]
• Output: 2 (Arrows at x=6 and x=12).
• Input: points = [[1,2],[3,4],[5,6],[7,8]]
• Output: 4 (No overlaps, 4 arrows).
• Input: points = [[1,2],[2,3],[3,4],[4,5]]
• Output: 2 (Arrows at x=2 and x=4).

Understanding the Problem: Aiming for Efficiency

To solve LeetCode 452: Minimum Number of Arrows to Burst Balloons in Python, we need to minimize arrows by maximizing overlaps—each arrow should burst as many balloons as possible at one x-coordinate. This is an interval scheduling problem: find the fewest points to intersect all intervals. A brute force approach—trying all x-coordinates—is impractical. Instead, a greedy strategy works wonders. We’ll explore:

• Best Solution (Greedy, Sort by End): O(n log n) time, O(1) space—optimal and elegant.
• Alternative Solution (Greedy, Sort by Start): O(n log n) time, O(1) space—intuitive but less efficient.

Let’s dive into the sort-by-end solution—it’s the archer’s bullseye we need.

Best Solution: Greedy with Sorting by End Coordinates

Why This Is the Best Solution

The greedy approach sorting by end coordinates is the top pick because it’s O(n log n) time and O(1) space (excluding sorting space), guaranteeing the minimum arrows by always choosing the earliest possible shot to burst overlapping balloons. It sorts by x_end, then greedily shoots at each end point unless overlapped by prior shots. It’s like aiming at the tightest deadlines first, catching as many balloons as possible per arrow—smart and precise!

How It Works

Here’s the strategy:

• Step 1: Sort intervals by x_end (if ties, x_start doesn’t matter much here).
• Step 2: Initialize arrows = 1, first end as shot point.
• Step 3: Iterate sorted intervals:
• If x_start > previous end, new arrow needed, update end.
• If overlap (x_start ≤ prev_end), same arrow works.
• Step 4: Return total arrows.
• Why It Works:
• Earliest end forces minimal shots.
• Overlaps are maximized per arrow.

Step-by-Step Example

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

• Sort by End: [[1,6], [2,8], [7,12], [10,16]].
• Process:
• [1,6]: arrows = 1, prev_end = 6 (shoot at 6).
• [2,8]: 2 ≤ 6, overlaps, arrows = 1, prev_end = 6.
• [7,12]: 7 > 6, new arrow, arrows = 2, prev_end = 12.
• [10,16]: 10 ≤ 12, overlaps, arrows = 2, prev_end = 12.
• Result: 2 arrows.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0

        # Step 1: Sort by end coordinate
        points.sort(key=lambda x: x[1])

        # Step 2: Initialize with first balloon
        arrows = 1
        prev_end = points[0][1]

        # Step 3: Process remaining balloons
        for i in range(1, len(points)):
            x_start, x_end = points[i]
            if x_start > prev_end:
                # New arrow needed
                arrows += 1
                prev_end = x_end

        return arrows

• Line 3-4: Handle empty list.
• Line 7: Sort by x_end (e.g., [[1,6], [2,8], …]).
• Line 10-11: Start with 1 arrow at first end.
• Line 14-17: Iterate:
• If x_start > prev_end, new shot, update end.
• If overlap, same arrow suffices.
• Line 19: Return total.
• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(1)—no extra space.

It’s like an archer’s perfect shot planner!

Alternative Solution: Greedy with Sorting by Start Coordinates

Why an Alternative Approach?

The greedy approach sorting by start coordinates also runs in O(n log n) time and O(1) space, but it’s less optimal as it may require tracking more intervals before shooting. It sorts by x_start, merging overlaps from the left. It’s like aiming at the earliest starts, adjusting as you go—intuitive but less efficient for minimal shots.

How It Works

• Step 1: Sort by x_start.
• Step 2: Process intervals:
• If no overlap with prev, new arrow.
• If overlap, update current end to min of ends.
• Step 3: Return arrows.

Step-by-Step Example

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

• Sort by Start: [[1,6], [2,8], [7,12], [10,16]].
• Process:
• [1,6]: arrows = 1, curr_end = 6.
• [2,8]: 2 ≤ 6, curr_end = min(6, 8) = 6.
• [7,12]: 7 > 6, arrows = 2, curr_end = 12.
• [10,16]: 10 ≤ 12, curr_end = 12.
• Result: 2 arrows.

Code for Start-Sort Approach

Copy codeclass Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0

        # Sort by start
        points.sort(key=lambda x: x[0])

        arrows = 1
        curr_end = points[0][1]

        for i in range(1, len(points)):
            x_start, x_end = points[i]
            if x_start > curr_end:
                arrows += 1
                curr_end = x_end
            else:
                curr_end = min(curr_end, x_end)

        return arrows

• Time Complexity: O(n log n)—sorting.
• Space Complexity: O(1)—minimal space.

It’s a left-to-right arrow aimer!

Comparing the Two Solutions

• Sort by End (Best):
• Pros: O(n log n), O(1), optimal shots.
• Cons: Less intuitive initially.
• Sort by Start (Alternative):
• Pros: O(n log n), O(1), natural flow.
• Cons: May overestimate arrows.

End-sort wins for minimality.

Edge Cases and More Examples

• Input: [] → 0.
• Input: [[1,2]] → 1.
• Input: [[1,5],[2,3]] → 1.

End-sort handles all perfectly.

Complexity Recap

• End-Sort: Time O(n log n), Space O(1).
• Start-Sort: Time O(n log n), Space O(1).

End-sort’s the champ.

Key Takeaways

• End-Sort: Greedy precision.
• Start-Sort: Greedy intuition.
• Python Tip: Greedy rocks intervals—see [Python Basics](/python/basics).

Final Thoughts: Burst Those Balloons

LeetCode 452: Minimum Number of Arrows to Burst Balloons in Python is a greedy archer’s delight. Sorting by end coordinates is your sharpshooter, while start-sorting offers a steady aim. Want more greedy fun? Try LeetCode 435: Non-overlapping Intervals or LeetCode 646: Maximum Length of Pair Chain. Ready to fire some arrows? Head to Solve LeetCode 452 on LeetCode and take aim today—your coding skills are right on target!