Asteroid Collision
You are given an array/list “ASTEROIDS” representing asteroids in a row. For each element of the given array, its absolute value denotes the size of that asteroid and its sign denotes the direction it is moving in(+ve meaning right and -ve meaning left). An asteroid with a weight of 0 denotes a massless asteroid that moves in the right direction.

All asteroids are moving at the same speed. Whenever two asteroids collide, the smaller asteroid gets destroyed. If both the asteroids have the same size, then both the asteroids get destroyed. Two asteroids moving in the same direction never collide.

You are supposed to find the state of the asteroids after all collisions.

For Example :

ASTEROIDS = {3,-2,4} The first asteroid will destroy the second asteroid. Hence, after the collision, the state of the asteroids will be {3,4}.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows. The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array/list. The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the array/list.

Output Format :

For each test case, print all remaining asteroids separated by a single space.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1

Question

Asteroid Collision

You are given an array/list “ASTEROIDS” representing asteroids in a row. For each element of the given array, its absolute value denotes the size of that asteroid and its sign denotes the direction it is moving in(+ve meaning right and -ve meaning left). An asteroid with a weight of 0 denotes a massless asteroid that moves in the right direction.

All asteroids are moving at the same speed. Whenever two asteroids collide, the smaller asteroid gets destroyed. If both the asteroids have the same size, then both the asteroids get destroyed. Two asteroids moving in the same direction never collide.

You are supposed to find the state of the asteroids after all collisions.

For Example :

ASTEROIDS = {3,-2,4}
The first asteroid will destroy the second asteroid. Hence, after the collision, the state of the asteroids will be {3,4}.

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases. The test cases are as follows.

The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array/list.

The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the array/list.

Output Format :

For each test case, print all remaining asteroids separated by a single space.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 50
1 <= 'N' <= 10^4
-10^5 <= ASTEROIDS[i] <= 10^5

Where ASTEROIDS[i] denotes the i-th asteroid.

Time Limit: 1 sec

Accepted Answer

Thought about stack solution.

Accepted Answer

Stack Based Approach

The idea is to use the stack to maintain the state of the asteroids. If we find an asteroid moving to the left (-ve value), let’s say at index i, then it will collide with an asteroid moving to the right (+ve value) and having index less than i. Hence, we can use a stack to keep track of asteroids moving to the right and then pop the elements from the stack as and when any asteroid gets destroyed.

The steps are as follows :

Define a stack, for keeping track of asteroids, let’s say remainingAsteroids.
Iterate through the given array/list, let’s say our current index is i.
1. If the ASTEROIDS[i] is positive, then we will push the current element into the stack.
2. If the stack is empty or the element at the top of the stack is negative then also we will push the current element into the stack. Since the asteroid at the top of the stack is negative, all the asteroids in the stack, as well as the current asteroid, would be moving to the left. Thus, the current asteroid will not collide with any other asteroid.
3. If ASTEROIDS[i] is negative then while the element at the top of the stack is positive and is less than the absolute value of ASTEROIDS[i] we will keep popping the top element from the stack. We do this because the current asteroid will collide with and destroy all asteroids moving to the right and having a size less than that of the current asteroid.
4. Now if the element at the top of the stack is equal to the absolute value of ASTEROIDS[i] then pop the element because incase of asteroids of equal size, both the asteroids will be destroyed.
5. Else if the stack is empty or the top element is negative, then we will push the current element into the stack.
Now all the elements present in the stack will represent the final state of the asteroids. Hence we will return all the elements of the stack.

Space Complexity: O(n)Explanation:

O(N), where N is the length of the given array/list.

We are using a stack for maintaining the state of the asteroids, in the worst case when all the asteroids are moving in the same direction the size of the stack will become ‘N’. Thus, the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the length of the given array/list.

We are iterating through the given array/list which will take O(N) time. Also, we are performing push and pop operations on a stack which take constant time. Thus, the overall time complexity is O(N).

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    Where 'N' is the number of elements in the given array/list
*/

vector collidingAsteroids(vector &asteroids)
{
    int n = asteroids.size();

    //    Using a vector as a stack since we can pop the last element of a vector in O(1) and push_back() operation also takes O(1) time.
    vector remainingAsteroids;

    //    Iterate through the given array/list.
    for (int i = 0; i < n; i++)
    {
        //    Push the current asteroid in the stack.
        if (asteroids[i] > 0 || remainingAsteroids.size() == 0 || remainingAsteroids.back() < 0)
        {
            remainingAsteroids.push_back(asteroids[i]);
        }
        else
        {
            //    Pop the asteroids from the stack.
            while (remainingAsteroids.size() > 0 && remainingAsteroids.back() > 0 && remainingAsteroids.back() < -asteroids[i])
            {
                remainingAsteroids.pop_back();
            }

            //    If size of both asteroids is the same then destroy both the asteroids.
            if (remainingAsteroids.size() > 0 && remainingAsteroids.back() == -asteroids[i])
            {
                remainingAsteroids.pop_back();
            }

            //    If the current asteroid has not been destroyed then push the current asteroid to the stack.
            else if (remainingAsteroids.size() == 0 || remainingAsteroids.back() <= 0)
            {
                remainingAsteroids.push_back(asteroids[i]);
            }
        }
    }

    //    Return the final state of the asteroids
    return remainingAsteroids;
}

Python (3.5)

'''
    Time Complexity: O(N)
    Space Complexity: O(N)

    Where 'N' is the number of elements in the given array/list
'''


def collidingAsteroids(asteroids):
    n = len(asteroids)

    # Using a list as a stack and our final answer
    remainingAsteroids = []

    # Iterate through the given array/list.
    for i in range(n):
        # Stores the current asteroid
        cur = asteroids[i]

        if cur > 0 or len(remainingAsteroids) == 0 or remainingAsteroids[-1] < 0:
            remainingAsteroids.append(cur)
        else:
            # Pop the asteroids from the stack.
            while len(remainingAsteroids) and remainingAsteroids[-1] > 0 and remainingAsteroids[-1] < cur * -1:
                del remainingAsteroids[-1]

            # If size of both asteroids is the same then destroy both the asteroids.
            if len(remainingAsteroids) and remainingAsteroids[-1] == cur * -1:
                del remainingAsteroids[-1]

            # If the current asteroid has not been destroyed then push the current asteroid to the stack.
            elif len(remainingAsteroids) == 0 or remainingAsteroids[-1] <= 0:
                remainingAsteroids.append(cur)

    # The elements of the stack is the final answer
    return remainingAsteroids

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    Where 'N' is the number of elements in the given array/list
*/

import java.util.Stack;
import java.util.ArrayList;
import java.util.Collections;

public class Solution
{

    public static ArrayList collidingAsteroids(ArrayList asteroids)
    {
        int n = asteroids.size();

        //    Using a ArrayList as a stack since we can pop the last element of a ArrayList in O(1) and push_back() operation also takes O(1) time.
        Stack remainingAsteroids = new Stack();

        //    Iterate through the given array/list.
        for (int i = 0; i < n; i++)
        {

            //    Push the current asteroid in the stack.
            if (asteroids.get(i) > 0 || remainingAsteroids.size() == 0 || remainingAsteroids.peek() < 0)
            {
                remainingAsteroids.push(asteroids.get(i));
            }
            else
            {

                //    Pop the asteroids from the stack.
                while (remainingAsteroids.size() > 0 && remainingAsteroids.peek() > 0 && remainingAsteroids.peek() < -asteroids.get(i))
                {
                    remainingAsteroids.pop();
                }

                //    If size of both asteroids is the same then destroy both the asteroids.
                if (remainingAsteroids.size() > 0 && remainingAsteroids.peek() == -asteroids.get(i))
                {
                    remainingAsteroids.pop();
                }
                //    If the current asteroid has not been destroyed then push the current asteroid to the stack.
                else if (remainingAsteroids.size() == 0 || remainingAsteroids.peek() <= 0)
                {
                    remainingAsteroids.push(asteroids.get(i));
                }
            }
        }

        ArrayList ans = new ArrayList(remainingAsteroids.size());

        while (remainingAsteroids.isEmpty() == false)
        {
            ans.add(remainingAsteroids.pop());
        }

        Collections.reverse(ans);

        //    Return the final state of the asteroids
        return ans;
    }
}