Robot Collisions - Solution & Explanation

Problem Overview: You are given robots on a number line with positions, health values, and directions (L or R). Robots moving toward each other collide. The robot with lower health is destroyed, and the winner loses one health. The task is to simulate all collisions and return the remaining health values of surviving robots in their original order.

Approach 1: Sorting and Stack-based Collision Detection (O(n log n) time, O(n) space)

Robots interact based on their positions, not their input order. The first step is to sort robot indices by position using sorting. After sorting, iterate from left to right. Maintain a stack that stores indices of robots moving to the right (R). When you encounter a robot moving left (L), it may collide with robots stored in the stack.

Resolve collisions using a loop. Compare the current robot's health with the robot on top of the stack. The robot with smaller health is removed. The survivor loses one health and may continue colliding with the next robot. If both have equal health, both are destroyed. This pattern is a classic use of a stack to simulate pairwise interactions. Each robot is pushed and popped at most once, so the collision processing itself is linear.

The overall complexity is O(n log n) due to sorting by position, while the stack simulation runs in O(n). Space complexity is O(n) for storing robot indices and survivors. This approach is the most intuitive and closely mirrors how the physical simulation works.

Approach 2: Two-Pointer Collision Simulation (O(n log n) time, O(n) space)

Another way to model the system is to first sort robots by position and then simulate interactions using two directional scans. After sorting, track right-moving robots and resolve collisions when a left-moving robot appears. Instead of an explicit stack structure, pointers track the most recent active right-moving robot that could collide with the current left-moving robot.

The algorithm repeatedly compares the current robot with the nearest opposing robot and applies the same health reduction rules used in the simulation. When a robot is destroyed, pointers advance to the next possible candidate. This technique keeps the logic iterative and avoids explicit stack operations, though conceptually it still represents the same collision frontier.

The runtime remains O(n log n) because sorting dominates the cost. The simulation step processes each robot a constant number of times, giving O(n) additional work. Space complexity is O(n) for storing sorted indices and tracking robot states.

Recommended for interviews: The sorting + stack approach is the most expected solution. It clearly models collisions and demonstrates understanding of monotonic interaction patterns similar to asteroid collision problems. Starting with a naive simulation shows understanding of the rules, but implementing the stack-based collision resolution signals strong algorithmic reasoning.