Skip to main content
Talentd

Robot Collisions - Solution & Explanation

HardArrayStackSortingSimulation18 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

There are n 1-indexed robots, each having a position on a line, health, and movement direction.

You are given 0-indexed integer arrays positions, healths, and a string directions (directions[i] is either 'L' for left or 'R' for right). All integers in positions are unique.

All robots start moving on the line simultaneously at the same speed in their given directions. If two robots ever share the same position while moving, they will collide.

If two robots collide, the robot with lower health is removed from the line, and the health of the other robot decreases by one. The surviving robot continues in the same direction it was going. If both robots have the same health, they are both removed from the line.

Your task is to determine the health of the robots that survive the collisions, in the same order that the robots were given, i.e. final health of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.

Return an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur.

Note: The positions may be unsorted.

 

 

Example 1:

Input: positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"
Output: [2,17,9,15,10]
Explanation: No collision occurs in this example, since all robots are moving in the same direction. So, the health of the robots in order from the first robot is returned, [2, 17, 9, 15, 10].

Example 2:

Input: positions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL"
Output: [14]
Explanation: There are 2 collisions in this example. Firstly, robot 1 and robot 2 will collide, and since both have the same health, they will be removed from the line. Next, robot 3 and robot 4 will collide and since robot 4's health is smaller, it gets removed, and robot 3's health becomes 15 - 1 = 14. Only robot 3 remains, so we return [14].

Example 3:

Input: positions = [1,2,5,6], healths = [10,10,11,11], directions = "RLRL"
Output: []
Explanation: Robot 1 and robot 2 will collide and since both have the same health, they are both removed. Robot 3 and 4 will collide and since both have the same health, they are both removed. So, we return an empty array, [].

 

Constraints:

  • 1 <= positions.length == healths.length == directions.length == n <= 105
  • 1 <= positions[i], healths[i] <= 109
  • directions[i] == 'L' or directions[i] == 'R'
  • All values in positions are distinct

Approach Overview

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.

Approach 1: Sorting and Stack-based Collision Detection

This approach involves sorting the robots based on their positions so that we can simulate their movements along the line. We utilize a stack to keep track of the robots moving rightward. When a robot moving left encounters one or more robots on the stack, a collision is detected, and their healths are compared to determine the outcome.

The function first combines the input into a list of tuples and sorts it based on positions. For each robot, if it's moving right, its index is pushed onto a stack. When a left-moving robot encounters right-moving ones, collisions occur, and appropriate robots are removed based on their healths.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log n) due to sorting the list of robots.
Space Complexity: O(n) because of the additional data structures used (stack and survivor list).

Try this approach in the editor →

Approach 2: Two-Pointer Collision Simulation

This approach simulates the collision process using a two-pointer technique. Each pointer represents a different direction of movement. By carefully checking each pair of robots, we can simulate their interactions and resolve collisions by adjusting health values and determining survivors.

This solution leverages a two-pointer-like mechanism where rightward-moving robots are managed with a stack. As each leftward-moving robot approaches, they are compared against the stack, with resulting health and survival adjustments.

Code

JavaScriptC

JavaScript

C

Complexity

Time Complexity: O(n log n) due to sorting the positions.
Space Complexity: O(n) due to extra data structures for handling collisions.

Try this approach in the editor →

Approach 3: Default Approach

We first sort the robots by position in ascending order, storing the sorted robot indices in an array idx. We then use a stack to simulate the collision process:

  1. Traverse the robot indices i in idx from left to right. If directions[i] is moving right, push i onto the stack.
  2. If directions[i] is moving left, it collides with the right-moving robot at the top of the stack, until the stack is empty or the current robot is removed.
    • If the top robot's health is greater than the current robot's, the current robot is removed and the top robot's health decreases by 1.
    • If the top robot's health is less than the current robot's, the top robot is removed, the current robot's health decreases by 1, and the current robot continues to collide with the new top robot.
    • If both have equal health, both are removed.

Finally, we return the health values of all robots with health greater than 0.

The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of robots.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Stack-based Collision Detection

Time Complexity: O(n log n) due to sorting the list of robots.
Space Complexity: O(n) because of the additional data structures used (stack and survivor list).

Two-Pointer Collision Simulation

Time Complexity: O(n log n) due to sorting the positions.
Space Complexity: O(n) due to extra data structures for handling collisions.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Stack Collision DetectionO(n log n)O(n)General solution; clean collision modeling using a stack
Two-Pointer Collision SimulationO(n log n)O(n)When implementing a pointer-based simulation without an explicit stack

Video Solution

Robot Collisions | Made Easy | Dry Run | Leetcode 2751 | codestorywithMIK • codestorywithMIK • 16,872 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Robot Collisions easy or hard?
Robot Collisions is rated Hard because it combines sorting, stack-based collision handling, and careful simulation logic. The challenge comes from correctly updating health values and handling repeated collisions while maintaining the final output order.
How to solve Robot Collisions in O(n)?
Pure O(n) is only possible if robot positions are already sorted. With sorted positions, you can scan from left to right and use a stack (or pointer tracking) to resolve collisions in linear time. Each robot participates in at most one push and one pop operation.
Robot Collisions Python or Java solution
Most implementations follow the same pattern: sort robot indices by position, iterate through them, and use a stack to manage right-moving robots. Python and Java solutions typically store indices in the stack and update the health array directly during collision resolution.
What is the best approach for Robot Collisions?
The sorting + stack simulation is the most reliable approach. First sort robots by position, then use a stack to track right-moving robots and resolve collisions when a left-moving robot appears. Each collision is processed in constant time, giving O(n log n) overall complexity due to sorting and O(n) space.
Is Robot Collisions asked at Google/Amazon/Meta?
Collision simulation and stack-based interaction problems frequently appear in interviews at companies like Amazon, Google, and Meta. Robot Collisions is conceptually similar to problems such as Asteroid Collision, which is a common interview question testing stacks and simulation logic.
What data structure is used in Robot Collisions?
A stack is the key data structure used to track robots moving to the right. When a left-moving robot appears, it repeatedly collides with robots from the stack until one survives or both are destroyed. Sorting is also required to process robots in positional order.
What is the time complexity of Robot Collisions?
The optimal solution runs in O(n log n) time because robots must be sorted by position before simulating collisions. After sorting, the stack-based collision processing runs in O(n) since each robot is pushed and popped at most once.

Ready to solve this problem?

Practice Robot Collisions with our built-in code editor and test cases.

Practice on FleetCode
Previous

Asteroid Collision