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).
1import java.util.*;
2
3class RobotCollision {
4 public List<Integer> survivingRobotsHealth(int[] positions, int[] healths, String directions) {
5 int n = positions.length;
6 Integer[] indices = new Integer[n];
7 for (int i = 0; i < n; i++) indices[i] = i;
8 Arrays.sort(indices, Comparator.comparingInt(i -> positions[i]));
9
10 List<Integer> result = new ArrayList<>();
11 Deque<Integer> stack = new ArrayDeque<>();
12
13 boolean[] survivor = new boolean[n];
14 Arrays.fill(survivor, true);
15
16 for (int idx : indices) {
17 if (directions.charAt(idx) == 'R') {
18 stack.push(idx);
19 } else {
20 while (!stack.isEmpty() && healths[stack.peek()] < healths[idx]) {
21 int rIdx = stack.pop();
22 healths[idx]--;
23 survivor[rIdx] = false;
24 }
25 if (!stack.isEmpty() && healths[stack.peek()] == healths[idx]) {
26 survivor[stack.pop()] = false;
27 survivor[idx] = false;
28 } else if (!stack.isEmpty()) {
29 healths[stack.peek()]--;
30 survivor[idx] = false;
31 }
32 }
33 }
34
35 for (int i = 0; i < n; i++) {
36 if (survivor[i]) {
37 result.add(healths[i]);
38 }
39 }
40
41 return result;
42 }
43}This Java solution sorts the indices of robots based on their positions. It uses a stack to manage right-moving robots and iterates through. When a left-moving robot is encountered, it checks the stack for possible collisions, adjusting health values and survivors accordingly.
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.
1#include <stdbool.h>
2#include <stdio.h>
The C implementation applies a similar technique with simple structure-based sorting and a stack for managing collision simulations. It iterates through the sorted robots and adjusts survivors as necessary.