168. Asteroid Collision
Challenge1000 ms256 MBSolved by 0%
Asteroids move along a line. Each is given by a non-zero integer: the size is its absolute value, and the sign is its direction — positive moves RIGHT, negative moves LEFT. All move at the same speed.
Two asteroids collide when a right-moving one is followed by a left-moving one. The smaller explodes. If they are the same size, both explode. Asteroids moving the same way, or moving apart, never meet.
Read n asteroids in order and print what survives, or Empty if nothing does.
Constraints - `1 ≤ n ≤ 100000` - `-1000 ≤ a[i] ≤ 1000`, and never 0.
Input
The first line contains an integer n.
The second line contains n space-separated integers.
Output
Print the surviving asteroids in order on ONE line, separated by single spaces, or Empty if none survive.
Input2
5 -5
OutputEmpty
Notehas two equal asteroids that destroy each other
Input3
5 10 -5
Output5 10
Notehas the left-mover lose to the larger right-mover
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution