Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

With equal speeds, collisions occur only between a right-moving robot and a later left-moving robot in position order. The nearest unresolved right-moving robot is encountered first, so a stack can process collisions without computing their times.

Approach

Sort robot records by position while retaining original indices. Push right-moving robots. For a left-moving robot, repeatedly compare its health with a right-moving stack top: equal health destroys both; greater stack health survives minus one and destroys the newcomer; greater newcomer health removes the top and continues with one less health. Push the newcomer if it survives. Finally sort survivors by original index and return their remaining healths. Each collision removes at least one robot, bounding total collision work.

class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        n = len(positions)
        arr = []
        s = []

        for i in range(n):
            arr.append([i, positions[i], healths[i], directions[i]])
        arr.sort(key = lambda x: x[1])

        for i in range(n):
            idx, p, h, d = arr[i]
            if d == 'R':
                s.append([idx, p, h, d])
            else:
                while s and s[-1][3] == 'R':
                    if s[-1][2] == h:
                        s.pop()
                        h = 0
                        break
                    elif s[-1][2] > h:
                        s[-1][2] -= 1
                        h = 0
                        break
                    else:
                        s.pop()
                        h -= 1
                if h > 0:
                    s.append([idx, p, h, d])

        s.sort(key = lambda x: x[0])
        res = []
        for idx, p, h, d in s:
            res.append(h)

        return res

Complexity analysis

Let n = positions.length. Time: O(n log n) for position ordering and restoring original order; collision processing is amortized O(n). Auxiliary space: O(n) for robot records and the survivor stack.