Problem Statement in English

You’re given three arrays: positions, healths, and directions.

Each robot is represented by its position, health, and direction. When two robots collide, the survivor loses 1 health point, and the loser is destroyed. If a robot survives it continues moving in its original direction, albeit with reduced health. If both robots have the same health, they both get destroyed.

You need to determine the health of the surviving robots after all collisions have occurred, in the order of their original indices. Return an array of the healths of the surviving robots, sorted by their original indices.

Approach

To solve this problem, we can use a stack to simulate the collisions between the robots.

Since we need to process the robots in the order of their positions, we will first sort the robots based on their positions. Then, we will iterate through the sorted list of robots and use a stack to keep track of the robots that are currently moving to the right (‘R’).

When we encounter a robot moving to the left (‘L’), we will check for collisions with the robots (the ones with direction ‘R’) in the stack. We will compare their healths and determine which robot survives or if both get destroyed. We will continue this process until there are no more collisions to resolve.

Finally, we will sort the surviving robots by their original indices and return their healths.

Solution in Python


class Solution:
    def survivedRobotsHealths(self, positions: List[int], healths: List[int], directions: str) -> List[int]:
        n = len(positions)
        # Create robots with (position, health, direction, original_index)
        robots = []
        for i in range(n):
            robots.append([positions[i], healths[i], directions[i], i])
        
        # Sort by position (essential for collision order)
        robots.sort()
        
        stack = [] # Will store [health, direction, original_index]
        
        for pos, health, direction, idx in robots:
            if direction == 'R':
                stack.append([health, direction, idx])
            else:
                # Collision logic for 'L' moving robot
                while stack and stack[-1][1] == 'R' and health > 0:
                    if stack[-1][0] < health:
                        stack.pop()
                        health -= 1
                    elif stack[-1][0] > health:
                        stack[-1][0] -= 1
                        health = 0
                    else:
                        stack.pop()
                        health = 0
                
                if health > 0:
                    stack.append([health, direction, idx])
        
        # Sort by original index to match required output format
        stack.sort(key=lambda x: x[2])
        
        return [x[0] for x in stack]

Complexity

  • Time: $O(n \log n)$
    Since we sort the robots by their positions and then sort the survivors by their original indices.

  • Space: $O(n)$
    Since we store the robots in a list and the stack can also grow up to size n in the worst case.

Mistakes I Made

I didn’t sort the robots by their position, which is crucial for determining the order of collisions 😬

And we are done.