Robot Collisions

Intuition #

We have a bunch of robots that are moving in a horizontal line going either left (L), or right (R).

Robots are numbered from 1 until n.

Robot 1 is at position[0] with health[0] and direction[0]. Since each robot might differ in position, that means the positions array might not be ordered.

At first we need to order the arrays and keep hold the original index since the result array require us to return in the same order that the robots were given.

To do that we can create a new struct that will hold the index (original index), position, health, and direction.

Then we can join all the robots data into one array of type that holds the newly struct for each robot, and go on and solve the problem.

To solve the problem we can, iterate over and over and over until there’s no more collision, but that will be inefficient because of the constraints.

Can we think of an efficient solution? If each robots are moving at the same time and they differ by a fixed position, the only robots that will collide are the robots that are going L and the one that are going R towards it.

--Robot 1--> <--Robot 2-- (Collision)
<--Robot 1-- --Robot 2--> (No Collision)
<--Robot 1-- <--Robot 2-- (No Collision)
--Robot 1--> --Robot 2--> (No Collision)

The only time that a collision happens is when the left robot is going to the right and the right robot is going to the left.

We can then use a stack to keep track of the top robot and the next robot.

Why we can use a stack? We can since the robots are moving at the same speed.

Then when do we update the stack? When we only have the top of the stack going right and the next robot is going left, like the first line in the diagram.

Approach #

• Create a robot struct with fields: index, position, health, and direction.
• Create a list robots of size n.
• Loop i from 0 to len(positions) - 1:
  • Set dir to 1. (1 means going right).
  • If directions[i] == 'L', set dir to -1.
  • Create a robot with:
    • index = i + 1
    • position = positions[i]
    • health = healths[i]
    • direction = dir
  • Append robot to robots.
• Sort robots by position in increasing order.
• Create an empty stack.
• Loop over each robot r in robots:
  • If r.direction == 1:
    • Push r onto the stack.
    • Continue to next robot.
  • Set toAdd = r.
  • While stack is not empty:
    • Let top be the last element of the stack.
    • If top.direction != 1:
      • Break the loop.
    • Pop top from the stack.
    • If top.health > toAdd.health:
      • Decrease top.health by 1.
      • Set toAdd = top.
      • Break the loop.
    • Else if top.health < toAdd.health:
      • Decrease toAdd.health by 1.
      • Continue the loop.
    • Else (equal health):
      • Set both top.health and toAdd.health to 0.
      • Set toAdd = nil.
      • Break the loop.
  • If toAdd is not nil:
    • Push toAdd onto the stack.
• Sort stack by original index in increasing order.
• Create result array of size equal to stack length.
• Loop i from 0 to len(stack) - 1:
  • Set result[i] = stack[i].health.
• Return result.

Complexity #

• Time complexity: $O(NLog(N))$

  • Going through the input is $O(N)$.
  • Sorting the created robots and stack arrays is $O(NLog(N))$.

• Space complexity: $O(N)$

  • The required space for the robots and stack array is $O(N)$.

Code #

 1import "slices"
 2
 3type robot struct {
 4	index     int
 5	position  int
 6	health    int
 7	direction int
 8}
 9
10func survivedRobotsHealths(positions []int, healths []int, directions string) []int {
11	robots := make([]*robot, 0, len(positions))
12	for i := range positions {
13		dir := 1 // Right
14		if directions[i] == 'L' {
15			dir = -1
16		}
17
18		r := &robot{
19			index:     i + 1,
20			position:  positions[i],
21			health:    healths[i],
22			direction: dir,
23		}
24
25		robots = append(robots, r)
26	}
27	slices.SortFunc(robots, func(a, b *robot) int {
28		return a.position - b.position
29	})
30
31	stack := make([]*robot, 0, len(robots))
32	for _, r := range robots {
33		// ->
34		if r.direction == 1 {
35			stack = append(stack, r)
36			continue
37		}
38
39		toAdd := r
40		for len(stack) > 0 {
41			top := stack[len(stack)-1]
42
43			// -> <-
44			if top.direction == 1 {
45				stack = stack[:len(stack)-1]
46
47				// -> greater than <-
48				if top.health > toAdd.health {
49					top.health -= 1
50					toAdd = top
51					break
52				} else if top.health < toAdd.health {
53					toAdd.health -= 1
54				} else { // ==
55					// Drop both
56					toAdd.health = 0
57					top.health = 0
58					toAdd = nil
59					break
60				}
61			} else { // <-
62				break
63			}
64		}
65
66		if toAdd != nil {
67			stack = append(stack, toAdd)
68		}
69	}
70
71	slices.SortFunc(stack, func(a, b *robot) int {
72		return a.index - b.index
73	})
74
75	result := make([]int, len(stack))
76	for i, r := range stack {
77		result[i] = r.health
78	}
79
80	return result
81}