Watch 10 video solutions for Movement of Robots, a medium level problem involving Array, Brainteaser, Sorting. This walkthrough by Prakhar Agrawal has 1,666 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |