Last Updated: 12 Dec, 2020
Asteroid Collision
Moderate
Asked in companies
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 moves 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 asteroids are the same size, then both 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.
Example :
Input: ‘asteroids’ = [3,-2,4]
Output: [3, 4]
Explanation: The first asteroid will destroy the second asteroid. Hence, after the collision, the state of the asteroids will be [3,4].
Note:
You don’t need to print anything. Just implement the given function.
Input Format :
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 :
Return an array representing the final state of asteroids.
Approaches
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’, it will collide with an asteroid moving to the right (+ve value) and having an 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’.
- If ‘asteroids[i]’ is positive, then we will push the current element into the stack.
- If the stack is empty or the element at the top of the stack is negative, we will also push the current element into the stack. Since the asteroid at the top of the stack is negative, all the asteroids in the stack and the current asteroid would be moving to the left. Thus, the recent asteroid will not collide with any other asteroid.
- If 'asteroids[i]' is negative, 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.
- Now if the element at the top of the stack is equal to the absolute value of 'asteroids[i]', then pop the element because, in case of asteroids of equal size, both asteroids will be destroyed.
- 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.