Problem Description

You have a planet with an initial mass and a collection of asteroids with different masses. Your goal is to determine if the planet can destroy all asteroids by colliding with them.

The rules are:

• You can choose to collide with asteroids in any order you want
• When the planet collides with an asteroid:
  • If the planet's mass is greater than or equal to the asteroid's mass: the asteroid is destroyed and the planet absorbs its mass (planet's mass increases by the asteroid's mass)
  • If the planet's mass is less than the asteroid's mass: the planet is destroyed

Given:

• mass: an integer representing the initial mass of the planet
• asteroids: an array of integers where asteroids[i] represents the mass of the i-th asteroid

Return true if it's possible to destroy all asteroids, false otherwise.

The key insight is that since you can choose the collision order, you should collide with smaller asteroids first to grow the planet's mass before tackling larger ones. This is why the solution sorts the asteroids in ascending order and greedily checks if each asteroid can be destroyed. If at any point the planet's mass is less than the current asteroid's mass, the planet would be destroyed and we return false. If we successfully destroy all asteroids, we return true.

Intuition

The key observation is that we have complete freedom to choose the order in which we collide with asteroids. This means we should strategically pick an order that maximizes our chances of success.

Think about it this way: if we encounter a large asteroid early when our planet is still small, we might get destroyed. But if we first collide with smaller asteroids to grow our mass, we might be able to handle that same large asteroid later.

This naturally leads to a greedy strategy: always collide with the smallest available asteroid first. Why does this work?

1. If we can't destroy the smallest asteroid (our mass is less than it), then we definitely can't destroy any larger asteroids either. The game is over.

2. If we can destroy the smallest asteroid, we should do it immediately because:

   • It grows our mass, making us stronger for future collisions
   • There's no benefit to delaying this collision - we'll need to destroy it eventually anyway
   • By growing our mass as early as possible, we maximize our chances of handling larger asteroids later

This is why sorting the asteroids in ascending order and processing them one by one works perfectly. At each step, we're facing the smallest remaining asteroid. If we can't handle it, we know it's impossible to destroy all asteroids. If we can handle it, we absorb its mass and move on to the next smallest asteroid.

The beauty of this approach is that it's both optimal and simple - by always choosing the easiest target first and growing stronger, we give ourselves the best chance of completing the mission.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a straightforward sorting + greedy strategy:

1. Sort the asteroids array in ascending order: We use asteroids.sort() to arrange all asteroids from smallest to largest mass. This ensures we always encounter asteroids in the optimal order.

2. Iterate through the sorted asteroids: We process each asteroid one by one using a simple for loop: for x in asteroids:

3. Check if the planet can destroy the current asteroid: At each step, we compare the planet's current mass with the asteroid's mass:

   • If mass < x: The planet cannot destroy this asteroid and will be destroyed instead. We immediately return False since it's impossible to destroy all asteroids.
   • If mass >= x: The planet successfully destroys the asteroid.

4. Update the planet's mass: When an asteroid is destroyed, the planet absorbs its mass: mass += x. This makes the planet stronger for subsequent collisions.

5. Return the final result: If we successfully iterate through all asteroids without returning False, it means all asteroids have been destroyed, so we return True.

The algorithm has a time complexity of O(n log n) due to the sorting step, where n is the number of asteroids. The space complexity is O(1) if we don't count the sorting space (or O(n) if we do, depending on the sorting algorithm used).

The elegance of this solution lies in its simplicity - by sorting first and then greedily consuming asteroids from smallest to largest, we guarantee the optimal outcome with minimal code.

Example Walkthrough

Let's walk through an example where we have a planet with initial mass 5 and asteroids with masses [4, 9, 23, 4, 1].

Step 1: Sort the asteroids in ascending order

• Original: [4, 9, 23, 4, 1]
• Sorted: [1, 4, 4, 9, 23]

Step 2: Process each asteroid from smallest to largest

Collision 1: Planet (mass=5) vs Asteroid (mass=1)

• Since 5 ≥ 1, the asteroid is destroyed
• Planet absorbs the mass: 5 + 1 = 6
• New planet mass: 6

Collision 2: Planet (mass=6) vs Asteroid (mass=4)

• Since 6 ≥ 4, the asteroid is destroyed
• Planet absorbs the mass: 6 + 4 = 10
• New planet mass: 10

Collision 3: Planet (mass=10) vs Asteroid (mass=4)

• Since 10 ≥ 4, the asteroid is destroyed
• Planet absorbs the mass: 10 + 4 = 14
• New planet mass: 14

Collision 4: Planet (mass=14) vs Asteroid (mass=9)

• Since 14 ≥ 9, the asteroid is destroyed
• Planet absorbs the mass: 14 + 9 = 23
• New planet mass: 23

Collision 5: Planet (mass=23) vs Asteroid (mass=23)

• Since 23 ≥ 23, the asteroid is destroyed
• Planet absorbs the mass: 23 + 23 = 46
• Final planet mass: 46

Result: All asteroids destroyed successfully, return True

Notice how by tackling the smaller asteroids first, we built up enough mass to handle the larger ones. If we had tried to collide with the asteroid of mass 23 first (when our planet only had mass 5), we would have been destroyed immediately!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The dominant operation in this code is the asteroids.sort() call, which uses Python's Timsort algorithm with a time complexity of O(n × log n) where n is the number of asteroids. After sorting, the code iterates through the sorted array once with a for loop, which takes O(n) time. Since O(n × log n) + O(n) = O(n × log n), the overall time complexity is O(n × log n).

Space Complexity: O(log n)

Python's built-in sort() method sorts the list in-place and uses Timsort algorithm. While the sorting is done in-place (modifying the original list), Timsort requires O(log n) auxiliary space for its merge operations and maintaining the stack of pending runs during the sorting process. The rest of the code uses only O(1) additional space for the loop variable and comparisons. Therefore, the overall space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow Issues

One critical pitfall that's often overlooked is the potential for integer overflow when accumulating the planet's mass. As the planet absorbs asteroid masses, the total mass can grow exponentially and potentially exceed the maximum integer value in some programming languages.

The Problem:

# This could cause issues with very large numbers
mass += asteroid_mass  # What if this exceeds max integer?

Example scenario:

• Initial mass: 10^9
• Asteroids: [10^9, 10^9, 10^9, ...]
• After absorbing several asteroids, the mass could exceed typical integer limits

Solutions:

1. Use appropriate data types:

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        # Python handles arbitrary precision integers automatically
        # But in other languages, you might need:
        # - Use long long in C++
        # - Use BigInteger in Java
        # - Check for overflow conditions explicitly
      
        asteroids.sort()
      
        for asteroid_mass in asteroids:
            if mass < asteroid_mass:
                return False
          
            # In Python, this is safe, but consider overflow in other languages
            mass += asteroid_mass
          
        return True

2. Early termination optimization:

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        asteroids.sort()
      
        # Track the sum of all asteroids we've destroyed
        total_absorbed = 0
      
        for asteroid_mass in asteroids:
            if mass + total_absorbed < asteroid_mass:
                return False
          
            total_absorbed += asteroid_mass
          
            # Optional: Early termination if we've grown large enough
            # to destroy any remaining asteroid
            if mass + total_absorbed >= sum(asteroids):
                return True
              
        return True

2. Modifying Input Array In-Place

Another pitfall is sorting the input array in-place, which modifies the original data structure. This could be problematic if the caller expects the array to remain unchanged.

The Problem:

asteroids.sort()  # This modifies the original array!

Solution - Create a copy:

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        # Create a copy to avoid modifying the original array
        sorted_asteroids = sorted(asteroids)  # Creates a new sorted list
      
        for asteroid_mass in sorted_asteroids:
            if mass < asteroid_mass:
                return False
            mass += asteroid_mass
          
        return True

3. Not Considering Edge Cases

Missing edge case checks:

class Solution:
    def asteroidsDestroyed(self, mass: int, asteroids: List[int]) -> bool:
        # Add edge case handling
        if not asteroids:  # Empty asteroid list
            return True
          
        if mass <= 0:  # Invalid initial mass
            return False if asteroids else True
          
        asteroids.sort()
      
        for asteroid_mass in asteroids:
            if mass < asteroid_mass:
                return False
            mass += asteroid_mass
          
        return True

These pitfalls highlight the importance of considering numerical limits, data integrity, and edge cases even in seemingly straightforward greedy algorithms.