#2731

Medium

LeetCode Problem Workspace

Movement of Robots

Calculate total distances between robots moving on a number line while accounting for collisions using array plus brainteaser logic.

array brainteaser sorting prefix sum

Problem Statement

You have several robots positioned on an infinite number line, each at a unique coordinate given by the integer array nums. Each robot moves one unit per second, and the direction of movement is determined by a string s, where 'L' moves left and 'R' moves right. If robots collide, they immediately reverse directions, but collisions can be treated carefully to simplify computation.

Given an integer d representing seconds of movement, calculate the total sum of distances between every pair of robots after d seconds. Consider using array transformations, sorting, or prefix sums to handle the positions efficiently without simulating each second individually.

Examples

Example 1

Input: nums = [-2,0,2], s = "RLL", d = 3

Output: 8

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

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.

Solution Approach

Simulate ignoring collisions

Treat each robot as moving in its direction without considering collisions. Calculate its final position after d seconds as nums[i] + d if 'R', or nums[i] - d if 'L'. This transforms the problem into computing distances from final positions only.

Sort positions and apply prefix sums

Sort the adjusted final positions and compute prefix sums to efficiently calculate the sum of distances between all pairs. Each robot contributes to the total sum based on its relative position in the sorted array, which avoids quadratic time simulation.

Sum pairwise distances

Use the prefix sum array to compute total distances for all pairs by iterating through the sorted positions. For each robot, multiply its contribution to pairs on the left and right to accumulate the total, fitting the array plus brainteaser pattern of handling transformations instead of collisions directly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) for sorting plus O(n) for computing pair sums using prefix sums. Space complexity is O(n) for storing adjusted positions and prefix sums.

What Interviewers Usually Probe

Notice how collisions can be conceptually ignored by swapping directions, hinting at array transformation.
Observe that sorting final positions allows efficient computation of all pair distances without per-second simulation.
Prefix sums are likely useful to accumulate distances efficiently, which is a common pattern in array plus brainteaser problems.

Common Pitfalls or Variants

Common pitfalls

Attempting to simulate every second of movement, which is too slow for large d or n.
Forgetting that collisions can be treated as swaps, leading to incorrect final positions.
Ignoring the need to sort positions before computing distances, causing incorrect pair sums.

Follow-up variants

Compute maximum distance instead of sum of distances after d seconds.
Handle robots with variable speeds, requiring different final position calculations.
Introduce obstacles on the number line that robots cannot cross, modifying movement rules.

FAQ

Can I ignore collisions when calculating final positions?

Yes, for this problem treating collisions as swaps lets you compute final positions directly without simulating each second.

Why use prefix sums after sorting positions?

Prefix sums let you efficiently calculate total distances between all pairs without iterating over every combination, reducing complexity.

Does this problem pattern relate to other array plus brainteaser questions?

Yes, the core idea is transforming arrays and using sorting or prefix sums instead of simulating all steps, which is common in array plus brainteaser problems.

What happens if d is very large?

The approach still works efficiently since we compute final positions directly using d, avoiding slow step-by-step simulation.

Are negative coordinates handled differently?

No, the same transformation and distance calculation works for negative numbers since distances use absolute differences.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def sumDistance(self, nums: List[int], s: str, d: int) -> int:
        mod = 10**9 + 7
        for i, c in enumerate(s):
            nums[i] += d if c == "R" else -d
        nums.sort()
        ans = s = 0
        for i, x in enumerate(nums):
            ans += i * x - s
            s += x
        return ans % mod

Continue Practicing

#2681 power of heroes #2602 minimum operations to make all array elements equal #2587 rearrange array to maximize prefix score