By Expert Funda Wednesday, April 1, 2026

LeetCode 2751 – Robot Collisions

LeetCode 2751 – Robot Collisions | ExpertFunda

ExpertFunda › LeetCode Solutions › 2751 · Robot Collisions Java · Stack · Sorting

#2751

Robot Collisions

Hard Stack Array Sorting Simulation Weekly Contest 351

Acceptance ~52% Time O(n log n) Space O(n) Companies Google · Amazon

Problem Statement

There are n robots, each numbered from 1 to n. You are given 0-indexed integer arrays positions, healths, and a string directions. All integers in positions are unique.

All robots start moving simultaneously at the same speed in their given directions. If two robots ever share the same position, a collision takes place with the following rules:

• The robot with lower health is removed. The surviving robot's health decreases by 1.
• If both robots have equal health, both are removed.

Return an array of the healths of the remaining robots after all collisions, in the order they were given. If no robots remain, return an empty array.

Example 1

Input: positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRSLLS"

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

Output: [14] // only robot at pos 3 survives

Example 2 — your test case

Input: positions = [1,40], healths = [10,11], directions = "RL"

Output: [10] // Robot 1 (hp=11) beats Robot 0 (hp=10), survives with hp=10

Constraints

1 ≤ n ≤ 10⁵
1 ≤ positions[i], healths[i] ≤ 10⁹
directions[i] is either 'L' or 'R'
All values in positions are distinct

Intuition

Key insight: Only a robot moving right can collide with a robot moving left that arrives from ahead of it. Two robots going the same direction never collide. This is the classic "asteroids"-style stack problem.

Think of the stack as a waiting room for right-movers. Every robot going R sits in the waiting room. When a L-mover arrives, it is on a collision course with whoever is at the front of that room.

The left-mover keeps fighting until one of three things happens:

💥

L loses

R-mover hp>L-mover hp
R loses 1, L dies (hp=0)

💥

L wins

L-mover hp>R-mover hp
R dies (hp=0, popped), L loses 1

💥

Both die

Equal hp
Both set to 0, R popped

Critical bug to avoid: When the right-mover loses, you must set healths[top] = 0 before popping. The final collection loop checks healths[i] > 0 — if you forget to zero it, a dead right-mover gets counted as a survivor.

Step-by-Step Simulation

Using Example 2: positions=[1,40], healths=[10,11], directions="RL"

Sort by position → process R0 first (pos=1)

→ R0 hp=10

pos 1

···

← R1 hp=11

pos 40

Stack after step: R0 hp=10

R0 direction is 'R' — push to stack. Stack = [R0].

Process R1 (pos=40, dir=L) → collision detected!

→ R0 hp=10

in stack

vs
⚡

← R1 hp=11

current

R1 is 'L', stack top is R0 ('R'). Compare: R0 hp=10 vs R1 hp=11. R1 is stronger → R0 eliminated.

R1 wins — R0 destroyed, R1 hp drops by 1

R0 hp=0 ✕

dead

← R1 hp=10

survivor

Stack after step: (empty)

healths[R0] = 0 (zeroed + popped) | healths[R1] = 11 - 1 = 10. Stack empty → loop exits.

Collect survivors in original index order

i=0 → healths[0]=0 → skip

i=1 → healths[1]=10 → include

Output: [10]

Execution Trace Table

Step	Current robot	Stack top	Comparison	Action	Stack state
1	R0 (R, hp=10)	—	direction = R	PUSH R0	[R0]
2	R1 (L, hp=11)	R0 (hp=10)	11 > 10	R1 wins, R0 hp=0, POP	[]
3	R1 (L, hp=10)	—	stack empty	—	[]
4	Collect: healths[0]=0 (skip), healths[1]=10 → result = [10]

Java Solution

Java

class Solution {
    public List<Integer> survivedRobotsHealths(
            int[] positions, int[] healths, String directions) {

        int n = positions.length;

        // Step 1: create index array and sort by position
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> positions[a] - positions[b]);

        // Step 2: stack stores indices of right-moving robots
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i : idx) {
            if (directions.charAt(i) == 'R') {
                stack.push(i);       // right-mover: wait in stack

            } else {              // left-mover: fight stack top
                while (!stack.isEmpty() && healths[i] > 0) {
                    int top = stack.peek();

                    if (healths[top] > healths[i]) {
                        healths[top]--;
                        healths[i] = 0;         // L-mover dies

                    } else if (healths[top] < healths[i]) {
                        healths[i]--;
                        healths[top] = 0;       // ← FIX: zero before pop!
                        stack.pop();

                    } else {
                        healths[i]   = 0;
                        healths[top] = 0;       // ← FIX: zero before pop!
                        stack.pop();
                    }
                }
            }
        }

        // Step 3: collect survivors — anyone with hp > 0
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++)
            if (healths[i] > 0) result.add(healths[i]);

        return result;
    }
}
        

Complexity Analysis

Time complexity

O(n log n)

Dominated by the sort step. Each robot enters/leaves the stack at most once → collision loop is O(n) amortized.

Space complexity

O(n)

Index array + stack each hold at most n elements. Result list holds surviving robots.

Why not O(n²)? Although we have a nested while loop, each robot is pushed and popped from the stack at most once. Total stack operations across all robots = O(n). This is the amortized argument that keeps the overall complexity at O(n) for the collision phase.

Alternative Approaches

Stack (optimal) Recommended O(n log n) / O(n)

Sort by position, push right-movers, resolve left-movers greedily against the stack top. Each robot touches the stack once.

Clean O(n) collision step
Each robot enters stack once
Straightforward to implement

Sorting needed upfront
Index-tracking is tricky

Brute-force simulation TLE O(n² × max_hp) / O(n)

Actually simulate each time step: move all robots, detect adjacency collisions, resolve, repeat. Maps directly to the problem statement.

Very easy to reason about
Matches problem description 1:1

Extremely slow for large inputs
Depends on max health value

Priority queue Overkill O(n log n) / O(n)

Use a max-heap to always process the highest-health robot first. Generalizes to harder variants where order changes dynamically.

Generalizes to harder variants
Natural priority ordering

Overcomplicated for this problem
Hard to preserve original order

Common Mistakes

Forgetting healths[top] = 0 before popping

When the right-mover loses, just calling stack.pop() removes it from future collisions but leaves its health positive. The final loop then incorrectly includes it as a survivor. Always zero the health before popping.

Processing in input order instead of position order

Robots must be processed left-to-right by position, not by their original index. Sort by positions[i] first, then process. Skipping the sort produces wrong collision sequencing.

Returning result in sorted order, not original index order

The final collection loop must iterate from i=0 to n-1 (original indices), not over the sorted index array. The problem explicitly asks for the order they were given.

Tags:

Continue Reading →