We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Robot Collisions

Difficulty: Hard

Problem Description

You are given n robots, each having a position on a line, health, and movement direction. You need to determine the health of the robots that survive collisions, in the same order they were given. If two robots collide, the robot with lower health is removed, and the other loses 1 health. If both have the same health, both are removed.

Key Insights

  • Robots move simultaneously in their specified directions.
  • Collisions only occur between robots moving towards each other (R and L).
  • When a collision occurs, the robot with lower health is removed, and the other loses health.
  • The final health of surviving robots must be returned in the order they were given.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the positions. Space Complexity: O(n) - for the stack to keep track of surviving robots.

Solution

The approach involves:

  1. Pairing each robot's position, health, and direction into a tuple.
  2. Sorting the robots by their position to handle collisions efficiently.
  3. Using a stack to keep track of surviving robots:
    • Traverse the sorted robots and process collisions based on their directions.
    • If a robot moving right (R) meets a robot moving left (L), determine the outcome based on their health.
    • Continue processing until all possible collisions are resolved.
  4. The remaining robots in the stack are the survivors, and their health is returned in the original order.

Code Solutions

def robotCollisions(positions, healths, directions):
    robots = sorted(zip(positions, healths, directions))
    stack = []
    
    for pos, health, dir in robots:
        if dir == 'R':
            stack.append([health])  # Push health of robot moving right
        else:  # dir == 'L'
            while stack and stack[-1][0] > 0:  # Resolve collisions
                if stack[-1][0] < health:
                    health -= 1
                    stack.pop()  # Remove the weaker robot
                elif stack[-1][0] == health:
                    stack.pop()  # Both robots are removed
                    health = -1  # Mark for removal
                    break
                else:
                    health = -1  # Current robot removed
                    break
            if health > 0:
                stack.append([health])  # Surviving robot moving left
    
    return [h[0] for h in stack]
← Back to All Questions