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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5
6

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 <= 10^5
  • -2 * 109 <= nums[i] <= 2 * 109
  • 0 <= d <= 10^9
  • nums.length == s.length
  • s consists of ‘L’ and ‘R’ only
  • nums[i] will be unique.

Solution

Method 1 -

Intuition

After d seconds, each robot’s position is nums[i] + d if s[i] == ‘R’, else nums[i] - d. Collisions do not affect the final positions, so we can ignore them. The sum of all pairwise distances can be computed efficiently by sorting the final positions and using prefix sums.

Approach

Compute the final positions for all robots. Sort them. For each position, the total distance to all previous positions is i * pos[i] - sum of previous positions. Sum this for all i to get the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int sumDistance(vector<int>& nums, string s, int d) {
    const int MOD = 1e9+7;
    int n = nums.size();
    vector<long long> pos(n);
    for (int i = 0; i < n; ++i)
        pos[i] = nums[i] + (s[i] == 'R' ? d : -d);
    sort(pos.begin(), pos.end());
    long long res = 0, prefix = 0;
    for (int i = 0; i < n; ++i) {
        res = (res + pos[i]*i - prefix) % MOD;
        prefix += pos[i];
    }
    return (res + MOD) % MOD;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public int sumDistance(int[] nums, String s, int d) {
    int MOD = 1_000_000_007, n = nums.length;
    long[] pos = new long[n];
    for (int i = 0; i < n; i++)
        pos[i] = nums[i] + (s.charAt(i) == 'R' ? d : -d);
    Arrays.sort(pos);
    long res = 0, prefix = 0;
    for (int i = 0; i < n; i++) {
        res = (res + pos[i]*i - prefix) % MOD;
        prefix += pos[i];
    }
    return (int)((res + MOD) % MOD);
}
1
2
3
4
5
6
7
8
9

def sumDistance(nums, s, d):
    MOD = 10**9+7
    pos = [x + d if dir == 'R' else x - d for x, dir in zip(nums, s)]
    pos.sort()
    res, prefix = 0, 0
    for i, x in enumerate(pos):
        res = (res + x*i - prefix) % MOD
        prefix += x
    return (res + MOD) % MOD

Complexity

  • ⏰ Time complexity: O(n log n) for sorting and prefix sum.
  • 🧺 Space complexity: O(n) for positions.