nlog(n) time, 0 space, python solution
Intuition\n Describe your first thoughts on how to solve this problem. \nWe don\'t have to change the direction of the robots, the colliding robots are intercha
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe don\'t have to change the direction of the robots, the colliding robots are interchangeable in position.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTo calculate the distance, we cannot use bruteforce approach, which causes O(n^2) time and would exceed time limit. We can try to use precalculated distance of previous robots to reduce duplicate calculation. \n\n**Method 1: back-to-front calculation & extra space**\nIt requires a few mathematical derivation.\nConsider a0, a1, a2, a3, which is the final positions of robots in ascending order.\n\nassume we have calculate s1, which is the distance from a1 to all the following robots, i.e. a2 and a3. How can we make use of s1 to calculate s0? Note that we calculate backwards.\nYou would find out we just need to add the distance from a0 to a1 for each following robots. For example, consider a0 to a2, it\'s a0 to a1 and a1 to a2; for a0 to a3, it\'s a0 to a1 and a1 to a3. \n\nTherefore, s0 = s1 + (number of following robots) * (distance to previou robot)\ns0 = s1 + 3 * (a1 - a0)\n=> this is how I derive the formular in the code \nand we can just sum them up in the result\n\n**Method 2: front-to-back & 0 space**\nit doesn\'t necessarily have to use extra space though\n\nstill consider a0, a1, a2, a3\nwe want to calculate s3, s3 = a3-a2 + a3-a1 + a3-a0 = 3 * a3 - (a0+a1+a2). See? we found the pattern\n=> si = i * ai - ( a_0+a_1+...+a_i-1 )\n\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nnlogn\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nn\n\n# Code\n```python3 []\nclass Solution:\n    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n        n = len(nums)\n        for i, num in enumerate(nums):\n            if s[i] == \'R\':\n                nums[i] += d\n            else:\n                nums[i] -= d\n        nums.sort()\n\n        <!-- method 1 -->\n        <!-- s = [0] * n\n        s[-2] = nums[-1] - nums[-2]\n        for i in range(n-3, -1, -1):\n            s[i] = s[i+1] + (nums[i+1] - nums[i]) * (n - i - 1)\n        return sum(s) % (10 ** 9 + 7) -->\n\n        <!-- method 2 -->\n        s = 0\n        res = 0\n        for i,num in enumerate(nums):\n            res += (i * num - s)\n            s += num\n        return res % (10 ** 9 + 7)\n                \n                \n```
['Python3']