# Movement of Robots
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/movement-of-robots)
Canonical: https://scaleengineer.com/dsa/problems/movement-of-robots
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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 `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.

# Approaches
## Brute Force on Final Positions
A crucial observation simplifies this problem: when two robots collide, they are described as reversing their directions. From the perspective of the set of positions on the number line, this is indistinguishable from the robots simply passing through each other. The identities of the robots at specific positions might change, but since we only care about the distances between positions, we can ignore the collisions entirely. This allows us to calculate the final position of each robot by simply applying its initial movement direction for `d` seconds.

This approach first calculates the final destination of every robot. Then, it iterates through every possible pair of robots, calculates the distance between them, and adds it to a running total. This is a direct translation of the problem statement after applying the 'pass-through' insight.
**Time:** O(n^2). Calculating the final positions takes O(n) time. The nested loops to sum the pairwise distances dominate the complexity, taking O(n^2) time. · **Space:** O(n), where `n` is the number of robots. This space is used to store the final positions of the robots.
**Pros:** It's conceptually simple and easy to implement once the 'pass-through' nature of collisions is understood.; It correctly solves the problem for small input sizes.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints where `n` can be up to 10^5, which will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
First, we determine the final position of each robot. For a robot starting at `nums[i]` with direction `s[i]`, its final position after `d` seconds will be `nums[i] + d` if moving right ('R') or `nums[i] - d` if moving left ('L'). We store these final positions in a new array, for instance, `finalPositions`.

Once we have the array of all final positions, the problem is to find the sum of distances between all pairs. A brute-force method involves using two nested loops. The outer loop selects a robot `i`, and the inner loop selects another robot `j` (where `j > i` to avoid duplicate pairs and self-comparison). For each pair, we compute the absolute distance `abs(finalPositions[i] - finalPositions[j])`. This distance is added to a cumulative sum. Since the total sum can be very large, we apply the modulo operator (`% 10^9 + 7`) at each addition to keep the sum within manageable bounds.

```java
import java.lang.Math;

class Solution {
    public int sumDistance(int[] nums, String s, int d) {
        int n = nums.length;
        long[] finalPositions = new long[n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'R') {
                finalPositions[i] = (long) nums[i] + d;
            } else {
                finalPositions[i] = (long) nums[i] - d;
            }
        }

        long totalDistance = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long distance = Math.abs(finalPositions[i] - finalPositions[j]);
                totalDistance = (totalDistance + distance) % MOD;
            }
        }

        return (int) totalDistance;
    }
}
```
### Algorithm
*   **Insight:** Realize that when two robots collide and reverse directions, it's equivalent to them passing through each other. The set of positions occupied by robots remains the same. This avoids a complex, step-by-step simulation.
*   **Calculate Final Positions:** Create an array `finalPositions` of size `n`. Iterate from `i = 0` to `n-1`. If `s[i]` is 'R', the final position is `nums[i] + d`. If `s[i]` is 'L', it's `nums[i] - d`. Store these in `finalPositions`.
*   **Sum Pairwise Distances:** Initialize a variable `totalDistance` to 0. Use a nested loop to iterate through all unique pairs of indices `(i, j)` where `i < j`.
*   **Calculation:** For each pair, compute the absolute difference `abs(finalPositions[i] - finalPositions[j])`.
*   **Accumulate with Modulo:** Add this distance to `totalDistance`, taking the modulo `10^9 + 7` at each step to prevent overflow. `totalDistance = (totalDistance + distance) % MOD`.
*   **Return:** After iterating through all pairs, return `totalDistance`.

## Optimal Approach using Sorting and Prefix Sum
This approach improves upon the brute-force method by optimizing the summation of pairwise distances. While we still begin by calculating the final positions using the 'pass-through' insight, we avoid the O(n^2) nested loops. The key idea is to sort the final positions first. Once the positions are sorted, the sum of absolute differences `Sum |p_i - p_j|` can be calculated much more efficiently.
**Time:** O(n log n). Calculating final positions is O(n), sorting is O(n log n), and the final summation pass is O(n). The sorting step is the bottleneck. · **Space:** O(n) for storing the final positions. The space complexity of sorting in Java for primitives is typically O(log n) for the call stack, but we count the O(n) storage for the positions array as the dominant factor.
**Pros:** Highly efficient, with a time complexity of O(n log n), which is fast enough for the given constraints.; It is the optimal way to solve the problem.
**Cons:** The implementation requires careful handling of modulo arithmetic, especially with potentially negative positions, to avoid subtle bugs.; It is slightly more complex to conceptualize than the straightforward brute-force approach.
### Explanation
After calculating the final positions and storing them in an array, we sort this array. Let the sorted positions be `p'_0, p'_1, ..., p'_{n-1}`. The total sum of distances is `Sum_{0 <= j < i < n} (p'_i - p'_j)`.

We can compute this sum in a single pass (O(n)) over the sorted array. We iterate from `i = 0` to `n-1`, and at each step `i`, we add the sum of distances between `p'_i` and all preceding elements (`p'_0` to `p'_{i-1}`) to our total. This sum is `(p'_i - p'_0) + (p'_i - p'_1) + ... + (p'_i - p'_{i-1})`. This can be regrouped as `i * p'_i - (p'_0 + p'_1 + ... + p'_{i-1})`.

We can maintain a `prefixSum` variable that stores the sum of elements encountered so far. In each iteration `i`, we calculate `i * p'_i - prefixSum`, add this value to our `totalDistance`, and then update `prefixSum` by adding `p'_i`. To handle the large numbers and potential negative positions, all calculations are performed with `long` data types and modulo `10^9 + 7`.

```java
import java.util.Arrays;

class Solution {
    public int sumDistance(int[] nums, String s, int d) {
        int n = nums.length;
        long[] finalPositions = new long[n];
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'R') {
                finalPositions[i] = (long) nums[i] + d;
            } else {
                finalPositions[i] = (long) nums[i] - d;
            }
        }

        Arrays.sort(finalPositions);

        long totalDistance = 0;
        long prefixSum = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            long currentPos = finalPositions[i];
            
            // Sum of distances from currentPos to all previous elements:
            // (i * currentPos) - prefixSum
            // We must perform modulo arithmetic carefully.
            long distanceToPrevious = (i * currentPos) - prefixSum;

            // Apply modulo at each step to prevent overflow
            totalDistance = (totalDistance + distanceToPrevious) % MOD;
            prefixSum = (prefixSum + currentPos);
            // prefixSum can also become very large, so it should also be taken modulo.
            // A safer way is to apply modulo at each step of the calculation.
        }

        // The above loop is conceptually correct but can overflow `long` if n is large.
        // A safer implementation with proper modulo arithmetic:
        totalDistance = 0;
        prefixSum = 0;
        for (int i = 0; i < n; i++) {
            long currentPos = finalPositions[i];
            long currentPosMod = (currentPos % MOD + MOD) % MOD;

            long term = ((long)i * currentPosMod) % MOD;
            long distanceSum = (term - prefixSum + MOD) % MOD;

            totalDistance = (totalDistance + distanceSum) % MOD;
            prefixSum = (prefixSum + currentPosMod) % MOD;
        }

        return (int) totalDistance;
    }
}
```
### Algorithm
*   **Calculate Final Positions:** Same as the brute-force approach, compute the final position of each robot as if it passed through others and store them in a `long` array, `finalPositions`. This takes O(n) time.
*   **Sort Positions:** Sort the `finalPositions` array in non-decreasing order. This is the key step that enables a more efficient summation and takes O(n log n) time.
*   **Sum with Prefix Sum:** Initialize `totalDistance = 0` and `prefixSum = 0`. Iterate through the sorted `finalPositions` from `i = 0` to `n-1`.
*   **Efficient Calculation:** In each iteration `i`, the sum of distances from the current position `p_i` to all previous positions `p_0, ..., p_{i-1}` is `(p_i - p_0) + ... + (p_i - p_{i-1})`, which simplifies to `i * p_i - (p_0 + ... + p_{i-1})`. The second term is the `prefixSum` of positions seen so far.
*   **Update Sums:** Calculate `distanceToPrevious = (i * p_i) - prefixSum`. Add this to `totalDistance`. Then, update `prefixSum` by adding `p_i` to it.
*   **Modulo Arithmetic:** All calculations involving `totalDistance` and `prefixSum` must be done modulo `10^9 + 7` to prevent overflow and handle negative intermediate results correctly.
*   **Return:** The final `totalDistance` is the answer.

# Solutions
### Java

```java
class Solution {
public
  int sumDistance(int[] nums, String s, int d) {
    int n = nums.length;
    long[] arr = new long[n];
    for (int i = 0; i < n; ++i) {
      arr[i] = (long)nums[i] + (s.charAt(i) == 'L' ? -d : d);
    }
    Arrays.sort(arr);
    long ans = 0, sum = 0;
    final int mod = (int)1 e9 + 7;
    for (int i = 0; i < n; ++i) {
      ans = (ans + i * arr[i] - sum) % mod;
      sum += arr[i];
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int sumDistance(vector<int> &nums, string s, int d) {
    int n = nums.size();
    vector<long long> arr(n);
    for (int i = 0; i < n; ++i) {
      arr[i] = 1LL * nums[i] + (s[i] == 'L' ? -d : d);
    }
    sort(arr.begin(), arr.end());
    long long ans = 0;
    long long sum = 0;
    const int mod = 1e9 + 7;
    for (int i = 0; i < n; ++i) {
      ans = (ans + i * arr[i] - sum) % mod;
      sum += arr[i];
    }
    return ans;
  }
};

```

### Python

```python
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

```