Problem of the day
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.
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.
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.
4
6 7 -9 7
-9 7
The third asteroid destroys the first and the second asteroids.
Hence, the remaining asteroids are [-9, 7].
5
3 4 5 -2 7
3 4 5 7
The third asteroid destroys the 4th asteroid.
Hence, the remaining asteroids are [3, 4, 5, 7].
The expected time complexity is O(n).
1 <= 'n' <= 10^6
-10^5 <=asteroids[i] <= 10^5
Time Limit: 1 sec
Can you use a stack to find out which asteroids will collide?
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 :
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).
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).