Rust/Python O(n log n) and constant space. With detailed explanation
Intuition\nThe key observation in this problem is how to find the final position of the robots. Lets assume that we have two robots going towards each other. Le
# Intuition\nThe key observation in this problem is how to find the final position of the robots. Lets assume that we have two robots going towards each other. Lets assume their positions are `[6, 24]`. At timestep 9 they will meet (at position 15) and change directions. At time 11, position of robot 1 will be at position of 13 and position of robot 2 will be at position 17.\n\nBut we do not need to know the position of every specific robot. I will be enough for us to find a position of all robots (without specifying which robot is where). And this is exactly what happens if the robots are behaving as ghosts and going over each other. As you see the positions at t=11 will be `[17, 13]` (same as we calculated previously).\n\nSo we can easily caclulate all of them in $O(n)$ `[p + d if direction == \'R\' else p - d for p, direction in zip(nums, s)]`.\n\n----\n\nNow that we know all the positions, how can we find the total pairwise distance between all points. It is easy to find it in $O(n^2)$, but we need something better.\n\nLets assume our points are `[1, 5, 6, 9]`. What is the distance towards `9`? It is `(9 - 6) + (9 - 5) + (9 - 1)`, which can be rewritten to `9 * 3 - (1 + 5 + 6)`\n\nSimilar to distance towards 6. It will be `6 * 2 - (1 + 5)` (we do not calculate distance between 6 and 9 as we already calculated it previously). So as you see it can be calculated in linear time by calculating prefix sum. But to do this we need to sort an array\n\n\n# Complexity\n- Time complexity: $O(n \\log n)$\n- Space complexity: $O(1)$\n\nConstant time complexity assumes that we are overwriting array of nums (do not do this in Python, only in Rust). Also this assumes that sorting is in place\n\n# Code\n\n```Python []\nclass Solution:\n  def sumDistance(self, nums: List[int], s: str, d: int) -> int:\n    positions = sorted([p + d if direction == \'R\' else p - d for p, direction in zip(nums, s)], reverse=True)\n    res, curr_sum, curr_cnt, mod = 0, 0, 0, 10**9 + 7\n    for v in positions:\n      res = (res + curr_sum - curr_cnt * v) % mod\n      curr_sum += v\n      curr_cnt += 1\n    return res\n```\n```Rust []\nimpl Solution {\n  pub fn sum_distance(mut nums: Vec<i32>, s: String, d: i32) -> i32 {\n    let n = nums.len();\n    let s = s.into_bytes();\n\n    for i in 0 .. n {\n      if s[i] == 76 {\n        nums[i] -= d;\n      } else {\n        nums[i] += d;\n      }\n    }\n    nums.sort_unstable();\n\n    let (mut res, mut curr_sum, mut curr_cnt) = (0i64, 0i64, 0i64);\n    const m: i64 = 1000000007;\n    for i in (0 .. n).rev() {\n      res = (res + curr_sum - curr_cnt * (nums[i] as i64)) % m;\n      curr_sum = (curr_sum + nums[i] as i64) % m;\n      curr_cnt += 1;\n    }\n\n    return ((m + res) % m) as i32;\n  }\n}\n```\n
['Rust']