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.Problem Overview: You are given robot positions on a number line and a string describing their movement direction (left or right). After d seconds, each robot moves d units in its direction. The task is to compute the sum of pairwise distances between all robots after movement.
Approach 1: Simulation Based Approach (O(n²) time, O(n) space)
The most direct idea is to simulate the final position of every robot. For each index i, move the robot left or right by d depending on the direction character. This produces a new array of final coordinates. Once the final positions are known, compute the distance between every pair of robots using a nested loop and accumulate the absolute difference.
This approach is straightforward and mirrors the problem statement. However, calculating distances for every pair requires O(n²) comparisons. It works for small inputs and is useful for verifying correctness during development, but it becomes too slow for large arrays.
Approach 2: Optimized Pairwise Calculation (Sorting + Prefix Sum) (O(n log n) time, O(n) space)
The key observation is that robot collisions do not matter for the final distance calculation. When two robots collide and swap directions, the result is equivalent to them passing through each other. Because of this, you can treat each robot independently and simply compute its final position after d seconds.
First compute the final coordinate for each robot. If the direction is 'R', the new position becomes nums[i] + d. If the direction is 'L', it becomes nums[i] - d. After calculating all positions, sort the array. Sorting enables efficient pairwise distance computation because distances between ordered elements follow a predictable pattern.
Iterate through the sorted array while maintaining a running prefix sum. For each index i, the contribution of pos[i] to the total distance with previous elements is pos[i] * i - prefixSum. Add this value to the result and update the prefix sum. This eliminates the need for nested loops and reduces the pairwise computation to linear time after sorting.
This technique relies on patterns commonly used in sorting problems and prefix sum accumulation. The positions themselves are stored in an array, and the sorted order ensures that each pair distance is counted exactly once.
Recommended for interviews: The optimized sorting + prefix sum approach is what interviewers expect. The simulation method demonstrates understanding of the problem mechanics, but the optimized solution shows you recognize the collision equivalence insight and can compute pairwise distances efficiently.
In this approach, we simulate the movement of each robot over time, while handling collisions. We'll update positions step by step, checking for collisions and reversing directions when needed. Finally, we'll calculate the sum of distances between each pair of robots after d seconds.
Calculate the new position of each robot after d seconds by adding or subtracting d from their initial positions based on the direction. Sort the positions and calculate the sum of the pairwise distances.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n^2) due to pairwise distance calculation.
Space Complexity: O(n) for storing positions.
Instead of directly computing pairwise distances, optimize by leveraging mathematical properties of differences and precomputed sums. This will avoid the O(n^2) complexity.
Sort the positions and use a prefix sum to calculate the total distance efficiently: for each position, the distance contribution is based on how many times it gets added or subtracted in subsequent pairs.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for the positions array.
After two robots collide, they will immediately change direction, which is equivalent to the two robots continuing to move in their original direction. Therefore, we traverse the array nums, and according to the instructions in the string s, we add or subtract d from the position of each robot, and then sort the array nums.
Next, we enumerate the position of each robot from small to large, and calculate the sum of the distances between the current robot and all robots in front, which is the answer.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of robots.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Simulation Based Approach | Time Complexity: O(n^2) due to pairwise distance calculation. |
| Optimized Pairwise Calculation | Time Complexity: O(n log n) due to sorting. |
| Quick thinking + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulation Based Approach | O(n²) | O(n) | Simple implementation or verifying correctness for small inputs |
| Optimized Pairwise Calculation (Sorting + Prefix Sum) | O(n log n) | O(n) | Best general solution for large inputs; efficient pair distance computation |
Leetcode BiWeekly contest 106 - Medium - Movement of Robots • Prakhar Agrawal • 1,666 views views
Watch 9 more video solutions →Practice Movement of Robots with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor