# Robot Collisions
**Difficulty:** HARD
[External](https://leetcode.com/problems/robot-collisions)
Canonical: https://scaleengineer.com/dsa/problems/robot-collisions
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Stack
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Samsung](https://scaleengineer.com/companies/samsung), [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
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 bothremoved 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:**

![](https://assets.glich.co/dsa/robot-collisions/image0.png)

**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:**

![](https://assets.glich.co/dsa/robot-collisions/image1.png)

**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:**

![](https://assets.glich.co/dsa/robot-collisions/image2.png)

**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

# Approaches
## Brute-Force Simulation
This approach simulates the movement of robots over time. It repeatedly finds the next collision event, advances time to that point, and resolves the collision. This process continues until no more collisions are possible.
**Time:** O(N^3). In each step, we might find one collision. Finding the next collision takes O(N^2) time. There can be O(N) collisions. This leads to a total time complexity of O(N^3). · **Space:** O(N) to store the state of all robots.
**Pros:** Conceptually straightforward as it mimics the physical process.
**Cons:** Extremely inefficient with a high time complexity (O(N^3) or worse).; Difficult to implement correctly, especially handling floating-point precision for time and position.; Handling simultaneous collisions adds significant complexity.
### Explanation
We can model the process step-by-step. The core idea is to find which two robots will collide next, calculate the time until that collision, and then update the state of all robots.

The algorithm would be:
1.  Create a list of robot objects, including their current position, health, direction, and a flag indicating if they are active.
2.  Enter a loop that runs as long as new collisions can occur.
3.  Inside the loop, find the minimum time to the next collision. This involves checking every pair of robots `(i, j)` moving towards each other (`R` and `L` with `pos_i < pos_j`) and calculating `time = (pos_j - pos_i) / 2`.
4.  If no such pair exists, break the loop.
5.  Identify the pair(s) that will collide at this minimum time.
6.  Resolve the collision(s) by comparing healths, updating the survivor's health, and marking the destroyed robot(s) as inactive.
7.  Repeat the process.

After the loop, collect the healths of all active robots and return them in the original input order. This approach is highly inefficient due to the repeated search for the next collision across all pairs of robots. A code implementation would be overly complex and is omitted for practicality.
### Algorithm
- 1. Initialize a list of active robots with their properties (position, health, direction).
- 2. Loop indefinitely:
    - a. Find the smallest positive time `t_next` for the next collision by checking all pairs of robots moving towards each other.
    - b. If no such collision can happen, break the loop.
    - c. Identify all pairs that collide at `t_next`.
    - d. For each colliding pair, resolve the collision:
        - i. Compare healths.
        - ii. Update health of the survivor and decrease it by 1.
        - iii. Mark the destroyed robot(s) as inactive.
- 3. Collect the healths of the remaining active robots.
- 4. Sort the results based on the original index and return.

## Iterative Sorting and Collision
This approach improves upon brute force by recognizing that collisions only happen between adjacent robots moving towards each other after sorting by position. It repeatedly sorts the active robots and resolves the first collision it finds, iterating until no more collisions are possible.
**Time:** O(N^2 log N). In the worst case, we resolve one collision at a time. After each collision, we re-sort the remaining robots. If there are `k` robots, sorting takes O(k log k). This happens up to O(N) times. · **Space:** O(N) to store the list of robot objects.
**Pros:** More efficient than pure simulation.; Correctly identifies that only adjacent robots in sorted order can collide.
**Cons:** Inefficient due to repeated sorting of the robot list, leading to O(N^2 log N) complexity.; Implementation can be complex, especially managing the list of active robots.
### Explanation
Instead of simulating time, we can focus on the collision events. A collision can only occur between a robot moving right and a robot moving left that is immediately to its right in the sorted list of positions.

The algorithm is as follows:
1.  Create a list of robot objects, storing their original index, position, health, and direction.
2.  Start a loop that continues as long as we find and resolve a collision in a pass.
3.  In each pass, sort the current list of active robots by their position.
4.  Iterate through the sorted list to find the first adjacent pair `(i, i+1)` where robot `i` is moving right ('R') and robot `i+1` is moving left ('L').
5.  If such a pair is found, resolve the collision:
    - Compare their healths.
    - Update healths and remove the destroyed robot(s) from the list.
    - Break the inner loop and start a new pass from step 3, as the list of robots has changed.
6.  If a full pass over the sorted list completes without finding any such adjacent pair, it means no more collisions can occur. Break the main loop.
7.  Finally, the remaining robots in the list are the survivors. Sort them by their original index and return their healths.

This is better than brute-force simulation but still inefficient because of the repeated sorting. The implementation details of managing the list and re-running the process make it cumbersome.
### Algorithm
- 1. Create a list of robot objects, each with its original index, position, health, and direction.
- 2. Loop while collisions are being resolved:
    - a. Set a flag `found_collision_this_pass` to false.
    - b. Sort the current list of active robots by position.
    - c. Iterate through the sorted list to find the first adjacent pair of robots `(i, i+1)` moving towards each other ('R' then 'L').
    - d. If a pair is found:
        - i. Resolve the collision, updating healths.
        - ii. Remove destroyed robots from the list.
        - iii. Set `found_collision_this_pass` to true and break the inner loop to restart the process (re-sort).
    - e. If the inner loop completes without finding a collision, break the outer loop.
- 3. Sort the surviving robots by their original index and return their healths.

## Optimal Approach using Sorting and a Stack
This is the most efficient approach. It involves sorting the robots by position once, then using a stack to simulate the collisions in a single pass. Robots moving right are pushed onto the stack, and robots moving left collide with the robots on the stack.
**Time:** O(N log N). The dominant operation is sorting the robots by position. The subsequent pass with the stack takes O(N) time because each robot index is pushed and popped at most once. · **Space:** O(N). We need O(N) space for the indices array used for sorting and O(N) space for the stack in the worst-case scenario (all robots moving right).
**Pros:** Most efficient solution with O(N log N) time complexity.; Processes each robot a constant number of times after sorting.; Relatively straightforward to implement correctly.
**Cons:** Requires sorting, so it's not a linear time solution.; Uses extra space for the stack and indices array.
### Explanation
The key insight is that collisions only happen between a robot moving right ('R') and a robot moving left ('L') that is positioned to the right of the 'R' robot. By processing robots in order of their position, we can efficiently handle all collisions. A stack is the perfect data structure to keep track of 'R' robots that are "open" to collisions from upcoming 'L' robots.

```java
class Solution {
    public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
        int n = positions.length;
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }

        // Sort indices based on positions
        Arrays.sort(indices, (a, b) -> Integer.compare(positions[a], positions[b]));

        Stack<Integer> stack = new Stack<>(); // Stores indices of robots moving right

        for (int i : indices) {
            if (directions.charAt(i) == 'R') {
                stack.push(i);
            } else { // directions.charAt(i) == 'L'
                while (!stack.isEmpty() && healths[i] > 0) {
                    int j = stack.peek(); // Top robot on stack (moving right)

                    if (healths[j] > healths[i]) {
                        healths[j]--;
                        healths[i] = 0;
                    } else if (healths[j] < healths[i]) {
                        healths[i]--;
                        healths[j] = 0;
                        stack.pop();
                    } else { // healths[j] == healths[i]
                        healths[i] = 0;
                        healths[j] = 0;
                        stack.pop();
                    }
                }
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (healths[i] > 0) {
                result.add(healths[i]);
            }
        }
        return result;
    }
}
```
### Algorithm
- 1. Create an array of indices `0, 1, ..., n-1`.
- 2. Sort the indices array based on the robot positions.
- 3. Initialize an empty stack to store indices of right-moving robots.
- 4. Iterate through the sorted indices, processing one robot at a time.
    - a. If the robot is moving right, push its index onto the stack.
    - b. If the robot is moving left, handle collisions with robots on the stack:
        - i. While the stack is not empty and the left-moving robot has health > 0:
        - ii. Compare its health with the robot at the top of the stack.
        - iii. If the right-moving robot on the stack is stronger, it survives with health-1, and the left-moving robot is destroyed. Stop processing the left-moving robot.
        - iv. If the left-moving robot is stronger, it survives with health-1, and the right-moving robot is destroyed (popped from stack). The left-moving robot continues to collide with the next robot on the stack.
        - v. If healths are equal, both are destroyed. Pop from the stack and stop processing the left-moving robot.
- 5. After the loop, filter the original `healths` array for values > 0.
- 6. Return the list of surviving healths in their original order.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> survivedRobotsHealths(int[] positions, int[] healths,
                                      String directions) {
    int n = positions.length;
    Integer[] indices = new Integer[n];
    for (int i = 0; i < n; i++) {
      indices[i] = i;
    }
    Arrays.sort(indices, (i, j)->Integer.compare(positions[i], positions[j]));
    Stack<Integer> stack = new Stack<>();
    for (int currentIndex : indices) {
      if (directions.charAt(currentIndex) == 'R') {
        stack.push(currentIndex);
      } else {
        while (!stack.isEmpty() && healths[currentIndex] > 0) {
          int topIndex = stack.pop();
          if (healths[topIndex] > healths[currentIndex]) {
            healths[topIndex] -= 1;
            healths[currentIndex] = 0;
            stack.push(topIndex);
          } else if (healths[topIndex] < healths[currentIndex]) {
            healths[currentIndex] -= 1;
            healths[topIndex] = 0;
          } else {
            healths[currentIndex] = 0;
            healths[topIndex] = 0;
          }
        }
      }
    }
    List<Integer> result = new ArrayList<>();
    for (int health : healths) {
      if (health > 0) {
        result.add(health);
      }
    }
    return result;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} positions * @param {number[]} healths * @param {string} directions * @return {number[]} */ var survivedRobotsHealths = function ( positions , healths , directions ) { const idx = Array . from ({ length : positions . length }, ( _ , i ) => i ); const stk = []; idx . sort (( a , b ) => positions [ a ] - positions [ b ]); for ( let iRight of idx ) { while ( stk . length ) { const iLeft = stk . at ( - 1 ); const havePair = directions [ iLeft ] === ' R ' && directions [ iRight ] === ' L ' ; if ( ! havePair ) break ; if ( healths [ iLeft ] === healths [ iRight ]) { healths [ iLeft ] = healths [ iRight ] = iRight = - 1 ; stk . pop (); break ; } if ( healths [ iLeft ] < healths [ iRight ]) { healths [ iLeft ] = - 1 ; healths [ iRight ] -- ; stk . pop (); } else { healths [ iRight ] = iRight = - 1 ; healths [ iLeft ] -- ; break ; } } if ( iRight !== - 1 ) stk . push ( iRight ); } return healths . filter ( i => ~ i ); };
```

### CPP

```cpp
class Solution {
public:
  vector<int> survivedRobotsHealths(vector<int> &positions,
                                    vector<int> &healths, string directions) {
    int n = positions.size();
    vector<int> indices(n);
    iota(indices.begin(), indices.end(), 0);
    stack<int> st;
    auto lambda = [&](int i, int j) { return positions[i] < positions[j]; };
    sort(begin(indices), end(indices), lambda);
    vector<int> result;
    for (int currentIndex : indices) {
      if (directions[currentIndex] == 'R') {
        st.push(currentIndex);
      } else {
        while (!st.empty() && healths[currentIndex] > 0) {
          int topIndex = st.top();
          st.pop();
          if (healths[topIndex] > healths[currentIndex]) {
            healths[topIndex] -= 1;
            healths[currentIndex] = 0;
            st.push(topIndex);
          } else if (healths[topIndex] < healths[currentIndex]) {
            healths[currentIndex] -= 1;
            healths[topIndex] = 0;
          } else {
            healths[currentIndex] = 0;
            healths[topIndex] = 0;
          }
        }
      }
    }
    for (int i = 0; i < n; ++i) {
      if (healths[i] > 0) {
        result.push_back(healths[i]);
      }
    }
    return result;
  }
};

```

### Python

```python
class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]: n = len(positions) indices = list(range(n)) stack = [] indices . sort(key=lambda i: positions[i]) for currentIndex in indices: if directions[currentIndex] == "R": stack . append(currentIndex) else: while stack and healths[currentIndex] > 0: topIndex = stack . pop() if healths[topIndex] > healths[currentIndex]: healths[topIndex] -= 1 healths[currentIndex] = 0 stack . append(topIndex) elif healths[topIndex] < healths[currentIndex]: healths[currentIndex] -= 1 healths[topIndex] = 0 else: healths[currentIndex] = 0 healths[topIndex] = 0 result = [health for health in healths if health > 0] return result

```