Leetcode 2126: Destroying Asteroids
You are given a planet with an initial mass. There are asteroids approaching the planet, each with its own mass. The planet can destroy an asteroid if its current mass is greater than or equal to the asteroid’s mass. After destroying an asteroid, the planet’s mass increases by the asteroid’s mass. You need to determine if the planet can destroy all the asteroids by strategically choosing the order of the collisions.
Problem
Approach
Steps
Complexity
Input: You are given an integer representing the planet's mass and an array of integers representing the mass of each asteroid.
Example: mass = 15, asteroids = [7, 4, 9, 3, 2]
Constraints:
• 1 <= mass <= 10^5
• 1 <= asteroids.length <= 10^5
• 1 <= asteroids[i] <= 10^5
Output: Return true if all the asteroids can be destroyed, otherwise return false.
Example: Input: mass = 15, asteroids = [7, 4, 9, 3, 2] Output: true
Constraints:
• The mass of the planet and asteroids is within the specified range.
Goal: To determine if the planet can destroy all the asteroids, we need to check if the planet's mass is sufficient for each asteroid as we go through the list.
Steps:
• Sort the asteroids in ascending order.
• Iterate over each asteroid and check if the planet's current mass is greater than or equal to the asteroid's mass.
• If the planet can destroy the asteroid, increase the planet's mass by the asteroid's mass.
• If at any point the planet cannot destroy an asteroid, return false.
Goal: Ensure that the solution handles large input sizes efficiently.
Steps:
• The number of asteroids can be as large as 10^5.
• The mass of the planet and asteroids can be as large as 10^5.
Assumptions:
• The asteroids are processed in a way that allows the planet to destroy them in the most efficient order.
• Input: Input: mass = 15, asteroids = [7, 4, 9, 3, 2]
• Explanation: The planet starts with a mass of 15. By sorting the asteroids, the planet can destroy them in the order [2, 3, 4, 7, 9]. After destroying all asteroids, the planet's mass will be 15 + 2 + 3 + 4 + 7 + 9 = 40. Since the planet can destroy all asteroids, the output is true.
• Input: Input: mass = 10, asteroids = [4, 9, 8, 6]
• Explanation: The planet starts with a mass of 10. By sorting the asteroids, the planet can destroy them in the order [4, 6, 8]. However, after destroying the asteroid with mass 8, the planet's mass is still only 18, which is not enough to destroy the asteroid with mass 9. Therefore, the output is false.
Approach: To solve this problem, we can first sort the asteroids by mass in ascending order, then iterate through them to check if the planet can destroy each asteroid. If the planet cannot destroy an asteroid, we return false.
Observations:
• Sorting the asteroids allows the planet to destroy the smaller ones first, maximizing its chances of surviving.
• We need to ensure that the planet's mass is always sufficient to destroy the next asteroid.
Steps:
• Sort the asteroids in ascending order.
• Initialize a variable to track the current mass of the planet.
• Iterate over the sorted asteroids. For each asteroid, check if the planet's current mass is greater than or equal to the asteroid's mass.
• If the planet can destroy the asteroid, increase its mass by the asteroid's mass. If not, return false.
• If all asteroids are destroyed, return true.
Empty Inputs:
• If there are no asteroids, return true since there is nothing to destroy.
Large Inputs:
• Ensure that the solution efficiently handles up to 10^5 asteroids.
Special Values:
• If the planet's mass is very small compared to the asteroids, it may not be able to destroy even the smallest asteroid.
Constraints:
• The solution should be able to handle the maximum number of asteroids and mass values.
bool asteroidsDestroyed(int mass, vector<int>& ast) {
sort(ast.begin(), ast.end());
int n = ast.size();
long long mss = mass;
for(int i = 0;i < n; i++) {
if(mss >= ast[i])
mss += ast[i];
else return false;
}
return true;
}
1 : Function Definition
bool asteroidsDestroyed(int mass, vector<int>& ast) {
This line defines the function 'asteroidsDestroyed', which takes an integer 'mass' (the initial mass) and a reference to a vector 'ast' (representing the asteroid sizes) as input. The function returns a boolean indicating whether all asteroids can be destroyed.
2 : Sorting
sort(ast.begin(), ast.end());
This line sorts the asteroid sizes in ascending order, ensuring the spacecraft will destroy the smallest asteroids first, which maximizes the chance of success.
3 : Variable Initialization
int n = ast.size();
This line stores the number of asteroids in the variable 'n', which will be used in the subsequent loop to iterate over all asteroids.
4 : Variable Initialization
long long mss = mass;
This line initializes 'mss' with the spacecraft's initial mass. The variable 'mss' will be updated as asteroids are destroyed.
5 : Loop Start
for(int i = 0;i < n; i++) {
This line starts a loop that iterates over each asteroid in the sorted 'ast' vector.
6 : Check Mass Sufficiency
if(mss >= ast[i])
This line checks if the spacecraft's current mass ('mss') is greater than or equal to the mass of the current asteroid ('ast[i]'). If the mass is sufficient, it proceeds to destroy the asteroid.
7 : Update Mass
mss += ast[i];
This line updates the spacecraft's mass by adding the mass of the destroyed asteroid to 'mss'.
8 : Return False
else return false;
If at any point the spacecraft's mass is insufficient to destroy the asteroid, this line returns false, indicating the spacecraft cannot destroy all asteroids.
9 : Return True
return true;
If the loop completes without returning false, this line returns true, indicating the spacecraft was able to destroy all asteroids.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The sorting step takes O(n log n), and the iteration over the asteroids takes O(n). Thus, the overall time complexity is O(n log n), where n is the number of asteroids.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage required for the sorted list of asteroids, but can be O(1) if sorting is done in-place.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus