Some robots are standing on an infinite number line with their initial coordinates given by a 0-indexed integer array nums and will start moving once given the command to move. The robots will move a unit distance each second.
You are given a string s denoting the direction in which robots will move on command. 'L' means the robot will move towards the left side or negative side of the number line, whereas 'R' means the robot will move towards the right side or positive side of the number line.
If two robots collide, they will start moving in opposite directions.
Return the sum of distances between all the pairs of robots d seconds after the command. Since the sum can be very large, return it modulo 109 + 7.
Note:
i and j, pair (i,j) and pair (j,i) are considered the same pair.Example 1:
Input: nums = [-2,0,2], s = "RLL", d = 3 Output: 8 Explanation: After 1 second, the positions are [-1,-1,1]. Now, the robot at index 0 will move left, and the robot at index 1 will move right. After 2 seconds, the positions are [-2,0,0]. Now, the robot at index 1 will move left, and the robot at index 2 will move right. After 3 seconds, the positions are [-3,-1,1]. The distance between the robot at index 0 and 1 is abs(-3 - (-1)) = 2. The distance between the robot at index 0 and 2 is abs(-3 - 1) = 4. The distance between the robot at index 1 and 2 is abs(-1 - 1) = 2. The sum of the pairs of all distances = 2 + 4 + 2 = 8.
Example 2:
Input: nums = [1,0], s = "RL", d = 2 Output: 5 Explanation: After 1 second, the positions are [2,-1]. After 2 seconds, the positions are [3,-2]. The distance between the two robots is abs(-2 - 3) = 5.
Constraints:
2 <= nums.length <= 105-2 * 109 <= nums[i] <= 2 * 1090 <= d <= 109nums.length == s.length s consists of 'L' and 'R' onlynums[i] will be unique.The key observation in Movement of Robots is that when two robots collide and swap directions, their behavior is equivalent to them simply passing through each other. This insight removes the need to simulate collisions explicitly. Instead, you can compute the final position of each robot after d seconds: robots moving right end at pos + d, while robots moving left end at pos - d.
Once all final positions are calculated, the problem reduces to computing the sum of pairwise distances between robots. Sorting the final positions allows an efficient calculation using a prefix sum technique. For each position i, the contribution of distances with previous robots can be derived using accumulated sums rather than nested loops.
This approach avoids quadratic comparisons and keeps the solution efficient. Sorting dominates the runtime, while prefix sums help compute total distances in linear time after sorting.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sort final positions + Prefix Sum for pairwise distances | O(n log n) | O(1) to O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Observe that if you ignore collisions, the resultant positions of robots after d seconds would be the same.
After d seconds, sort the ending positions and use prefix sum to calculate the distance sum.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, problems like Movement of Robots appear in technical interviews because they test reasoning about simulations, mathematical transformations, and optimization using sorting and prefix sums.
The optimal approach observes that robot collisions can be treated as robots passing through each other. After computing final positions based on direction and distance, sort them and use prefix sums to efficiently calculate the sum of pairwise distances.
Arrays combined with prefix sums are the main tools used in this problem. Sorting the array of final positions enables an efficient linear pass to compute total pairwise distances.
Sorting the final robot positions allows efficient calculation of pairwise distances. Once sorted, the distance contributions can be computed incrementally using prefix sums instead of checking every pair.