Sponsored
Sponsored
This approach involves sorting the robots based on their positions so that we can simulate their movements along the line. We utilize a stack to keep track of the robots moving rightward. When a robot moving left encounters one or more robots on the stack, a collision is detected, and their healths are compared to determine the outcome.
Time Complexity: O(n log n) due to sorting the list of robots.
Space Complexity: O(n) because of the additional data structures used (stack and survivor list).
1def surviving_robots_health(positions, healths, directions):
2 robots = sorted(zip(positions, healths, directions, range(len(positions))), key=lambda x: x[0])
3 survivors = [True] * len(robots)
4 stack = [] # this will store indices of robots moving 'R'
5
6 for _, health, direction, index in robots:
7 if direction == 'R':
8 stack.append((health, index))
9 else:
10 while stack and stack[-1][0] < health:
11 health -= 1
12 prev_health, prev_index = stack.pop()
13 survivors[prev_index] = False
14 if stack:
15 if stack[-1][0] == health:
16 survivors[stack.pop()[1]] = False
17 survivors[index] = False
18 else:
19 stack[-1] = (stack[-1][0] - 1, stack[-1][1])
20 survivors[index] = False
21
22 return [h for (_, h, _, i), s in zip(robots, survivors) if s]The function first combines the input into a list of tuples and sorts it based on positions. For each robot, if it's moving right, its index is pushed onto a stack. When a left-moving robot encounters right-moving ones, collisions occur, and appropriate robots are removed based on their healths.
This approach simulates the collision process using a two-pointer technique. Each pointer represents a different direction of movement. By carefully checking each pair of robots, we can simulate their interactions and resolve collisions by adjusting health values and determining survivors.
Time Complexity: O(n log n) due to sorting the positions.
Space Complexity: O(n) due to extra data structures for handling collisions.
1function survivingRobotsHealth(positions, healths, directions) {
2
This solution leverages a two-pointer-like mechanism where rightward-moving robots are managed with a stack. As each leftward-moving robot approaches, they are compared against the stack, with resulting health and survival adjustments.