We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Destroying Asteroids

Difficulty: Medium

Problem Description

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the ith asteroid. You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed. Return true if all asteroids can be destroyed. Otherwise, return false.

Key Insights

  • The order of collision can be manipulated to maximize the chances of destroying all asteroids.
  • Sorting the asteroids in ascending order allows the planet to tackle the smallest asteroids first, which is a greedy approach.
  • If at any point the planet's mass is less than the mass of the asteroid it encounters, it cannot destroy that asteroid or any subsequent ones.

Space and Time Complexity

Time Complexity: O(n log n) - due to the sorting of the asteroids array.
Space Complexity: O(1) - no additional space is used beyond input storage.

Solution

The problem can be solved using a greedy algorithm. First, we sort the array of asteroids in ascending order. Then, we iterate through the sorted array and check if the planet's mass is sufficient to destroy each asteroid. If it is, we add the mass of that asteroid to the planet's mass. If we encounter an asteroid that the planet cannot destroy, we return false immediately. If we manage to go through all asteroids, we return true.

Code Solutions

def canDestroyAsteroids(mass, asteroids):
    # Sort the asteroids by mass in ascending order
    asteroids.sort()
    
    # Iterate through each asteroid
    for asteroid in asteroids:
        # If the planet's mass is less than the asteroid's mass, return False
        if mass < asteroid:
            return False
        # Otherwise, destroy the asteroid and increase the planet's mass
        mass += asteroid
    
    # If all asteroids are destroyed, return True
    return True
← Back to All Questions