Asteroid Collision

Share

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.
Constraints:

Contents

Solution 1 - Using stack

As per the problem statement, sign of the number represents its direction, positive sign means, it is going towards right and negative sign means, it is going towards left. If the asteroids going in opposite directions, only then they collide, meaning that current asteroid sign should be positive and the next asteroid sign should be negative. There is one more important thing to remember, if the asteroid sizes are same both will explode otherwise the smaller one will explode.

In this approach, we are going to use a Stack, to store asteroids, and since the asteroids will explode only if the current asteroid has negative sign and the top of the stack is a positive sign asteroid, then we apply following rules on which asteroids will explode.

  • If the top of the stack value (+ve value) and current asteroid value (-ve value) are same, that means both will explode, so remove the top element from stack and also ignore current element from output.
  • If the top of the stack value (+ve value) is greater than the current asteroid value (-ve value), current asteroid will explode, so we can ignore current asteroid from output.
  • If the top of the stack value (+ve value) is smaller than the current asteroid value (-ve value), then the asteroid at the top of the stack will explode, so remove the top element from the stack, also keep checking next elements as they also may get exploded as well.

Implementation steps:
  • First, we will create a variable stack a Stack that we will use to store asteroid values.
  • Next, loop through input array asteroids and create a variable add (initialize this with true), this is used to check whether we need to add current element to the stack or not, for example if the current asteroid is going to explode, then we don't need to add it to stack.
  • Then, using a while loop, check if the current element is a negative sign number, and the stack is not empty, and the top element is a positive number, this means a collision is going to happen.
    • If absolute values of both current and top of stack are same : Remove the top of the element, and update add=false and break the while loop.
    • If abosulute value of current element is less than top of stack element : update add=false and break the while loop.
    • If abosulute value of current element is greater than top of stack element : Remove the top of the element, and continue the while loop.
  • After the while loop, check if add value is true, if it is, then add current element to the stack.
  • Finally, whatever is left in the stack are the ones, return these as answer.
Java
import java.util.Arrays;
import java.util.Stack;

public class AsteroidCollision {

    static int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for(int asteroid: asteroids) {
            boolean add = true;
            while(asteroid <0 && !stack.isEmpty() && stack.peek() >0) {
                if(Math.abs(asteroid) == stack.peek()) {
                    stack.pop();// remove the top, and don't add current since both are explode
                    add = false;
                    break;
                } else if(Math.abs(asteroid) < stack.peek()) {
                    add = false; // current is smaller, so it wil explode, so don't need to add
                    break;
                } else {
                    stack.pop();
                }
            }
            if(add) {
                stack.push(asteroid);
            }
        }
        int[] remaining = new int[stack.size()];
        for(int i=0;i<remaining.length; i++) {
            remaining[i] = stack.get(i);
        }
        return remaining;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(asteroidCollision(new int[]{5,10,-5})));
        System.out.println(Arrays.toString(asteroidCollision(new int[]{-8, 8})));
        System.out.println(Arrays.toString(asteroidCollision(new int[]{8, -8})));
        System.out.println(Arrays.toString(asteroidCollision(new int[]{10,2,-5})));
    }

}
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input array asteroids.
Space complexity: O(n).

Above implementations source code can be found at GitHub link for Java code