Easy Beginner Friendly with Explanations Pass Through + Prefix Sum | C++ Python
Intuition\n Describe your first thoughts on how to solve this problem. \nIf two objects collide then it appears that they have pass through\n> In short if the i
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf two objects collide then it appears that they have pass through\n> In short if the ith robot is moving left then after time d it\'s position would be nums[i] - d and if it is moving right then it\'s position would be nums[i] + d\n\n**Example:** let 1 be moving right and 2 be moving left.\n\n![image.png](https://assets.leetcode.com/users/images/fb9bd148-4669-4b6c-a3f0-376fcaa43fa6_1686412037.2541788.png)\n\nSimilar intuition: [https://codingcompetitions.withgoogle.com/kickstart/round/00000000008cb4d1/0000000000b209bc#analysis](https://codingcompetitions.withgoogle.com/kickstart/round/00000000008cb4d1/0000000000b209bc#analysis)\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. We change the final positions using pass through property.\n    ``` C++\n    for(ll i = 0; i < n; i ++){\n        if(s[i] == \'L\'){\n            nums[i] -= d;\n        }else{\n            nums[i] += d;\n        }\n    }\n    ```\n2. To calculate absolute diff between every pair in O(N). We can sort the distance array.\n    - The index `j` contribution would be sum of `abs(nums[j] - nums[0]) + abs(nums[j] - nums[1]) + abs(nums[j] - nums[2]) + ...... + abs(nums[j] - nums[j - 1])`.\n    - But we know `for (i<j)` `nums[i] < nums[j](Sorted array)`\n    - So we can open the `abs()` as `nums[j] - nums[i]` \n    - The index `j` contribution would be sum of `nums[j] - nums[0] + nums[j] - nums[1] + nums[j] - nums[2] + ..... + nums[j] - nums[j - 1]`.\n    - If we notice then this converts into `j * nums[j] - sum(nums[i] i belongs from 0 to j - 1)` \n    - Sum of [0, j- 1] can be calculated in `O(1)` using prefix sum.\n        ``` C++ \n        for(ll i = 1; i < n; i++){\n            ll temp = (MOD + i * nums[i] - pre[i - 1])%MOD;\n            ans = ((ans%MOD) + (temp%MOD))%MOD;\n        }\n        ```\n\n# Complexity\n- Time complexity: `O(N * Log(N))`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(N)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` Python3 []\nclass Solution:\n    def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n        n, m = len(nums), int(1e9 + 7)\n        # Ignore the Collisions\n        for i in range(n):\n            if s[i] == \'L\':\n                nums[i] -= d\n            else: \n                nums[i] += d\n        \n        # Sort according to position to calculate abs sum of each pair in O(N)\n        nums.sort()\n\n        pre = nums.copy()\n        # Calculate Prefix Sum\n        for i in range(1, n):\n            pre[i] += pre[i - 1]\n            pre[i] %= m\n\n        ans = 0\n        for i in range(1, n):\n            # each jth index contributes to j * nums[j] - pre[j - 1]\n            ans += i * nums[i] - pre[i - 1]\n            ans %= m\n        return ans\n```\n``` C++ []\ntypedef long long int ll;\nconst ll MOD = 1e9 + 7;\nclass Solution {\npublic:\n    int sumDistance(vector<int>& nums, string s, int d) {\n        //Ignore the collisions!\n        for(ll i = 0; i < s.length(); i ++)\n            if(s[i] == \'L\')nums[i] -= d;\n            else nums[i] += d;\n        // Sort according to position to calculate abs sum of each pair in O(N)\n        sort(nums.begin(), nums.end());\n        \n        //Calculate Prefix Sum\n        vector<ll> pre(nums.begin(), nums.end());\n        for(ll i = 1; i < nums.size(); i++){\n            pre[i] += pre[i - 1];\n            pre[i] %= MOD;\n        }\n\n        ll ans = 0;\n        for(ll i = 1; i < nums.size(); i++){\n            // each jth index contributes to j * nums[j] - pre[j - 1]\n            ans += i * nums[i] - pre[i - 1];\n            ans %= MOD;\n        }\n        return ans;\n    }\n};\n```
['Array', 'String', 'Greedy', 'C++', 'Python3']