Can a Growing Planet Absorb Every Asteroid?
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
A planet starts with mass `mass`, and `asteroids[i]` is the mass of one asteroid. You may choose their collision order. The planet can absorb an asteroid when its current mass is at least the asteroid's mass, gaining that mass afterward. If its mass is smaller, the planet is destroyed. Return whether some order lets the planet absorb every asteroid.
```cpp
class Solution {
public:
bool asteroidsDestroyed(int mass, vector<int>& asteroids);
};
```
### Examples
**Example 1:**
```text
mass = 3, asteroids = [6,2,3]
Output: true
Explanation: Absorb 2, then 3, then 6; masses become 5,8,14.
```
**Example 2:**
```text
mass = 2, asteroids = [3,1,8]
Output: false
Explanation: After absorbing 1 and 3 the planet reaches only 6, below 8.
```
### Constraints
- `1 <= mass <= 10^5`.
- `1 <= asteroids.length <= 10^5`; each asteroid mass lies in `[1,10^5]`.
### Clarifying Questions
Equality is sufficient for absorption. The answer is Boolean, even though several collision orders can work.
```hint Inspect the structure
If the smallest remaining asteroid is too large, can another remaining asteroid help first?
```
### Reasoning checkpoints
- Respect the current mass at each collision, including the equality case.
- Prove that a successful answer has a feasible order and that a failure rules out every order.
- Represent the accumulated mass safely for the maximum number and size of asteroids.
### Optional extensions
Can the bounded range of asteroid masses improve the running time?
Overview: Can a Growing Planet Absorb Every Asteroid?. A planet starts with mass. You may choose the asteroid collision order. A collision succeeds when the current planet mass is at least the asteroid mass, after which that asteroid's mass is added to the planet. Otherwise the planet is destroyed. Return whether all asteroids can be absorbed.