Robot Collisions

Hard
1412.

Robot Collisions

Robot Collisions is a hard coding problem on arrays, sorting and simulation, asked in Amazon, Google and Meta interviews.

There are n robots on a line, numbered 0 to n - 1. Robot i starts at positions[i] (all positions are distinct), has health healths[i], and moves at the same constant speed in direction directions[i] — 'L' for left or 'R' for right. All robots start moving at the same moment.

When two robots meet, they collide: the one with the lower health is destroyed and the other loses 1 health and keeps moving in its direction. If both have the same health, both are destroyed.

Return the healths of the robots that survive once no more collisions can happen, listed in the order of their original indices (robot 0 first). Return an empty array if none survive.

Example 1

Input
positions = [2,8,5], healths = [4,7,3], directions = "RLR"
Output
[5]
Explanation
Robot 2 (at 5, moving right) meets robot 1 first and is destroyed; robot 1 drops to 6, then destroys robot 0 and ends with 5.

Example 2

Input
positions = [1,4], healths = [9,9], directions = "RL"
Output
[]

Example 3

Input
positions = [10,3,7], healths = [5,6,2], directions = "LLR"
Output
[4,6]
Explanation
Robot 2 crashes into robot 0, which survives with 4; robot 1 drives off to the left untouched.

Constraints

  • 1 <= positions.length == healths.length == directions.length <= 10^5
  • 1 <= positions[i], healths[i] <= 10^9
  • directions[i] is 'L' or 'R'
  • All values in positions are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} positions
 * @param {number[]} healths
 * @param {string} directions
 * @return {number[]}
 */
var survivedRobotsHealths = function(positions, healths, directions) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Robot Collisions — Solution in Python, Java & C++

Robot Collisions solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and sorting.

Robot Collisions is a hard coding problem on arrays, sorting and simulation, asked in Amazon, Google and Meta interviews.

  • Difficulty: Hard
  • Topics: Arrays, Sorting, Simulation, Stack
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n robots on a line, numbered 0 to n - 1. Robot i starts at positions[i] (all positions are distinct), has health healths[i], and moves at the same constant speed in direction directions[i] — 'L' for left or 'R' for right. All robots start moving at the same moment.

When two robots meet, they collide: the one with the lower health is destroyed and the other loses 1 health and keeps moving in its direction. If both have the same health, both are destroyed.

Return the healths of the robots that survive once no more collisions can happen, listed in the order of their original indices (robot 0 first). Return an empty array if none survive.

Example 1

Input: positions = [2,8,5], healths = [4,7,3], directions = "RLR"
Output: [5]
Explanation: Robot 2 (at 5, moving right) meets robot 1 first and is destroyed; robot 1 drops to 6, then destroys robot 0 and ends with 5.

Example 2

Input: positions = [1,4], healths = [9,9], directions = "RL"
Output: []

Example 3

Input: positions = [10,3,7], healths = [5,6,2], directions = "LLR"
Output: [4,6]
Explanation: Robot 2 crashes into robot 0, which survives with 4; robot 1 drives off to the left untouched.

Constraints

  • 1 <= positions.length == healths.length == directions.length <= 10^5
  • 1 <= positions[i], healths[i] <= 10^9
  • directions[i] is 'L' or 'R'
  • All values in positions are distinct.

Hints for Robot Collisions

  1. Hint 1

    Only a right-mover with a left-mover somewhere to its right can ever collide. Process the robots from left to right in position order.

  2. Hint 2

    Right-movers wait on a stack. A left-mover crashes into the nearest waiting right-mover first — the top of the stack.

  3. Hint 3

    Resolve the fight at the top repeatedly: the loser leaves (pop the stack or stop the left-mover), the winner loses 1 health, and continue while the left-mover is alive and the stack is non-empty.

How to solve Robot Collisions

This is asteroid collision with health. Sorted by position, a left-moving robot meets the right-moving robots to its left from nearest to farthest — exactly the order of a stack.

Approach

  1. Sort robot indices by position; copy the healths so they can be decreased.
  2. Scan in position order. Push every right-mover onto a stack.
  3. For a left-mover i, while it is alive and the stack is non-empty, fight the top j: if h[j] < h[i], destroy j (pop) and decrement h[i]; if h[j] > h[i], destroy i and decrement h[j]; if equal, destroy both.
  4. Finally list the positive healths in original index order.

Why it works

Between a right-mover j on the stack and a left-mover i, every robot that was ever between them has already been destroyed (otherwise j would not be on top), so i and j are the next pair to meet. Collisions of disjoint pairs do not interact, so resolving them in this order produces the same survivors as the real timeline. A surviving left-mover with an empty stack escapes, and right-movers left on the stack never meet anything.

Complexity

  • Time — O(n log n) for the sort; the stack phase is O(n)
  • Space — O(n)

Pitfalls

  • The input is not sorted by position — sort indices, but report in the original order.
  • A winning robot loses exactly 1 health per collision, not the loser's health.
  • Equal healths destroy both robots; make sure the left-mover stops fighting then.

Reference solution

Python

from typing import List

def survivedRobotsHealths(positions: List[int], healths: List[int], directions: str) -> List[int]:
    n = len(positions)
    h = list(healths)
    order = sorted(range(n), key=lambda i: positions[i])
    st = []
    for i in order:
        if directions[i] == 'R':
            st.append(i)
            continue
        while st and h[i] > 0:
            j = st[-1]
            if h[j] < h[i]:
                h[j] = 0
                st.pop()
                h[i] -= 1
            elif h[j] > h[i]:
                h[j] -= 1
                h[i] = 0
            else:
                h[j] = 0
                h[i] = 0
                st.pop()
    return [x for x in h if x > 0]

Java

public static int[] survivedRobotsHealths(int[] positions, int[] healths, String directions) {
    int n = positions.length;
    int[] h = healths.clone();
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(positions[a], positions[b]));
    int[] st = new int[n];
    int top = 0;
    for (int k = 0; k < n; k++) {
        int cur = order[k];
        if (directions.charAt(cur) == 'R') { st[top++] = cur; continue; }
        while (top > 0 && h[cur] > 0) {
            int j = st[top - 1];
            if (h[j] < h[cur]) { h[j] = 0; top--; h[cur]--; }
            else if (h[j] > h[cur]) { h[j]--; h[cur] = 0; }
            else { h[j] = 0; h[cur] = 0; top--; }
        }
    }
    int cnt = 0;
    for (int x : h) if (x > 0) cnt++;
    int[] res = new int[cnt];
    int p = 0;
    for (int x : h) if (x > 0) res[p++] = x;
    return res;
}

C++

vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) {
    int n = positions.size();
    vector<int> h = healths;
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) { return positions[a] < positions[b]; });
    vector<int> st;
    for (int cur : order) {
        if (directions[cur] == 'R') { st.push_back(cur); continue; }
        while (!st.empty() && h[cur] > 0) {
            int j = st.back();
            if (h[j] < h[cur]) { h[j] = 0; st.pop_back(); h[cur]--; }
            else if (h[j] > h[cur]) { h[j]--; h[cur] = 0; }
            else { h[j] = 0; h[cur] = 0; st.pop_back(); }
        }
    }
    vector<int> res;
    for (int x : h) if (x > 0) res.push_back(x);
    return res;
}

JavaScript

var survivedRobotsHealths = function(positions, healths, directions) {
    var n = positions.length;
    var h = healths.slice();
    var order = [];
    for (var i = 0; i < n; i++) order.push(i);
    order.sort(function(a, b) { return positions[a] - positions[b]; });
    var st = [];
    for (var k = 0; k < n; k++) {
        var cur = order[k];
        if (directions[cur] === "R") { st.push(cur); continue; }
        while (st.length > 0 && h[cur] > 0) {
            var j = st[st.length - 1];
            if (h[j] < h[cur]) { h[j] = 0; st.pop(); h[cur]--; }
            else if (h[j] > h[cur]) { h[j]--; h[cur] = 0; }
            else { h[j] = 0; h[cur] = 0; st.pop(); }
        }
    }
    var res = [];
    for (var t = 0; t < n; t++) if (h[t] > 0) res.push(h[t]);
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms