2751. Robot Collisions

/**
 * Problem: LeetCode 2751 - Robot Collisions
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

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 robot positions in ascending order
        Arrays.sort(indices, (a, b) -> Integer.compare(positions[a], positions[b]));

        Deque<Integer> stack = new ArrayDeque<>(); // stores indices of 'R' moving robots

        for (int curr : indices) {
            if (directions.charAt(curr) == 'R') {
                stack.push(curr);
            } else {
                // Robot moving 'L' collides with any 'R' robots encountered so far
                while (!stack.isEmpty() && healths[curr] > 0) {
                    int top = stack.peek();
                    if (healths[top] < healths[curr]) {
                        healths[top] = 0;
                        stack.pop();
                        healths[curr] -= 1;
                    } else if (healths[top] > healths[curr]) {
                        healths[curr] = 0;
                        healths[top] -= 1;
                    } else {
                        // Equal health: both robots eliminated
                        healths[top] = 0;
                        healths[curr] = 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;
    }
}

"""
Problem: LeetCode 2751 - Robot Collisions
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List


class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        n = len(positions)
        indices = sorted(range(n), key=lambda i: positions[i])
        stack = []  # stores indices of robots moving 'R'

        for curr in indices:
            if directions[curr] == 'R':
                stack.append(curr)
            else:
                # Robot moving 'L' collides with any 'R' robots in stack
                while stack and healths[curr] > 0:
                    top = stack[-1]
                    if healths[top] < healths[curr]:
                        healths[top] = 0
                        stack.pop()
                        healths[curr] -= 1
                    elif healths[top] > healths[curr]:
                        healths[curr] = 0
                        healths[top] -= 1
                    else:
                        healths[top] = 0
                        healths[curr] = 0
                        stack.pop()

        return [healths[i] for i in range(n) if healths[i] > 0]

/**
 * Problem: LeetCode 2751 - Robot Collisions
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>

using namespace std;

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);

        // Sort indices by positions ascending
        sort(indices.begin(), indices.end(), [&](int a, int b) {
            return positions[a] < positions[b];
        });

        vector<int> st; // stack storing indices of 'R' moving robots

        for (int curr : indices) {
            if (directions[curr] == 'R') {
                st.push_back(curr);
            } else {
                // Robot moving 'L' collides with 'R' robots in stack
                while (!st.empty() && healths[curr] > 0) {
                    int top = st.back();
                    if (healths[top] < healths[curr]) {
                        healths[top] = 0;
                        st.pop_back();
                        healths[curr] -= 1;
                    } else if (healths[top] > healths[curr]) {
                        healths[curr] = 0;
                        healths[top] -= 1;
                    } else {
                        healths[top] = 0;
                        healths[curr] = 0;
                        st.pop_back();
                    }
                }
            }
        }

        vector<int> result;
        for (int i = 0; i < n; i++) {
            if (healths[i] > 0) {
                result.push_back(healths[i]);
            }
        }
        return result;
    }
};

/**
 * Problem: LeetCode 2751 - Robot Collisions
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[]} positions
 * @param {number[]} healths
 * @param {string} directions
 * @return {number[]}
 */
var survivedRobotsHealths = function(positions, healths, directions) {
    const n = positions.length;
    const indices = Array.from({ length: n }, (_, i) => i);
    indices.sort((a, b) => positions[a] - positions[b]);

    const stack = []; // stores indices of robots moving 'R'

    for (const curr of indices) {
        if (directions[curr] === 'R') {
            stack.push(curr);
        } else {
            // Robot moving 'L' collides with 'R' robots in stack
            while (stack.length > 0 && healths[curr] > 0) {
                const top = stack[stack.length - 1];
                if (healths[top] < healths[curr]) {
                    healths[top] = 0;
                    stack.pop();
                    healths[curr] -= 1;
                } else if (healths[top] > healths[curr]) {
                    healths[curr] = 0;
                    healths[top] -= 1;
                } else {
                    healths[top] = 0;
                    healths[curr] = 0;
                    stack.pop();
                }
            }
        }
    }

    const result = [];
    for (let i = 0; i < n; i++) {
        if (healths[i] > 0) {
            result.push(healths[i]);
        }
    }
    return result;
};