Asteroid Collision

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
54 upvotes
Asked in companies
AmazonFlipkartDunzo

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
4
6 7 -9 7
Sample Output 1 :
-9 7
Explanation of Sample Input 1 :
The third asteroid destroys the first and the second asteroids. 

Hence, the remaining asteroids are [-9, 7].
Sample Input 2 :
5
3 4 5 -2 7
Sample Output 2 :
3 4 5 7
Explanation of Sample Input 2 :
The third asteroid destroys the 4th asteroid. 

Hence, the remaining asteroids are [3, 4, 5, 7].
Expected time complexity:
The expected time complexity is O(n).
Constraints :
1 <= 'n' <= 10^6
-10^5 <=asteroids[i] <= 10^5
Time Limit: 1 sec
Hint

 Can you use a stack to find out which asteroids will collide?

Approaches (1)
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’, 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 :

  1. Define a stack for keeping track of asteroids, let’s say, ‘remainingAsteroids’.
  2. Iterate through the given array/list. Let’s say our current index is ‘i’.
    1. If ‘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, 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.
    3. 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.
    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, in case of asteroids of equal size, both 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.
  3. 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.
Time Complexity

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 takes constant time. Thus, the overall time complexity is O(n).

Space Complexity

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, the stack size will become' N' when all the asteroids are moving in the same direction. Thus, the overall space complexity will be O(n).

Code Solution
(100% EXP penalty)
Asteroid Collision
Full screen
Console