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 linesimultaneously 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.

Examples

Example 1

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2023/05/15/image-20230516011718-12.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

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2023/05/15/image-20230516004433-7.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

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2023/05/15/image-20230516005114-9.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 <= 10^5
  • 1 <= positions[i], healths[i] <= 10^9
  • directions[i] == 'L' or directions[i] == 'R'
  • All values in positions are distinct

Solution

Method 1 - Stack Simulation by Position

Intuition

Robots only collide when a right-moving robot meets a left-moving robot. By sorting robots by position and simulating their movement with a stack, we can efficiently process all collisions.

Approach

Sort robots by position, keeping track of their original indices. Use a stack to store right-moving robots. For each left-moving robot, pop from the stack and resolve collisions according to the rules. After all collisions, collect the healths of surviving robots in the original order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<int> survivedRobotsHealths(vector<int>& positions, vector<int>& healths, string directions) {
        int n = positions.size();
        vector<tuple<int, int, int, char>> robots;
        for (int i = 0; i < n; ++i)
            robots.emplace_back(positions[i], healths[i], i, directions[i]);
        sort(robots.begin(), robots.end());
        stack<int> stk; // store indices in robots
        vector<int> health(n);
        vector<bool> alive(n, true);
        for (int i = 0; i < n; ++i) health[i] = get<1>(robots[i]);
        for (int i = 0; i < n; ++i) {
            auto [pos, h, idx, dir] = robots[i];
            if (dir == 'R') stk.push(i);
            else {
                while (!stk.empty() && alive[i]) {
                    int j = stk.top();
                    if (!alive[j]) { stk.pop(); continue; }
                    if (health[j] < health[i]) {
                        alive[j] = false;
                        health[i]--;
                        stk.pop();
                    } else if (health[j] == health[i]) {
                        alive[j] = false;
                        alive[i] = false;
                        stk.pop();
                    } else {
                        health[j]--;
                        alive[i] = false;
                    }
                }
            }
        }
        vector<pair<int, int>> res;
        for (int i = 0; i < n; ++i) if (alive[i]) res.emplace_back(get<2>(robots[i]), health[i]);
        sort(res.begin(), res.end());
        vector<int> ans;
        for (auto& [idx, h] : res) ans.push_back(h);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import "sort"
func survivedRobotsHealths(positions []int, healths []int, directions string) []int {
    n := len(positions)
    type robot struct{pos, health, idx int; dir byte}
    robots := make([]robot, n)
    for i := 0; i < n; i++ {
        robots[i] = robot{positions[i], healths[i], i, directions[i]}
    }
    sort.Slice(robots, func(i, j int) bool { return robots[i].pos < robots[j].pos })
    stack := []int{}
    alive := make([]bool, n)
    for i := range alive { alive[i] = true }
    health := make([]int, n)
    for i := range health { health[i] = robots[i].health }
    for i, r := range robots {
        if r.dir == 'R' {
            stack = append(stack, i)
        } else {
            for len(stack) > 0 && alive[i] {
                j := stack[len(stack)-1]
                if !alive[j] { stack = stack[:len(stack)-1]; continue }
                if health[j] < health[i] {
                    alive[j] = false
                    health[i]--
                    stack = stack[:len(stack)-1]
                } else if health[j] == health[i] {
                    alive[j] = false
                    alive[i] = false
                    stack = stack[:len(stack)-1]
                } else {
                    health[j]--
                    alive[i] = false
                }
            }
        }
    }
    res := []struct{idx, h int}{ }
    for i := 0; i < n; i++ {
        if alive[i] { res = append(res, struct{idx, h int}{robots[i].idx, health[i]}) }
    }
    sort.Slice(res, func(i, j int) bool { return res[i].idx < res[j].idx })
    ans := []int{}
    for _, v := range res { ans = append(ans, v.h) }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.util.*;
class Solution {
    public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
        int n = positions.length;
        class Robot implements Comparable<Robot> {
            int pos, health, idx; char dir;
            Robot(int p, int h, int i, char d) { pos=p; health=h; idx=i; dir=d; }
            public int compareTo(Robot o) { return Integer.compare(this.pos, o.pos); }
        }
        Robot[] robots = new Robot[n];
        for (int i = 0; i < n; i++) robots[i] = new Robot(positions[i], healths[i], i, directions.charAt(i));
        Arrays.sort(robots);
        Deque<Integer> stack = new ArrayDeque<>();
        boolean[] alive = new boolean[n];
        Arrays.fill(alive, true);
        int[] health = new int[n];
        for (int i = 0; i < n; i++) health[i] = robots[i].health;
        for (int i = 0; i < n; i++) {
            if (robots[i].dir == 'R') stack.push(i);
            else {
                while (!stack.isEmpty() && alive[i]) {
                    int j = stack.peek();
                    if (!alive[j]) { stack.pop(); continue; }
                    if (health[j] < health[i]) {
                        alive[j] = false;
                        health[i]--;
                        stack.pop();
                    } else if (health[j] == health[i]) {
                        alive[j] = false;
                        alive[i] = false;
                        stack.pop();
                    } else {
                        health[j]--;
                        alive[i] = false;
                    }
                }
            }
        }
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < n; i++) if (alive[i]) res.add(new int[]{robots[i].idx, health[i]});
        res.sort(Comparator.comparingInt(a -> a[0]));
        List<Integer> ans = new ArrayList<>();
        for (int[] a : res) ans.add(a[1]);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.util.*
class Solution {
    fun survivedRobotsHealths(positions: IntArray, healths: IntArray, directions: String): List<Int> {
        data class Robot(val pos: Int, var health: Int, val idx: Int, val dir: Char)
        val n = positions.size
        val robots = List(n) { Robot(positions[it], healths[it], it, directions[it]) }.sortedBy { it.pos }
        val stack = ArrayDeque<Int>()
        val alive = BooleanArray(n) { true }
        val health = robots.map { it.health }.toMutableList()
        for (i in 0 until n) {
            if (robots[i].dir == 'R') stack.addLast(i)
            else {
                while (stack.isNotEmpty() && alive[i]) {
                    val j = stack.last()
                    if (!alive[j]) { stack.removeLast(); continue }
                    if (health[j] < health[i]) {
                        alive[j] = false
                        health[i]--
                        stack.removeLast()
                    } else if (health[j] == health[i]) {
                        alive[j] = false
                        alive[i] = false
                        stack.removeLast()
                    } else {
                        health[j]--
                        alive[i] = false
                    }
                }
            }
        }
        val res = mutableListOf<Pair<Int, Int>>()
        for (i in 0 until n) if (alive[i]) res.add(robots[i].idx to health[i])
        return res.sortedBy { it.first }.map { it.second }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

from typing import List
class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        n = len(positions)
        robots = sorted([(p, h, i, d) for i, (p, h, d) in enumerate(zip(positions, healths, directions))])
        stack = []
        alive = [True] * n
        health = [h for _, h, _, _ in robots]
        for i, (pos, h, idx, dir) in enumerate(robots):
            if dir == 'R':
                stack.append(i)
            else:
                while stack and alive[i]:
                    j = stack[-1]
                    if not alive[j]:
                        stack.pop()
                        continue
                    if health[j] < health[i]:
                        alive[j] = False
                        health[i] -= 1
                        stack.pop()
                    elif health[j] == health[i]:
                        alive[j] = False
                        alive[i] = False
                        stack.pop()
                    else:
                        health[j] -= 1
                        alive[i] = False
        res = [(robots[i][2], health[i]) for i in range(n) if alive[i]]
        res.sort()
        return [h for _, h in res]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

impl Solution {
    pub fn survived_robots_healths(positions: Vec<i32>, healths: Vec<i32>, directions: String) -> Vec<i32> {
        let n = positions.len();
        let mut robots: Vec<(i32, i32, usize, char)> = positions.into_iter().zip(healths).zip(directions.chars())
            .enumerate().map(|(i, ((p, h), d))| (p, h, i, d)).collect();
        robots.sort_by_key(|x| x.0);
        let mut stack: Vec<usize> = vec![];
        let mut alive = vec![true; n];
        let mut health: Vec<i32> = robots.iter().map(|x| x.1).collect();
        for i in 0..n {
            let dir = robots[i].3;
            if dir == 'R' {
                stack.push(i);
            } else {
                while let Some(&j) = stack.last() {
                    if !alive[i] { break; }
                    if !alive[j] { stack.pop(); continue; }
                    if health[j] < health[i] {
                        alive[j] = false;
                        health[i] -= 1;
                        stack.pop();
                    } else if health[j] == health[i] {
                        alive[j] = false;
                        alive[i] = false;
                        stack.pop();
                    } else {
                        health[j] -= 1;
                        alive[i] = false;
                    }
                }
            }
        }
        let mut res: Vec<(usize, i32)> = (0..n).filter(|&i| alive[i]).map(|i| (robots[i].2, health[i])).collect();
        res.sort_by_key(|x| x.0);
        res.into_iter().map(|x| x.1).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

function survivedRobotsHealths(positions: number[], healths: number[], directions: string): number[] {
    const n = positions.length;
    const robots = positions.map((p, i) => ({pos: p, health: healths[i], idx: i, dir: directions[i]}));
    robots.sort((a, b) => a.pos - b.pos);
    const stack: number[] = [];
    const alive = Array(n).fill(true);
    const health = robots.map(r => r.health);
    for (let i = 0; i < n; i++) {
        if (robots[i].dir === 'R') {
            stack.push(i);
        } else {
            while (stack.length && alive[i]) {
                const j = stack[stack.length - 1];
                if (!alive[j]) { stack.pop(); continue; }
                if (health[j] < health[i]) {
                    alive[j] = false;
                    health[i]--;
                    stack.pop();
                } else if (health[j] === health[i]) {
                    alive[j] = false;
                    alive[i] = false;
                    stack.pop();
                } else {
                    health[j]--;
                    alive[i] = false;
                }
            }
        }
    }
    const res: {idx: number, h: number}[] = [];
    for (let i = 0; i < n; i++) if (alive[i]) res.push({idx: robots[i].idx, h: health[i]});
    res.sort((a, b) => a.idx - b.idx);
    return res.map(x => x.h);
}

Complexity

  • ⏰ Time complexity: O(n log n) — for sorting, and each robot is processed at most once in the stack.
  • 🧺 Space complexity: O(n) — for storing robot info and stack.