Solution For Asteroid Collision

Problem Statement:

We are given an array of integers that represent asteroids. Each asteroid in the array has a size, which can be either positive or negative. Positive asteroids travel in the same direction as the given array, and negative asteroids travel towards the opposite direction.

The problem is to simulate the motion of all the asteroids. If two asteroids collide, then the smaller asteroid will be destroyed. If two asteroids are of the same size, then both asteroids will be destroyed. The final state of the asteroids array is the state after all collisions have occurred.

Solution:

To solve this problem, we can use a stack data structure to keep track of the asteroids that are still in motion. We can iterate through the given asteroids array and check the direction of each asteroid. If the asteroid is moving towards the right, we can simply push it onto the stack. If the asteroid is moving towards the left, then we need to check if there are any asteroids in the stack that are moving towards the right.

If there are no asteroids in the stack that are moving towards the right, then the current asteroid will continue moving towards the left. We can simply push it onto the stack.

If there is an asteroid in the stack that is moving towards the right, then we need to compare the sizes of the two asteroids. If the size of the asteroid in the stack is greater than the current asteroid, then the current asteroid will be destroyed. We can simply skip the current asteroid and continue iterating through the rest of the array.

If the size of the asteroid in the stack is smaller than the current asteroid, then we need to remove the asteroid from the stack and compare it with the next asteroid in the stack. We repeat this process until all collisions have been resolved.

We can implement the above approach using a stack, and the time complexity of this algorithm is O(n), where n is the number of asteroids in the array.

Solution Code:

def asteroidCollision(asteroids: List[int]) -> List[int]:
stack = [] for asteroid in asteroids:
if asteroid > 0:
stack.append(asteroid)
else:
while stack and stack[-1] > 0 and stack[-1] < abs(asteroid):
stack.pop()
if not stack or stack[-1] < 0:
stack.append(asteroid)
elif stack[-1] == abs(asteroid):
stack.pop()
return stack

Explanation:

In the above code, we have used a stack to keep track of the asteroids that are still in motion. We iterate through the given asteroids array and check the direction of each asteroid.

If the asteroid is moving towards the right, we simply push it onto the stack.

If the asteroid is moving towards the left, we check if there are any asteroids in the stack that are moving towards the right.

If there are no asteroids in the stack that are moving towards the right, then the current asteroid will continue moving towards the left. We can simply push it onto the stack.

If there is an asteroid in the stack that is moving towards the right, we compare the sizes of the two asteroids.

If the size of the asteroid in the stack is greater than the current asteroid, then the current asteroid will be destroyed. We simply skip the current asteroid and continue iterating through the rest of the array.

If the size of the asteroid in the stack is smaller than the current asteroid, we remove the asteroid from the stack and compare it with the next asteroid in the stack. We repeat this process until all collisions have been resolved.

Finally, we return the stack, which contains the final state of the asteroids array after all collisions have occurred.

Step by Step Implementation For Asteroid Collision

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.

Example 1:
Input: 
asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: 
The 10 and -5 collide resulting in 10.  The 5 and 10 never collide.
Example 2:
Input: 
asteroids = [8, -8]
Output: []
Explanation: 
The 8 and -8 collide exploding each other.
Example 3:
Input: 
asteroids = [10, 2, -5]
Output: [10]
Explanation: 
The 2 and -5 collide resulting in -5.  The 10 and -5 collide resulting in 10.
Example 4:
Input: 
asteroids = [-2, -1, 1, 2]
Output: [-2, -1, 1, 2]
Explanation: 
The -2 and -1 are moving left, while the 1 and 2 are moving right.
Asteroids moving the same direction never meet, so no collisions happen.
Note:

The length of asteroids will be at most 10000.
Each asteroid will be a non-zero integer in the range [-1000, 1000]..

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        
        # create a stack to store the asteroids
        stack = []
        
        # loop through the asteroids
        for asteroid in asteroids:
            
            # if the stack is empty or the asteroid is going in the same direction as the top of the stack, add it to the stack
            if not stack or asteroid > 0 or stack[-1] < 0:
                stack.append(asteroid)
            
            # otherwise, if the asteroid is going in the opposite direction as the top of the stack, they may collide
            else:
                
                # while there is a collision
                while stack and asteroid < 0 < stack[-1]:
                    
                    # if the asteroid is smaller, it will be destroyed
                    if abs(asteroid) < abs(stack[-1]):
                        break
                    
                    # if the asteroid is the same size, they will both be destroyed
                    elif abs(asteroid) == abs(stack[-1]):
                        stack.pop()
                        break
                    
                    # if the asteroid is larger, the top of the stack will be destroyed
                    else:
                        stack.pop()
                
                # if there was no collision or the asteroid is larger, add it to the stack
                if not stack or asteroid > 0 or stack[-1] < 0:
                    stack.append(asteroid)
        
        # return the final stack
        return stack

var asteroidCollision = function(asteroids) {
    
    // create a stack to store the asteroids
    let stack = [];
    
    // loop through the asteroids array
    for (let i = 0; i < asteroids.length; i++) {
        
        // if the stack is empty or the current asteroid is going in the same direction as the last asteroid in the stack, push it to the stack
        if (stack.length === 0 || asteroids[i] > 0 || stack[stack.length - 1] < 0) {
            stack.push(asteroids[i]);
        }
        
        // if the current asteroid is going in the opposite direction as the last asteroid in the stack
        else {
            
            // while the stack is not empty and the last asteroid in the stack is going in the same direction as the current asteroid
            while (stack.length > 0 && stack[stack.length - 1] > 0 && asteroids[i] < 0) {
                
                // if the absolute value of the current asteroid is greater than the absolute value of the last asteroid in the stack, remove the last asteroid from the stack
                if (Math.abs(asteroids[i]) > Math.abs(stack[stack.length - 1])) {
                    stack.pop();
                }
                
                // if the absolute value of the current asteroid is less than the absolute value of the last asteroid in the stack, don't add the current asteroid to the stack
                else if (Math.abs(asteroids[i]) < Math.abs(stack[stack.length - 1])) {
                    break;
                }
                
                // if the absolute value of the current asteroid is equal to the absolute value of the last asteroid in the stack, remove the last asteroid from the stack and don't add the current asteroid to the stack
                else {
                    stack.pop();
                    break;
                }
            }
        }
    }
    
    // return the stack
    return stack;
};

We can solve this problem by using a stack. We iterate through the asteroids array from left to right. For each asteroid, we compare it with the top element of the stack. If the asteroid is going in the same direction (i.e. has the same sign) as the top element of the stack, we simply push it onto the stack. If the asteroid is going in the opposite direction, we keep popping elements off the stack until we either find an element going in the same direction, or we empty the stack. If we empty the stack, then we know that the asteroid will definitely collide with the ground, so we add it to the front of the array. Otherwise, if we find an element going in the same direction, we compare the sizes of the two asteroids. If the asteroid we are currently iterating over is larger, then we know that it will collide with the asteroid on the top of the stack, so we pop that element off the stack and continue iterating. If the asteroid on the top of the stack is larger, then we know that our current asteroid will collide with the ground, so we add it to the front of the array and continue iterating.

using System; 

public class Solution {
    public int[] AsteroidCollision(int[] asteroids) {
        Stack stack = new Stack();
        for (int i = 0; i < asteroids.Length; i++)
        {
            if (stack.Count == 0 || asteroids[i] > 0)
            {
                stack.Push(asteroids[i]);
            }
            else
            {
                while (stack.Count > 0 && stack.Peek() > 0 && stack.Peek() < -asteroids[i])
                {
                    stack.Pop();
                }

                if (stack.Count > 0 && stack.Peek() == -asteroids[i])
                {
                    stack.Pop();
                }
                else if (stack.Count == 0 || stack.Peek() < 0)
                {
                    stack.Push(asteroids[i]);
                }
            }
        }

        int[] result = new int[stack.Count];
        for (int i = stack.Count - 1; i >= 0; i--)
        {
            result[i] = stack.Pop();
        }

        return result;
    }
}