Movement of Robots solution and explanation
Google
8 more videos on this problem
Leetcode BiWeekly contest 106 - Medium - Movement of RobotsPrakhar Agrawal · 11:52 · 1K views
2731. Movement of Robots | LEETCODE BIWEEKLY CONTEST 106 | PREFIX SUMcode Explainer · 10:28 · 1K views
2731. Movement of Robots | Biweekly Contest 106codingMohan · 16:07 · 1K views
Movement of Robots | Leetcode 2731 | BiWeekly 106Tech Courses · 15:45 · 793 views
2731. Movement of Robots (Leetcode Medium)Programming Live with Larry · 13:08 · 759 views
[Eng] Leetcode | Biweekly Contest 106 | 2731 Movement of RobotsCyCode · 10:02 · 230 views
Leetcode 2731. Movement of RobotsElite Code · 25:13 · 124 views
2731. Movement of Robots || LeetcodeCanary Logic · 12:26 · 118 views
2731. Movement of RobotsHarmeet Singh · 8:26 · 33 views
The problem
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:
- For two robots at the index
iandj, pair(i,j)and pair(j,i)are considered the same pair. - When robots collide, they instantly change their directions without wasting any time.
- Collision happens when two robots share the same place in a moment.
- For example, if a robot is positioned in 0 going to the right and another is positioned in 2 going to the left, the next second they'll be both in 1 and they will change direction and the next second the first one will be in 0, heading left, and another will be in 2, heading right.
- For example, if a robot is positioned in 0 going to the right and another is positioned in 1 going to the left, the next second the first one will be in 0, heading left, and another will be in 1, heading right.
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.lengthsconsists of 'L' and 'R' onlynums[i]will be unique.
Approach overview
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 1: Simulation Based Approach
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.
def sum_of_distances(nums, s, d):
MOD = 10**9 + 7
n = len(nums)
positions = [nums[i] + d if s[i] == 'R' else nums[i] - d for i in range(n)]
positions.sort()
total_distance = 0
for i in range(n):
for j in range(i + 1, n):
total_distance = (total_distance + abs(positions[j] - positions[i])) % MOD
return total_distance
# Example usage:
result = sum_of_distances([-2, 0, 2], 'RLL', 3)
print(result)import java.util.Arrays;
public class RobotMovement {
public static int sumOfDistances(int[] nums, String s, int d) {
final int MOD = 1000000007;
int n = nums.length;
int[] positions = new int[n];
for (int i = 0; i < n; i++) {
positions[i] = s.charAt(i) == 'R' ? nums[i] + d : nums[i] - d;
}
Arrays.sort(positions);
long totalDistance = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
totalDistance = (totalDistance + Math.abs(positions[j] - positions[i])) % MOD;
}
}
return (int) totalDistance;
}
// Example usage:
// public static void main(String[] args) {
// System.out.println(sumOfDistances(new int[]{-2, 0, 2}, "RLL", 3));
// }
}#include <bits/stdc++.h>
using namespace std;
int sumOfDistances(vector<int> nums, string s, int d) {
const int MOD = 1e9 + 7;
int n = nums.size();
vector<int> positions(n);
for (int i = 0; i < n; ++i) {
positions[i] = s[i] == 'R' ? nums[i] + d : nums[i] - d;
}
sort(positions.begin(), positions.end());
long long total_distance = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
total_distance = (total_distance + abs(positions[j] - positions[i])) % MOD;
}
}
return total_distance;
}
// Example usage:
// cout << sumOfDistances({-2, 0, 2}, "RLL", 3) << endl;function sumOfDistances(nums, s, d) {
const MOD = 1000000007;
const positions = nums.map((num, idx) => s[idx] === 'R' ? num + d : num - d);
positions.sort((a, b) => a - b);
let totalDistance = 0;
for (let i = 0; i < positions.length; i++) {
for (let j = i + 1; j < positions.length; j++) {
totalDistance = (totalDistance + Math.abs(positions[j] - positions[i])) % MOD;
}
}
return totalDistance;
}
// Example usage:
// console.log(sumOfDistances([-2, 0, 2], 'RLL', 3));using System;
public class RobotMovement {
public static int SumOfDistances(int[] nums, string s, int d) {
int MOD = 1000000007;
int n = nums.Length;
int[] positions = new int[n];
for (int i = 0; i < n; i++) {
positions[i] = s[i] == 'R' ? nums[i] + d : nums[i] - d;
}
Array.Sort(positions);
long totalDistance = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
totalDistance = (totalDistance + Math.Abs(positions[j] - positions[i])) % MOD;
}
}
return (int)totalDistance;
}
// Example usage:
// Console.WriteLine(SumOfDistances(new int[]{-2, 0, 2}, "RLL", 3));
}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.
Time Complexity: O(n^2) due to pairwise distance calculation.
Space Complexity: O(n) for storing positions.
Approach 2: Optimized Pairwise Calculation
Instead of directly computing pairwise distances, optimize by leveraging mathematical properties of differences and precomputed sums. This will avoid the O(n^2) complexity.
def optimized_sum_of_distances(nums, s, d):
MOD = 10**9 + 7
n = len(nums)
positions = [nums[i] + d if s[i] == 'R' else nums[i] - d for i in range(n)]
positions.sort()
total_sum = 0
prefix_sum = 0
for i in range(n):
total_sum = (total_sum + i * positions[i] - prefix_sum) % MOD
prefix_sum += positions[i]
return total_sum
# Example usage:
result = optimized_sum_of_distances([-2, 0, 2], 'RLL', 3)
print(result)import java.util.Arrays;
public class RobotMovementOptimized {
public static int optimizedSumOfDistances(int[] nums, String s, int d) {
final int MOD = 1000000007;
int n = nums.length;
int[] positions = new int[n];
for (int i = 0; i < n; i++) {
positions[i] = s.charAt(i) == 'R' ? nums[i] + d : nums[i] - d;
}
Arrays.sort(positions);
long totalSum = 0, prefixSum = 0;
for (int i = 0; i < n; i++) {
totalSum = (totalSum + i * positions[i] - prefixSum) % MOD;
prefixSum += positions[i];
}
return (int) totalSum;
}
// Example usage:
// public static void main(String[] args) {
// System.out.println(optimizedSumOfDistances(new int[]{-2, 0, 2}, "RLL", 3));
// }
}#include <bits/stdc++.h>
using namespace std;
int optimizedSumOfDistances(vector<int> nums, string s, int d) {
const int MOD = 1e9 + 7;
int n = nums.size();
vector<int> positions(n);
for (int i = 0; i < n; ++i) {
positions[i] = s[i] == 'R' ? nums[i] + d : nums[i] - d;
}
sort(positions.begin(), positions.end());
long long total_sum = 0;
long long prefix_sum = 0;
for (int i = 0; i < n; ++i) {
total_sum = (total_sum + i * positions[i] - prefix_sum) % MOD;
prefix_sum += positions[i];
}
return total_sum;
}
// Example usage:
// cout << optimizedSumOfDistances({-2, 0, 2}, "RLL", 3) << endl;function optimizedSumOfDistances(nums, s, d) {
const MOD = 1000000007;
const positions = nums.map((num, idx) => s[idx] === 'R' ? num + d : num - d);
positions.sort((a, b) => a - b);
let totalSum = 0;
let prefixSum = 0;
for (let i = 0; i < positions.length; i++) {
totalSum = (totalSum + i * positions[i] - prefixSum) % MOD;
prefixSum += positions[i];
}
return totalSum;
}
// Example usage:
// console.log(optimizedSumOfDistances([-2, 0, 2], 'RLL', 3));using System;
public class RobotMovementOptimized {
public static int OptimizedSumOfDistances(int[] nums, string s, int d) {
int MOD = 1000000007;
int n = nums.Length;
int[] positions = new int[n];
for (int i = 0; i < n; i++) {
positions[i] = s[i] == 'R' ? nums[i] + d : nums[i] - d;
}
Array.Sort(positions);
long totalSum = 0;
long prefixSum = 0;
for (int i = 0; i < n; i++) {
totalSum = (totalSum + i * positions[i] - prefixSum) % MOD;
prefixSum += positions[i];
}
return (int)totalSum;
}
// Example usage:
// Console.WriteLine(OptimizedSumOfDistances(new int[]{-2, 0, 2}, "RLL", 3));
}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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for the positions array.
Approach 3: Quick thinking + Sorting
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.
function sumDistance(nums: number[], s: string, d: number): number {
const n = nums.length;
for (let i = 0; i < n; ++i) {
nums[i] += s[i] === 'L' ? -d : d;
}
nums.sort((a, b) => a - b);
let ans = 0;
let sum = 0;
const mod = 1e9 + 7;
for (let i = 0; i < n; ++i) {
ans = (ans + i * nums[i] - sum) % mod;
sum += nums[i];
}
return ans;
}func sumDistance(nums []int, s string, d int) (ans int) {
for i, c := range s {
if c == 'R' {
nums[i] += d
} else {
nums[i] -= d
}
}
sort.Ints(nums)
sum := 0
const mod int = 1e9 + 7
for i, x := range nums {
ans = (ans + i*x - sum) % mod
sum += x
}
return
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Movement of Robots easy or hard?
Movement of Robots is rated Medium difficulty. The tricky part is realizing that robot collisions can be ignored because swapping directions produces the same final positions as passing through each other. Once that insight is applied, the remaining work involves sorting and prefix-sum distance calculation.
Movement of Robots Python/Java solution
Python and Java implementations typically compute final robot coordinates first, store them in an array or list, sort the values, and then iterate while maintaining a prefix sum. Each step adds pos[i] * i - prefixSum to the total distance while applying modulo 1e9+7.
How to solve Movement of Robots in O(n)?
A strictly O(n) solution is not practical because the robot positions must be ordered to compute pairwise distances efficiently. The closest optimal complexity is O(n log n), achieved by sorting final positions and then using prefix sums to accumulate distances in linear time.
What is the best approach for Movement of Robots?
The best approach computes each robot’s final position after d seconds, sorts the resulting coordinates, and then calculates pairwise distances using a prefix sum formula. Sorting ensures robots are processed in order, allowing each position to contribute distances with previously seen robots efficiently. This approach runs in O(n log n) time and O(n) space.
Is Movement of Robots asked at Google/Amazon/Meta?
Movement of Robots represents a common interview pattern involving sorting and prefix-sum based pairwise distance calculations. Variations of this pattern appear in interviews at companies like Amazon, Google, and Meta because it tests mathematical insight and efficient aggregation techniques.
What data structure is used in Movement of Robots?
The main structure used is an array to store robot positions. After adjusting positions based on direction, the array is sorted and processed using a running prefix sum to compute pairwise distances efficiently.
What is the time complexity of Movement of Robots?
The optimal solution runs in O(n log n) time due to sorting the final robot positions. After sorting, the pairwise distance calculation uses a prefix sum sweep that takes O(n). A naive simulation that checks every pair of robots would take O(n²) time.