[C++] Ignore Collisions and Get Cumulative Sum, ~100% (90ms), ~45% Space (45.2MB)
So, for this problem the more crucial part was to figure out we can ignore each collision: similarly to a perfectly elastic linear system with two identical obj
So, for this problem the more crucial part was to figure out we can ignore each collision: similarly to a perfectly elastic linear system with two identical objects colliding with each other, each object will replace the other one, moving from the the collision spot in the opposite direction; this is basically a sophisticate version of [lasr moment before all ants fall out of a plank](https://leetcode.com/problems/last-moment-before-all-ants-fall-out-of-a-plank/) ([cracked here](https://leetcode.com/problems/last-moment-before-all-ants-fall-out-of-a-plank/solutions/3657689/c-just-ignore-collisions-and-get-the-maximum-distance-from-border-100-space-22-7mb/)).\n\nOnce we got all that and we had or subtract `d` to each element depending from its direction, we can store all the values of the final positions for the last part of the problem - computing the overall distances.\n\nSome people used a prefix array, but we can do better using only a running sum.\n\nTo clarify our approach, let\'s assume we have as final positions (already sorted) `{1, 5, 7, 10}`, we can proceed taking each value and thinking of it like the product of its index minus the sum of the previous elements:\n\n```cpp\n    1   5   7  10\n// sum of distances:\n( 5 - 1) +                      // ==  5 * 1 - 1\n( 7 - 5) + ( 7 - 1) +           // ==  7 * 2 - (5 + 1)\n(10 - 7) + (10 - 5) + (10 - 1)  // == 10 * 3 - (7 + 5 + 1)\n```\n\nNow, to turn all of this into code, let\'s start by declaring a few support variables as usual:\n* `len` is going to store the length of our initial inputs (both the vector and the string, guaranteed to have the same size);\n* `res` is going to be our usual accumulator variable, initialised to `0`;\n* `tot` will be our prefix sum, initially set to `0`;\n* `n` will be the ongoing value as we parse `ns` in the second half of the problem;\n* `ns` is going to store all the values of the final positions of each element originally in `nums`.\n\nNext we are going to start populating `ns`; going with `i` through all the elements in `nums`, we will:\n* store `nums[i]` in `n`;\n* if this robot was going left (ie: `s[i] == \'L\'`), we will subtract `d` from `n` (since it is moving backwards on the x axis);\n* otherwise, we will add `d` to `n`;\n* we can then write `n` in `ns[i]`.\n\nNow, since we need our elements in order, we will `sort` `ns`, then, for going with `i` through each position in it, we will:\n* store `ns[i]` in `n`;\n* increase `res` by the product of `n` and `i` minus the sum of all the previous elements `tot`, as explained above;\n* check if `res` is `>= modVal`, we will recompute it as `% modVal`;\n* increase `tot` by `n`.\n\nOnce done, we can `return` `res` :)\n\n# Complexity\n- Time complexity: $$O(n log(n))$$\n- Space complexity: $$O(n)$$\n\n# Code\n```cpp\nconst long long modVal = 1000000007;\n\nclass Solution {\npublic:\n    int sumDistance(vector<int> &nums, string s, int d) {\n        // support variables\n        int len = nums.size();\n        long long res = 0, tot = 0, n;\n        vector<long long> ns(len);\n        // populating ns\n        for (int i = 0; i < len; i++) {\n            n = nums[i];\n            if (s[i] == \'L\') n -= d;\n            else n += d;\n            ns[i] = n;\n        }\n        // parsing ns\n        sort(begin(ns), end(ns));\n        for (int i = 0; i < len; i++) {\n            n = ns[i];\n            // updating res and tot\n            res += i * n - tot;\n            if (res >= modVal) res %= modVal;\n            tot += n;\n        }\n        return res;\n    }\n};\n```\n\nAlternative version replacing the relatively expensive `%` with a subtraction; it works as fast, but apparently using a bit less memory on average (or it might be just more luck with the test cases):\n\n```cpp\nconst long long modVal = 1000000007;\n\nclass Solution {\npublic:\n    int sumDistance(vector<int> &nums, string s, int d) {\n        // support variables\n        int len = nums.size();\n        long long res = 0, tot = 0, n;\n        vector<long long> ns(len);\n        // populating ns\n        for (int i = 0; i < len; i++) {\n            n = nums[i];\n            if (s[i] == \'L\') n -= d;\n            else n += d;\n            ns[i] = n;\n        }\n        // parsing ns\n        sort(begin(ns), end(ns));\n        for (int i = 0; i < len; i++) {\n            n = ns[i];\n            // updating res and tot\n            res += i * n - tot;\n            while (res >= modVal) res -= modVal;\n            tot += n;\n        }\n        return res;\n    }\n};\n```\n\n# Brag\n![image.png](https://assets.leetcode.com/users/images/880b92fa-dc41-4dc3-9326-a4e0bcd4461c_1687127641.552774.png)\n
['Array', 'Brainteaser', 'Sorting', 'Prefix Sum', 'C++']