Movement of Robots — Editorial

Opening the reading…

Intuitionwhy swapping directions does not change the final set of positions

When two robots collide, swapping their directions has the same effect as letting them pass through each other while keeping their labels attached to their original paths. Before the collision, one robot moves right and the other moves left; after the collision, those two moving paths continue in the same directions. The occupied positions are therefore unchanged by treating robots as ghosts that pass through one another.

That means each starting robot can be moved independently for d seconds. A robot marked R finishes at nums[i] + d, while a robot marked L finishes at nums[i] - d. Once those final positions are known, robot identities no longer matter because the answer asks for distances between positions, not between named robots.

A collision changes robot labels, not the set of positions.

Approach

Create a final-position array with one entry per robot, because each robot can be advanced independently once collisions are replaced by ghost crossings.

For every index i, add d to nums[i] when s[i] is R and subtract d when s[i] is L, because speed 1 for d seconds changes the coordinate by exactly d.

Sort the final positions, because the sum of absolute differences is easiest to count when positions are in non-decreasing order; robot identities are irrelevant after this point.

Scan the sorted positions from left to right while storing the sum of all earlier positions, because every earlier position forms one pair with the current position.

For position pos[i], add i * pos[i] - pref to the answer, where i earlier positions each contribute pos[i] minus their own value; without this aggregation, you would revisit the same pairs in a quadratic loop.

Add pos[i] to pref after using it, so the current position is included only for later elements and no pair is counted twice.

Keep the arithmetic in long long and reduce the accumulated answer modulo 1000000007, because coordinates after movement and intermediate products exceed 32-bit range.

Complexitysorting dominates the scan

MEASURE	BOUND	WHY
Time	O(n log n)	Computing positions and scanning them each take O(n). Sorting the n final positions takes O(n log n), and every pair is represented once through the current position's aggregate contribution rather than being enumerated individually.
Space	O(n) extra	The final-position vector stores n working values, which dominates the O(log n) sorting stack space. The returned value is a single integer, so it contributes no output storage. No input arrangement worsens this bound.

Here n is the number of robots. The distance d and coordinate magnitudes affect integer size, not the asymptotic operation count.

Annotated solutionC++ · sorted positions with a one-pass prefix sum

CPPMove each robot independently, sort the endpoints, and add each endpoint's distance from all earlier endpoints.

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    int sumDistance(vector<int>& nums, string s, int d) {
        const long long MOD = 1000000007LL;
        int n = nums.size();
        vector<long long> pos(n);

        for (int i = 0; i < n; ++i) {
            if (s[i] == 'R') {
                pos[i] = static_cast<long long>(nums[i]) + d;
            } else {
                pos[i] = static_cast<long long>(nums[i]) - d;
            }
        }

        sort(pos.begin(), pos.end());

        long long answer = 0;
        long long pref = 0;
        for (int i = 0; i < n; ++i) {
            long long contribution = static_cast<long long>(i) * pos[i] - pref;
            answer = (answer + contribution) % MOD;
            pref += pos[i];
        }

        return static_cast<int>(answer);
    }
};