Destroying Asteroids

Destroying Asteroids

What is this problem about?

In the Destroying Asteroids coding problem, you are given an initial mass of a planet and an array of integers representing the masses of various asteroids. If the planet's mass is greater than or equal to an asteroid's mass, the planet can destroy it and absorb its mass. You need to determine if it's possible to destroy all the asteroids in any order.

Why is this asked in interviews?

Amazon and Google use this problem to evaluate a candidate's ability to identify optimal strategies. It's a classic example of a problem where a specific ordering of operations leads to the best outcome. It tests your proficiency with the greedy interview pattern and your understanding of how cumulative sums behave.

Algorithmic pattern used

This problem is solved using a Greedy approach combined with Sorting. The optimal strategy is to always destroy the smallest possible asteroid first. By doing this, you increase the planet's mass as quickly as possible with the "easiest" targets, giving you the best chance to destroy larger asteroids later.

1. Sort the asteroids array in ascending order.
2. Iterate through the sorted array.
3. If the current mass is $\ge$ the asteroid mass, add the asteroid's mass to the planet's mass.
4. If at any point the current mass is $<$ the asteroid mass, return false.

Example explanation

Planet mass: 10, Asteroids: [5, 20, 10].

1. Sort asteroids: [5, 10, 20].
2. Destroy 5: $10 \ge 5$. New mass: $10 + 5 = 15$.
3. Destroy 10: $15 \ge 10$. New mass: $15 + 10 = 25$.
4. Destroy 20: $25 \ge 20$. New mass: $25 + 20 = 45$. Result: true.

Common mistakes candidates make

• No Sorting: Trying to use a complex search or backtracking to find the right order, which is $O(N!)$ and unnecessary.
• Integer Overflow: Forgetting that the planet's mass can grow very large and exceed the limits of a 32-bit integer. Always use long for the cumulative mass.
• Early Exit: Returning true too early before checking all asteroids.

Interview preparation tip

Whenever a problem involves "accumulating power" to overcome "obstacles," always consider if sorting the obstacles from smallest to largest works. This greedy strategy is a recurring theme in competitive programming.