Destroying Asteroids

Medium

Asked by:

29 views

Topics:

ArraysGreedy Algorithms

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 i^th 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.

Example 1:

Input: mass = 10, asteroids = [3,9,19,5,21]
Output: true
Explanation: One way to order the asteroids is [9,19,5,3,21]:
- The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19
- The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38
- The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43
- The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46
- The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67
All asteroids are destroyed.

Example 2:

Input: mass = 5, asteroids = [4,9,23,4]
Output: false
Explanation: 
The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23.
After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22.
This is less than 23, so a collision would not destroy the last asteroid.

Constraints:

1 <= mass <= 10⁵
1 <= asteroids.length <= 10⁵
1 <= asteroids[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the mass of the initial planet and the mass of each asteroid?
Can the mass of the initial planet or any of the asteroids be zero?
Is the order of asteroids in the input array significant, or can I rearrange them?
If it's impossible to destroy all asteroids, what should I return?
Could the input array be empty?

Brute Force Solution

Approach

The brute force approach to destroying asteroids involves trying every single possible order in which you could destroy them. For each order, we check if it's possible to destroy all asteroids with the given mass, and then choose the 'best' order, if one exists.

Here's how the algorithm would work step-by-step:

First, list all possible orderings of the asteroids.
For each of these orderings, simulate destroying the asteroids in that order.
During the simulation, for each asteroid in the current ordering, check if the current mass is large enough to destroy it.
If the mass is not large enough, this ordering is not a solution, so we can move on to the next ordering.
If the mass is large enough, destroy the asteroid and increase the mass.
If you can successfully destroy all asteroids in the ordering, this is a valid solution.
After checking all orderings, if at least one valid solution was found, then it is possible to destroy all asteroids, otherwise it is not.

Code Implementation

def can_destroy_asteroids_brute_force(mass, asteroids):
    import itertools

    asteroid_permutations = list(itertools.permutations(asteroids))

    for asteroid_order in asteroid_permutations:
        current_mass = mass
        can_destroy_all = True

        for asteroid_size in asteroid_order:
            # Check if current mass is enough
            if current_mass < asteroid_size:
                can_destroy_all = False

                break

            # Update mass after destroying asteroid
            current_mass += asteroid_size

        # If the asteroids in this ordering were destroyed, return true
        if can_destroy_all:
            return True

    # If no ordering works, we return false
    return False

Big(O) Analysis

Time Complexity

O(n! * n) – The algorithm iterates through all possible permutations (orderings) of the asteroids. Generating all permutations of n elements takes O(n!) time. For each permutation, we iterate through the asteroids to simulate the destruction process. This simulation involves iterating through each of the n asteroids in the current permutation. Therefore, the overall time complexity is O(n! * n) because for each of the n! permutations, we perform O(n) operations to simulate destroying the asteroids in that specific order. The nested nature of this approach drives the cost.

Space Complexity

O(N!) – The brute force solution generates all possible orderings of the asteroids. Generating all permutations of N asteroids requires storing those permutations. In the worst case, we need to store all N! permutations in memory before checking them. Therefore, the auxiliary space is O(N!).

Optimal Solution

Approach

To successfully destroy all asteroids, we need to sort them and then check if our current mass is sufficient to destroy them in order. The clever part is understanding that if we can't destroy an asteroid, we'll never be able to destroy any that are larger than it.

Here's how the algorithm would work step-by-step:

First, organize the asteroids by size, from smallest to largest.
Start with your initial mass and try to destroy the smallest asteroid first.
If your mass is greater than or equal to the size of the asteroid, you can destroy it. When you destroy it, your mass increases by the asteroid's size.
Move on to the next largest asteroid and repeat the process: check if your current mass is sufficient to destroy it.
If at any point your mass is smaller than the size of an asteroid, you cannot destroy it, and since the asteroids are sorted, you will never be able to destroy any of the remaining asteroids.
If you make it through all the asteroids, you win! Otherwise, you lose.

Code Implementation

def destroying_asteroids(mass, asteroids):
    asteroids.sort()

    current_mass = mass

    for asteroid_size in asteroids:
        # If current mass can't destroy,
        #  it will never be able to destroy larger ones
        if current_mass >= asteroid_size:

            current_mass += asteroid_size

        else:
            return False

    # Return true if all asteroids can be destroyed
    return True

Big(O) Analysis

Time Complexity

O(n log n) – The primary driver of time complexity in this algorithm is the sorting step. Sorting the asteroids array of size n using an efficient algorithm like merge sort or quicksort takes O(n log n) time. The subsequent loop iterates through the sorted asteroids once, performing a constant-time comparison and update for each asteroid. Therefore, the loop itself takes O(n) time. Since O(n log n) dominates O(n), the overall time complexity is O(n log n).

Space Complexity

O(1) – The provided plain English explanation describes sorting the asteroids and iterating through them. While the sorting step itself could potentially use extra space depending on the specific sorting algorithm used, the prompt does not specify the sorting algorithm. Aside from the sorting, the explanation only requires storing a few variables: the current mass and an index to track the current asteroid being considered. The number of variables needed does not depend on the number of asteroids N, thus, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Empty asteroids array	Return true immediately, as there are no asteroids to destroy so the planet trivially succeeds.
Mass is less than or equal to 0	If mass is non-positive, immediately return false because the planet will never grow.
Asteroids array contains very large numbers	Consider using a language with arbitrary precision integers, or explicitly check for and handle integer overflow during mass updates and comparisons to prevent incorrect results.
Asteroids are sorted in descending order and planet's initial mass is small	This will lead to immediate failure as even the first asteroid's mass will be larger than the initial planet mass, causing the algorithm to terminate early.
All asteroids have the same mass, greater than the initial planet's mass	The planet will never grow, so return false.
Large number of asteroids (close to maximum allowed)	Ensure the sorting algorithm used has optimal time complexity (O(n log n)) to avoid exceeding time limits.
The planet can destroy all the asteroids except for the last one due to integer overflow	Use a larger integer type (e.g., long long in C++, long in Java) or check for overflow during mass updates to avoid incorrect comparison.
Asteroids array contains negative numbers	Clarify in the prompt if negative asteroids are valid, and if not, handle them as invalid input (e.g., by throwing an exception or returning an error code).

Empty asteroids array

How to Handle:

Return true immediately, as there are no asteroids to destroy so the planet trivially succeeds.

Mass is less than or equal to 0

How to Handle:

If mass is non-positive, immediately return false because the planet will never grow.

Asteroids array contains very large numbers

How to Handle:

Consider using a language with arbitrary precision integers, or explicitly check for and handle integer overflow during mass updates and comparisons to prevent incorrect results.

Asteroids are sorted in descending order and planet's initial mass is small

How to Handle:

This will lead to immediate failure as even the first asteroid's mass will be larger than the initial planet mass, causing the algorithm to terminate early.

All asteroids have the same mass, greater than the initial planet's mass

How to Handle:

The planet will never grow, so return false.

Large number of asteroids (close to maximum allowed)

How to Handle:

Ensure the sorting algorithm used has optimal time complexity (O(n log n)) to avoid exceeding time limits.

The planet can destroy all the asteroids except for the last one due to integer overflow

How to Handle:

Use a larger integer type (e.g., long long in C++, long in Java) or check for overflow during mass updates to avoid incorrect comparison.

Asteroids array contains negative numbers

How to Handle:

Clarify in the prompt if negative asteroids are valid, and if not, handle them as invalid input (e.g., by throwing an exception or returning an error code).