DSA SheetMedium
EditorialPractice

PREFIX SUM › PREFIX SUM

Movement of Robots

MediumEditorial · 7 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

Two robots approaching and crossing on a number lineA horizontal number line shows one robot starting on the left and moving right and another starting on the right and moving left. Their paths meet at a central collision point. In the collision interpretation, the robots swap directions and continue outward. In the ghost interpretation, the paths cross and each robot continues straight. Both interpretations end with one robot at the same left final position and one at the same right final position, so the set of positions is identical.A →B ←A reversesB reversesTwo interpretations, the same occupied positionssolid: collide and reversedashed: pass throughcollision: labels exchange directionsstartfinalmeetfinalstartSwap directions at the collision: the labels change, but the two final positions do not.
A collision changes robot labels, not the set of positions.

Approach

  1. Create a final-position array with one entry per robot, because each robot can be advanced independently once collisions are replaced by ghost crossings.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. Add pos[i] to pref after using it, so the current position is included only for later elements and no pair is counted twice.
  7. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(n) extraThe 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);
    }
};

Common mistakestwo lines that change the mathematics

Previous · Find All Good Indices