Asteroid Collision
Problem Description
We are given an array asteroids of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.
Examples:
Input: asteroids = [5,10,-5].
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.
Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.
Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.
Constraints:
- 2 <= asteroids.length <= 10⁴
- -1000 <= asteroids[i] <= 1000
- asteroids[i] != 0
Brute Force Approach
Okay! What comes to mind after understanding the problem?
As mentioned in the problem description, we know that positive numbers won't collide with other positive numbers, and negative numbers won't collide with other negative numbers.
In other words, numbers of the same parity (both positive or both negative) never collide.
Now, let's break this down further: if the numbers in the array are all of the same parity, we simply take them as they are and add them to the result—there’s nothing special we need to do. However, when a number with different parity shows up, we need to perform some actions to manage potential collisions.
So, let’s say we’re processing the array and start encountering positive numbers. As we traverse the array, we add these positive numbers to our result directly since they won’t interfere with each other. However, when we hit a negative number, that’s when we need to backtrack a bit.
At this point, we go back to the result (which would have positive numbers by now) and start eliminating them based on the following conditions:
- If the absolute value of the negative number is greater than the positive number, it means the negative number would eliminate the positive one. So, we set that positive number to zero and keep checking the next one. We continue this process as long as the conditions hold or the array becomes empty.
- If the absolute value of the negative number is equal to the positive number, both numbers cancel each other out. In this case, we eliminate both by setting the positive number to zero and then continue processing the array further.
- If the absolute value of the negative number is smaller than the positive number, it means the negative number isn’t strong enough to eliminate the positive one. So, in this case, we just move forward and skip that negative number.
Finally, if the result is empty, we add the current number—whether it’s positive or negative—since it won’t collide with anything at that point.
Once you've processed all numbers, traverse the result array again and construct the final result by keeping only the non-zero elements.
Let's understand with example:
Let's dry run this approach with the array:
[3, 5, −3, 4, −5, 2, −2]
First Pass (Processing numbers):
- 3: Positive, add to result → 3
- 5: Positive, add to result → 3,5
- -3: Negative:
- Compare with 5 (absolute value 3 < 5), skip.
- 4: Positive, add to result → 3,5,0,4
- -5: Negative:
- Compare with 4 (absolute value 5 > 4), set 4 to 0 -> 3, 5, 0, 0.
- Compare with 5 (absolute value 5 == 5), set 5 to 0 and skip → 3, 0, 0, 0, 0
- 2: Positive, add to result → 3, 0, 0, 0, 0, 2
- -2: Negative:
- Compare with 2 (absolute value 2 == 2), set both to 0 → 3, 0, 0, 0, 0, 0, 0
Second Pass (Remove zeroes):
Final result → 3
Conclusion:
After handling all collisions, the remaining array is [3].
Let's understand with visuals
How to implement it in code:
- Traverse the array:
- For each positive number, add it to the result as it is.
- Handle negative numbers:
- When encountering a negative number, backtrack through the result:
- Eliminate smaller positives: If the absolute value of the negative number is greater than the positive number, set the positive number to 0 and continue checking.
- Cancel equal values: If the absolute value equals the positive number, set both the positive number and the negative number to 0.
- Skip smaller negatives: If the absolute value of the negative number is smaller than the positive number, skip the negative number and move on.
- Final check: If the result becomes empty or contains no positive numbers, add the negative number since there's nothing to collide with.
- Second pass:
- Once you've processed all numbers, traverse the result array again and construct the final result by keeping only the non-zero elements.
This approach ensures we handle collisions by setting eliminated numbers to 0, then filter out the 0's in a second pass.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
int n = asteroids.size();
// Initialize the result vector with 0s. It will store the status of asteroids (either 0 or their values).
vector<int> result(n, 0);
// Traverse the array and process each number
for (int i = 0; i < n; i++) {
int num = asteroids[i];
// If the current number is positive or if it's the first asteroid, add it directly to the result
if (num > 0 || i == 0)
{
result[i] = num;
} else {
// If the current asteroid is negative, check for collisions with previous asteroids
for (int j = i - 1; j >= 0; j--) {
// If the asteroid in result is negative, it means there is no collision; the negative asteroid survives
if (result[j] < 0) {
result[i] = num;
break;
}
// If both asteroids have the same absolute value, they cancel each other out
if (result[j] == abs(num)) {
result[j] = 0;
result[i] = 0;
break;
}
// If the absolute value of the positive asteroid is smaller than the current negative asteroid,
// eliminate the positive asteroid and continue the process
else if (result[j] < abs(num)) {
result[j] = 0;
result[i] = num;
} else {
result[i] = 0;
// Break out of the loop as no further collision happens
break;
}
}
}
}
// Second pass to remove 0's, which are placeholders for asteroids that have been eliminated
vector<int> finalResult;
for (int num : result) {
// Only push non-zero values into final result
if (num != 0) {
finalResult.push_back(num);
}
}
return finalResult;
}
};2. Java Try on Compiler
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int n = asteroids.length;
// Initialize the result array with 0s. It will store the status of asteroids (either 0 or their values).
int[] result = new int[n];
// Traverse the array and process each number
for (int i = 0; i < n; i++) {
int num = asteroids[i];
// If the current number is positive or if it's the first asteroid, add it directly to the result
if (num > 0 || i == 0) {
result[i] = num;
} else {
// If the current asteroid is negative, check for collisions with previous asteroids
for (int j = i - 1; j >= 0; j--) {
// If the asteroid in result is negative, it means there is no collision; the negative asteroid survives
if (result[j] < 0) {
result[i] = num;
break;
}
// If both asteroids have the same absolute value, they cancel each other out
if (result[j] == Math.abs(num)) {
result[j] = 0;
result[i] = 0;
break;
}
// If the absolute value of the positive asteroid is smaller than the current negative asteroid,
// eliminate the positive asteroid and continue the process
else if (result[j] < Math.abs(num)) {
result[j] = 0;
result[i] = num;
} else {
result[i] = 0;
// Break out of the loop as no further collision happens
break;
}
}
}
}
// Second pass to remove 0's, which are placeholders for asteroids that have been eliminated
ArrayList<Integer> finalResult = new ArrayList<>();
for (int num : result) {
// Only add non-zero values into final result
if (num != 0) {
finalResult.add(num);
}
}
// Convert finalResult to an array and return
int[] finalArray = new int[finalResult.size()];
for (int i = 0; i < finalResult.size(); i++) {
finalArray[i] = finalResult.get(i);
}
return finalArray;
}
}
3. Python Try on Compiler
class Solution:
def asteroidCollision(self, asteroids):
n = len(asteroids)
# Initialize the result vector with 0s. It will store the status of asteroids (either 0 or their values).
result = [0] * n
# Traverse the array and process each number
for i in range(n):
num = asteroids[i]
# If the current number is positive or if it's the first asteroid, add it directly to the result
if num > 0 or i == 0:
result[i] = num
else:
# If the current asteroid is negative, check for collisions with previous asteroids
for j in range(i - 1, -1, -1):
# If the asteroid in result is negative, it means there is no collision; the negative asteroid survives
if result[j] < 0:
result[i] = num
break
# If both asteroids have the same absolute value, they cancel each other out
if result[j] == abs(num):
result[j] = 0
result[i] = 0
break
# If the absolute value of the positive asteroid is smaller than the current negative asteroid,
# eliminate the positive asteroid and continue the process
elif result[j] < abs(num):
result[j] = 0
result[i] = num
else:
result[i] = 0
# Break out of the loop as no further collision happens
break
# Second pass to remove 0's, which are placeholders for asteroids that have been eliminated
final_result = [num for num in result if num != 0]
return final_result
4. Javascript Try on Compiler
var asteroidCollision = function (asteroids) {
const n = asteroids.length;
// Initialize the result array with 0s. It will store the status of asteroids (either 0 or their values).
const result = new Array(n).fill(0);
// Traverse the array and process each number
for (let i = 0; i < n; i++) {
const num = asteroids[i];
// If the current number is positive or if it's the first asteroid, add it directly to the result
if (num > 0 || i === 0) {
result[i] = num;
} else {
// If the current asteroid is negative, check for collisions with previous asteroids
for (let j = i - 1; j >= 0; j--) {
// If the asteroid in result is negative, it means there is no collision; the negative asteroid survives
if (result[j] < 0) {
result[i] = num;
break;
}
// If both asteroids have the same absolute value, they cancel each other out
if (result[j] === Math.abs(num)) {
result[j] = 0;
result[i] = 0;
break;
}
// If the absolute value of the positive asteroid is smaller than the current negative asteroid,
// eliminate the positive asteroid and continue the process
else if (result[j] < Math.abs(num)) {
result[j] = 0;
result[i] = num;
} else {
result[i] = 0;
// Break out of the loop as no further collision happens
break;
}
}
}
}
// Second pass to remove 0's, which are placeholders for asteroids that have been eliminated
const finalResult = [];
for (let num of result) {
if (num !== 0) {
finalResult.push(num);
}
}
return finalResult;
};Time Complexity: O(n²)
The algorithm processes each asteroid in the input array by iterating through it. The outer loop runs once for each asteroid, so it iterates n times, where n is the length of the asteroids array.
For each negative asteroid, the algorithm may need to backtrack through the result array, starting from the current index i and moving backwards. In the worst-case scenario, for each negative asteroid, the algorithm might have to check all previous asteroids. This means that the inner loop could run O(n) times for each negative asteroid.
To better understand the time complexity, let's consider the inner loop's behavior. As the inner loop traverses from 0 to n, for each iteration i of the outer loop, the inner loop could go up to i-1 times. Mathematically, this can be represented as:
0 + 1 + 2 + 3 + ... + (n-1).
This is the sum of the first n-1 terms, which is equivalent to: n(n−1)/2
In Big-O notation, we focus on the term that grows the fastest as n increases, and we ignore constant factors and lower-order terms. Therefore, we express the time complexity as: O(n(n−1)/2)≈O(n²)
So, the total time complexity in the worst case is O(n²), because, for each of the n asteroids, the collision check might take O(n) time.
After processing all asteroids, there's a second pass through the result array to remove the zeros, which represent eliminated asteroids. This second loop takes O(n) time because we're simply iterating over the result array once.
Combining the worst-case scenario of the inner loop and the second pass, the overall time complexity is O(n²).
Thus, the algorithm has a O(n²) time complexity in the worst case, primarily due to the collision checks that may require backtracking through previous asteroids, especially when many of them are negative.
Space Complexity: O(n)
- Auxiliary Space: O(n)
Explanation: We use a new array, result, to store all the asteroids after collision. In the worst case, this array can hold n elements (where n is the number of asteroids), so the auxiliary space for this array is O(n).
We also use the finalResult array, which again can hold up to n asteroids in the worst case. Therefore, the auxiliary space for this array is also O(n). - Total Space Complexity: O(n)
Explanation: The total space complexity is the space used by the result and finalResult arrays, which are both O(n) in the worst case.
Hence, the total space complexity is O(n).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is suitable for n ≤ 10⁴. This means that for each test case where the number of asteroids (n) is at most 10⁴, the solution should execute within the given time limits.
Since O(n²) results in a maximum of 10⁸ operations (for n = 10⁴), the solution is expected to work well for individual test cases under these constraints, typically allowing around 1–2 seconds for execution.
In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning for n ≤ 10⁴, the solution is efficient enough. However, when multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10⁸ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can there be a better approach?
Yes! There is a better approach to solve this problem.
Curious?
Currently, the algorithm backtracks for each negative asteroid, checking all the previous asteroids in the result array. This increases the time complexity, as we might end up comparing every asteroid with all the preceding ones.
But here's an idea:
Instead of checking every asteroid before the current one, we can optimize by only looking at the relevant asteroids that could possibly collide with the current one.
This means, we don’t need to backtrack over all elements but just focus on the ones that might actually interact with the current asteroid. Once a collision is resolved or no further interaction is possible, we can stop checking earlier asteroids.
How can we do this efficiently?
Rather than storing all elements in the result array (including eliminated ones), we can use a more targeted approach. We only store the relevant elements—those that are still in play and haven't been eliminated.
This way, we eliminate unnecessary comparisons, and when a collision happens, we only check against the relevant asteroids, instead of checking every one before the current asteroid.
By keeping track of only the relevant asteroids in a more controlled data structure, we ensure that each asteroid is processed only twice—once when it's added to the result and once when it might collide. This prevents redundant checks and significantly reduces space complexity, while also improving efficiency.
As we need a data structure that will only hold the relevant asteroids still in play as we traverse the array, and we also need to eliminate those in reverse order when necessary, which data structure can be useful here?
Yes, you're right! We can use a stack to store the last elements and optimally remove them in reverse order whenever a negative asteroid comes.
What is a stack?
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. You can think of it like a stack of plates where you add and remove plates from the top.
Using the stack ensures we only backtrack as needed and avoid unnecessary checks, leading to a much more efficient solution.
This approach allows us to backtrack on a minimal set of elements rather than the entire array, improving both time and space complexity.
How can we do it?
We iterate through the array of asteroids.
- If it's positive, we simply push it onto the stack because it is moving to the right and will not collide with any asteroids already in the stack (which are also moving right).
- If it's negative, we need to check for potential collisions with the asteroids in the stack:
- We compare the top of the stack (which represents the most recent asteroid).
- If the top of the stack is negative (or the stack is empty), the negative asteroid simply moves forward, so we push it onto the stack.
- If the absolute value of the negative asteroid is equal, both asteroids are destroyed (pop the stack), and we stop checking for further collisions for this asteroid.
- If the top of the stack is positive (moving right), a collision can happen, so we compare their sizes:
- If the absolute value of the negative asteroid is greater, the positive asteroid is destroyed (pop the stack), and we continue checking the next asteroid in the stack (if any).
- If the absolute value of the negative asteroid is smaller, the negative asteroid is destroyed, and we stop the process for this asteroid.
- Once we process all asteroids, the stack will contain the asteroids that survived.
Let's understand with an example:
Input: asteroids = [5, 10, -5]
- Stack: [] (initially empty)
- Asteroid 5:
- Positive, moving right → push to stack.
- Stack: [5]
- Asteroid 10:
- Positive, moving right → push to stack.
- Stack: [5, 10]
- Asteroid -5:
- Negative, moving left → check for collision with top of stack (10).
- abs(-5) < abs(10) → -5 is destroyed, no changes to the stack.
- Stack: [5, 10]
Final Stack: [5, 10]
- Surviving asteroids: [5, 10]
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
// Stack to store the surviving asteroids
stack<int> asteroidStack;
// Traverse through each asteroid in the input array
for(auto &asteroid: asteroids)
{
// If the current asteroid is moving right (positive), push it onto the stack
if(asteroid > 0)
asteroidStack.push(asteroid);
else
{
// If the asteroid is moving left (negative), check for collisions
while(asteroidStack.empty() || asteroidStack.top() < 0 || abs(asteroid) >= asteroidStack.top())
{
// If the stack is empty or the top of the stack is negative, push the negative asteroid
if(asteroidStack.empty() || asteroidStack.top() < 0)
{
asteroidStack.push(asteroid);
break;
}
// If the sizes are equal, both asteroids are destroyed (pop the stack)
else if(asteroidStack.top() == abs(asteroid))
{
asteroidStack.pop();
break;
}
// If the negative asteroid is larger, destroy the top asteroid and continue
else
asteroidStack.pop();
}
}
}
// Prepare the final result array with surviving asteroids
vector<int> result;
while(!asteroidStack.empty())
{
result.push_back(asteroidStack.top());
asteroidStack.pop();
}
// Reverse the result to maintain the correct order
reverse(result.begin(), result.end());
return result;
}
};
2. Java Try on Compiler
class Solution {
public int[] asteroidCollision(int[] asteroids) {
// Stack to store the surviving asteroids
Stack<Integer> asteroidStack = new Stack<>();
// Traverse through each asteroid in the input array
for (int asteroid : asteroids) {
// If the current asteroid is moving right (positive), push it onto the stack
if (asteroid > 0) {
asteroidStack.push(asteroid);
} else {
// If the asteroid is moving left (negative), check for collisions
while (asteroidStack.isEmpty() || (asteroidStack.peek() < 0 || Math.abs(asteroid) >= asteroidStack.peek())) {
// If the stack is empty or the top of the stack is negative, push the negative asteroid
if (asteroidStack.isEmpty() || asteroidStack.peek() < 0) {
asteroidStack.push(asteroid);
break;
}
// If the sizes are equal, both asteroids are destroyed (pop the stack)
else if (asteroidStack.peek() == Math.abs(asteroid)) {
asteroidStack.pop();
break;
}
// If the negative asteroid is larger, destroy the top asteroid and continue
else {
asteroidStack.pop();
}
}
}
}
// Prepare the final result array with surviving asteroids
int[] result = new int[asteroidStack.size()];
for (int i = asteroidStack.size() - 1; i >= 0; i--) {
result[i] = asteroidStack.pop();
}
return result;
}
}3. Python Try on Compiler
class Solution(object):
def asteroidCollision(self, asteroids):
# Stack to store the surviving asteroids
asteroid_stack = []
# Traverse through each asteroid in the input array
for asteroid in asteroids:
# If the current asteroid is moving right (positive), push it onto the stack
if asteroid > 0:
asteroid_stack.append(asteroid)
else:
# If the asteroid is moving left (negative), check for collisions
while not asteroid_stack or (asteroid_stack[-1] < 0 or abs(asteroid) >= asteroid_stack[-1]):
# If the stack is empty or the top of the stack is negative, push the negative asteroid
if not asteroid_stack or asteroid_stack[-1] < 0:
asteroid_stack.append(asteroid)
break
# If the sizes are equal, both asteroids are destroyed (pop the stack)
elif asteroid_stack[-1] == abs(asteroid):
asteroid_stack.pop()
break
# If the negative asteroid is larger, destroy the top asteroid and continue
else:
asteroid_stack.pop()
return asteroid_stack
4. Javascript Try on Compiler
var asteroidCollision = function(asteroids) {
// Stack to store the surviving asteroids
let asteroidStack = [];
// Traverse through each asteroid in the input array
for (let asteroid of asteroids) {
// If the current asteroid is moving right (positive), push it onto the stack
if (asteroid > 0) {
asteroidStack.push(asteroid);
} else {
// If the asteroid is moving left (negative), check for collisions
while (!asteroidStack.length || (asteroidStack[asteroidStack.length - 1] < 0 || Math.abs(asteroid) >= asteroidStack[asteroidStack.length - 1])) {
// If the stack is empty or the top of the stack is negative, push the negative asteroid
if (!asteroidStack.length || asteroidStack[asteroidStack.length - 1] < 0) {
asteroidStack.push(asteroid);
break;
}
// If the sizes are equal, both asteroids are destroyed (pop the stack)
else if (asteroidStack[asteroidStack.length - 1] === Math.abs(asteroid)) {
asteroidStack.pop();
break;
}
// If the negative asteroid is larger, destroy the top asteroid and continue
else {
asteroidStack.pop();
}
}
}
}
return asteroidStack;
};
Time Complexity: O(n)
The outer loop iterates through each asteroid in the input list. This gives us O(n) operations in the worst case.
For each asteroid, we either push it onto the stack if it's positive or check for collisions if it's negative.
Each asteroid is either pushed onto the stack once or popped from the stack at most once. In the worst case, an asteroid could be pushed and then popped, but this will happen at most once per asteroid.
This means the total number of push and pop operations for all asteroids is O(n) as each asteroid is handled at most twice (once when pushed and once when popped, which is constant).
As each asteroid is pushed and popped at most once, the total time complexity remains O(n), where n is the number of asteroids.
Thus, the time complexity is O(n), which is efficient and scales linearly with the number of asteroids.
Space Complexity: O(n)
Auxiliary Space: O(n)
Explanation: In this solution, the only extra space used is the stack (asteroidStack) where we store the asteroids that are still in play (those that have not been destroyed).
In the worst case, when no asteroids collide, all asteroids are stored in the stack, which takes O(n) space, where n is the number of asteroids.
Thus, the auxiliary space complexity is O(n).
Total Space: O(n)
Explanation: The total space complexity is O(n) because the space required for the stack and the input list is in the same order of magnitude.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
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.
You are given n 1-indexed robots, each having a position on a line, health, and movement direction.
You are given 0-indexed integer arrays positions, healths, and a string directions (directions[i] is either 'L' for left or 'R' for right). All integers in positions are unique.
All robots start moving on the line simultaneously at the same speed in their given directions. If two robots ever share the same position while moving, they will collide.
If two robots collide, the robot with lower health is removed from the line, and the health of the other robot decreases by one. The surviving robot continues in the same direction it was going. If both robots have the same health, they are both removed from the line.
Your task is to determine the health of the robots that survive the collisions, in the same order that the robots were given, i.e., final health of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.
Return an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur.
Note: The positions may be unsorted.