Colliding Rocks in a Row
Problem
Rocks move along a line at the same speed. Each is given as a nonzero integer: the absolute value is its size, and the sign is its direction, positive for right and negative for left. When two rocks meet, the smaller one breaks; if they are the same size, both break. Rocks moving in the same direction never meet. Return the rocks that remain after every collision, in their original order. There are between 2 and 10,000 rocks, and each size is at most 1,000.
Examples
Input: rocks = [5, 10, -5]
Output: [5, 10]
Why: -5 meets 10 and breaks; 5 and 10 move the same way and never meetInput: rocks = [10, 2, -5]
Output: [10]
Why: -5 breaks 2, then meets 10 and breaks itselfInput: rocks = [8, -8]
Output: []
Why: edge case, equal sizes break each otherHints
0 / 3
A collision only happens between a rock moving right and a rock further along the line moving left. Rocks moving left at the start of the line simply leave.
Walk from left to right and keep the survivors on a stack. A new left-mover can only hit the right-movers at the top of that stack, nearest first.
While the top is a right-mover smaller than the incoming left-mover, pop it. Then decide: equal sizes pop the top and drop the newcomer, a bigger top drops the newcomer, and otherwise the newcomer is pushed.
Solution
Scanning left to right, the stack holds the rocks that have survived so far. A right-mover never hits anything behind it, so it is pushed. A left-mover can only meet the right-movers at the top of the stack, and it meets the nearest one first, so it keeps popping smaller right-movers until it either breaks against a bigger one, cancels out an equal one, or reaches a left-mover or the bottom of the stack, in which case it survives and is pushed. What remains on the stack is already in the original order. Each rock is pushed and popped at most once, so time and space are O(n).
def after_collisions(rocks):
stack = []
for rock in rocks:
alive = True
while alive and rock < 0 and stack and stack[-1] > 0:
if stack[-1] < -rock: # the right-mover breaks, keep going
stack.pop()
continue
if stack[-1] == -rock: # both break
stack.pop()
alive = False # the incoming rock is gone
if alive:
stack.append(rock)
return stack
print(after_collisions([5, 10, -5])) # -> [5, 10]
print(after_collisions([10, 2, -5])) # -> [10]
print(after_collisions([8, -8])) # -> []
print(after_collisions([-2, -1, 1, 2])) # -> [-2, -1, 1, 2]Stuck on the idea rather than the code? Monotonic Stack covers it.