Robot Collisions

Problem

We are given three inputs:

• positions[i] = robot position on the line
• healths[i] = robot health
• directions[i] = 'L' or 'R'

All robots start moving at the same time and at the same speed.

If two robots collide:

• the robot with smaller health is removed
• the surviving robot loses 1 health
• if both health values are equal, both robots are removed

We need to return the health of the surviving robots in their original input order.

Key Observation

Robots only collide in one situation:

• a robot on the left is moving right
• a robot on the right is moving left

That means collision handling becomes much easier if we process robots from left to right by position.

The tricky part is that positions is unsorted, so we cannot simulate directly in input order.

Approach

1. Sort robots by position

Instead of rearranging all arrays, we sort an array of indices based on positions[index].

This lets us process robots in physical left-to-right order while still preserving the original indices for the final answer.

2. Use a stack for right-moving robots

If a robot is moving right, it may collide with some future left-moving robot, so we push its index onto a stack.

The stack stores the most recent unresolved right-moving robots.

3. Resolve collisions when we see a left-moving robot

When we encounter a left-moving robot:

• it can only collide with right-moving robots already seen
• the most recent right-moving robot is the first possible collision
• that matches stack behavior perfectly

So while the stack is not empty and the current left-moving robot is still alive:

• compare current left-moving robot with stack top
• smaller health robot dies
• larger health robot loses 1
• equal health means both die

4. Build the answer in original order

At the end, any robot with health greater than 0 survived.

We collect those health values in the same order as the input arrays.

Why Stack Works

Suppose we sort by position and scan from left to right.

If we are currently at a robot moving left, the only robots it can collide with are right-moving robots that appeared before it.

Among those, the closest unresolved right-moving robot collides first, not an older one farther away.

That is exactly why stack is the right structure here.

This is very similar in spirit to Asteroid Collision:

• keep unresolved items on a stack
• resolve conflicts with the newest valid candidate first

Solution

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

class Solution {
  public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
    int n = positions.length;
    Integer[] indices = new Integer[n];
    int[] remainingHealths = Arrays.copyOf(healths, n);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
      indices[i] = i;
    }

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

    for (int currentIndex : indices) {
      if (directions.charAt(currentIndex) == 'R') {
        stack.push(currentIndex);
        continue;
      }

      while (!stack.isEmpty() && remainingHealths[currentIndex] > 0) {
        int topIndex = stack.pop();

        if (remainingHealths[topIndex] > remainingHealths[currentIndex]) {
          remainingHealths[topIndex] -= 1;
          remainingHealths[currentIndex] = 0;
          stack.push(topIndex);
        } else if (remainingHealths[topIndex] < remainingHealths[currentIndex]) {
          remainingHealths[currentIndex] -= 1;
          remainingHealths[topIndex] = 0;
        } else {
          remainingHealths[currentIndex] = 0;
          remainingHealths[topIndex] = 0;
        }
      }
    }

    List<Integer> survivors = new ArrayList<>();

    for (int i = 0; i < n; i++) {
      if (remainingHealths[i] > 0) {
        survivors.add(remainingHealths[i]);
      }
    }

    return survivors;
  }
}

Walkthrough

Take this example:

positions   = [3, 5, 2, 6]
healths     = [10, 10, 15, 12]
directions  = "RLRL"

Sorted by position, the robots appear in this order:

index 2 -> position 2 -> health 15 -> L
index 0 -> position 3 -> health 10 -> R
index 1 -> position 5 -> health 10 -> L
index 3 -> position 6 -> health 12 -> R

Now process:

1. Robot at index 2 moves left, but stack is empty, so no collision.
2. Robot at index 0 moves right, push to stack.
3. Robot at index 1 moves left, collide with stack top 0. Since healths are equal (10 vs 10), both die.
4. Robot at index 3 moves right, push to stack.

But note that index 2 was already alive on the far left and never had a right-moving robot to collide with after sorting order was respected.

Final survivors:

[14]

Complexity Analysis

Time Complexity: O(n log n)

• sorting indices costs O(n log n)
• the collision pass is O(n) because each robot is pushed and popped at most once

Space Complexity: O(n)

• indices array takes O(n)
• stack takes O(n) in the worst case
• copied health array takes O(n)

Common Mistakes

1. Processing in input order

This breaks collision order because robots interact based on position, not input index.

2. Forgetting repeated collisions

A strong left-moving robot can destroy multiple right-moving robots in sequence, so collision handling must stay inside a while loop, not just a single comparison.

3. Losing original order in the answer

Even though we sort by position for simulation, the final result must still be collected in the original input order.

My Take

The most important insight here is:

sort by position first, then use stack to resolve only meaningful collisions.

Without sorting, the simulation is messy. Without stack, collision chaining becomes awkward.

Together, they make the problem feel surprisingly clean for a hard question.

I followed the editorial direction here because the sorting + stack model is the core insight, and once that clicks, the implementation becomes very natural.

Related Problems

• Asteroid Collision — Medium
• Car Fleet — Medium
• Number of Visible People in a Queue — Hard