432. Rock Collisions
Rocks drift along a straight line, listed from left to right. The absolute value of rocks[i] is its size and the sign is its heading: positive drifts right, negative drifts left, and all rocks move at the same speed. A value of 0 is harmless dust that vanishes at once and never takes part in anything.
Two rocks collide only when a right-moving rock is somewhere to the left of a left-moving one with nothing surviving between them. The smaller rock is destroyed; if the sizes are equal, both are destroyed. Rocks heading the same way never meet. Return the rocks that remain after all collisions, in their original left-to-right order, with their signs.
Example 1
- Input:
- rocks = [6,-2,-9,4,5,-5]
- Output:
- [-9,4]
- Explanation:
6 destroys -2, then -9 destroys 6. The 4 is never met by a left-mover before 5 arrives, and 5 and -5 cancel each other, leaving -9 and 4.
Example 2
- Input:
- rocks = [-3,-8,2,7,-4,-1]
- Output:
- [-3,-8,2,7]
- Explanation:
The two leading negatives drift away. 7 destroys -4 and -1 in turn, and 2 is trapped behind 7 and survives, so the result is -3, -8, 2, 7.
Constraints
1 ≤ rocks.length ≤ 105
-1000 ≤ rocks[i] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)