2751. Robot Collisions

Array
Stack
Sorting
Simulation

TIME

O(n log n)

SPACE

O(n)

Intuition

Similar to asteroid collision problems. Robots only collide when one moves right ('R') and another moves left ('L'). Use a stack to track right-moving robots and simulate collisions when a left-moving robot appears.

Solution

Step 1: Sort by Position

Collisions depend on spatial order, so sort robots by position while keeping track of original indices.

Step 2: Use Stack for Right-Moving Robots

Push indices of 'R' robots onto stack
When encountering an 'L' robot, check for collisions with stack top

Step 3: Collision Simulation

While stack is not empty and current 'L' robot is alive:

Case 1: Right robot health < Left robot health

Right robot removed (pop stack, set health to 0)
Left robot health -= 1
Continue checking next right robot

Case 2: Right robot health > Left robot health

Left robot removed (set health to 0)
Right robot health -= 1
Stop (left robot is gone)

Case 3: Equal health

Both removed (pop stack, both healths to 0)
Stop

Step 4: Collect Survivors

Iterate through original order and collect robots with health > 0.

Complexity

Time: O(n log n), sorting dominates; each robot pushed/popped at most once
Space: O(n), stack and sorting

Edge Cases

All same direction → no collisions
All collide → empty result
Single robot → return its health
Alternating R-L pattern → chain collisions

Code

from typing import List


class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        """
        2751. Robot Collisions
        Time: O(n log n)
        Space: O(n)
        """
        n = len(positions)

        robots = sorted([(positions[i], i) for i in range(n)])

        stack = []

        for _, i in robots:
            if directions[i] == 'R':
                stack.append(i)
            else:
                while stack and healths[i] > 0:
                    j = stack[-1]

                    if healths[j] < healths[i]:
                        healths[i] -= 1
                        healths[j] = 0
                        stack.pop()
                    elif healths[j] > healths[i]:
                        healths[j] -= 1
                        healths[i] = 0
                        break
                    else:
                        healths[j] = 0
                        healths[i] = 0
                        stack.pop()
                        break

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

import java.util.*;

/**
 * 2751. Robot Collisions
 * Time: O(n log n)
 * Space: O(n)
 */
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, (a, b) -> positions[a] - positions[b]);

        Stack<Integer> stack = new Stack<>();

        for (int idx : indices) {
            if (directions.charAt(idx) == 'R') {
                stack.push(idx);
            } else {
                while (!stack.isEmpty() && healths[idx] > 0) {
                    int top = stack.peek();

                    if (healths[top] < healths[idx]) {
                        healths[idx]--;
                        healths[top] = 0;
                        stack.pop();
                    } else if (healths[top] > healths[idx]) {
                        healths[top]--;
                        healths[idx] = 0;
                        break;
                    } else {
                        healths[top] = 0;
                        healths[idx] = 0;
                        stack.pop();
                        break;
                    }
                }
            }
        }

        List<Integer> result = new ArrayList<>();
        for (int h : healths) {
            if (h > 0) result.add(h);
        }

        return result;
    }
}