Skip to main content
Talentd

Movement of Robots - Solution & Explanation

MediumArrayBrainteaserSortingPrefix Sum17 min readAsked at: Meta, Google, Oyo
Practice this problem

Problem Statement

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 i and j, 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 * 109
  • 0 <= d <= 109
  • nums.length == s.length 
  • s consists of 'L' and 'R' only
  • nums[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.

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n^2) due to pairwise distance calculation.
Space Complexity: O(n) for storing positions.

Try this approach in the editor →

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.

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for the positions array.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulation Based Approach

Time Complexity: O(n^2) due to pairwise distance calculation.
Space Complexity: O(n) for storing positions.

Optimized Pairwise Calculation

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for the positions array.

Quick thinking + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulation Based ApproachO(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

Video Solution

Leetcode BiWeekly contest 106 - Medium - Movement of Robots • Prakhar Agrawal • 1,672 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Movement of Robots with our built-in code editor and test cases.

Practice on FleetCode
Previous

Last Moment Before All Ants Fall Out of a Plank