Movement of Robots

Movement of Robots

What is this problem about?

The Movement of Robots problem places robots on a number line, each moving either left or right. When two robots collide, they both reverse direction. Find the sum of absolute distances between all pairs of robots after d seconds. This Movement of Robots coding problem uses the classic "robots pass through each other" observation combined with prefix sums for efficient pair-distance computation.

Why is this asked in interviews?

Meta and Google ask this medium problem because it requires the non-obvious insight that colliding robots are equivalent to robots passing through each other — only the relative order of positions changes. After this observation, compute final positions, sort them, and use prefix sums to compute all pairwise distances efficiently. The brainteaser, array, sorting, and prefix sum interview pattern is showcased.

Algorithmic pattern used

Position-passing observation + prefix sum pair distances. When robots collide and reverse, it's equivalent to them passing through each other (only their "labels" switch). So compute each robot's final position directly: pos + d (if moving right) or pos - d (if moving left). Sort final positions. The sum of all pairwise absolute distances: sum_{i<j} |pos[i] - pos[j]| = for each j, contribute pos[j] * j - prefixSum[j]. Compute using prefix sums.

Example explanation

Robots: [-2, 0, 2], directions: [right, left, left]. d=3.

• Final positions: -2+3=1, 0-3=-3, 2-3=-1. Sorted: [-3, -1, 1].
• Pairwise distances: |-3-(-1)|=2, |-3-1|=4, |-1-1|=2. Sum = 8. Using prefix sum: at index 1, pos=-1, prefix=sum([-3])=-3. Contribution = -1*1 - (-3) = 2. Etc.

Common mistakes candidates make

• Simulating actual robot collisions (O(n²) or worse).
• Not recognizing the passing-through equivalence.
• Forgetting to sort positions before applying the prefix sum formula.
• Modular arithmetic errors (problem often requires answer mod 10^9+7).

Interview preparation tip

The "robots reverse = robots pass through" insight is a classic brainteaser that reduces a complex simulation to a simple formula. After learning this, practice the prefix sum formula for sum of all pairwise distances in a sorted array: sum_{j} (pos[j] * j - prefixSum[j]). This formula appears in many geometry and sorting problems. Recognizing the brainteaser observation is the hard part; the prefix sum computation is standard. Practice both independently.