2731. Movement of Robots LeetCode Solution

In this guide, you will get 2731. Movement of Robots LeetCode Solution with the best time and space complexity. The solution to Movement of Robots problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Movement of Robots solution in C++
Movement of Robots solution in Java
Movement of Robots solution in Python
Additional Resources

2731. Movement of Robots LeetCode Solution image

Problem Statement of Movement of Robots

Some robots are standing on an infinite number line with their initial coordinates given by a 0-indexed integer array nums and will start moving once given the command to move. The robots will move a unit distance each second.
You are given a string s denoting the direction in which robots will move on command. ‘L’ means the robot will move towards the left side or negative side of the number line, whereas ‘R’ means the robot will move towards the right side or positive side of the number line.
If two robots collide, they will start moving in opposite directions.
Return the sum of distances between all the pairs of robots d seconds after the command. Since the sum can be very large, return it modulo 109 + 7.
Note:

For two robots at the index i and j, pair (i,j) and pair (j,i) are considered the same pair.
When robots collide, they instantly change their directions without wasting any time.
Collision happens when two robots share the same place in a moment.

For example, if a robot is positioned in 0 going to the right and another is positioned in 2 going to the left, the next second they’ll be both in 1 and they will change direction and the next second the first one will be in 0, heading left, and another will be in 2, heading right.
For example, if a robot is positioned in 0 going to the right and another is positioned in 1 going to the left, the next second the first one will be in 0, heading left, and another will be in 1, heading right.

Example 1:

Input: nums = [-2,0,2], s = “RLL”, d = 3
Output: 8
Explanation:
After 1 second, the positions are [-1,-1,1]. Now, the robot at index 0 will move left, and the robot at index 1 will move right.
After 2 seconds, the positions are [-2,0,0]. Now, the robot at index 1 will move left, and the robot at index 2 will move right.
After 3 seconds, the positions are [-3,-1,1].
The distance between the robot at index 0 and 1 is abs(-3 – (-1)) = 2.
The distance between the robot at index 0 and 2 is abs(-3 – 1) = 4.
The distance between the robot at index 1 and 2 is abs(-1 – 1) = 2.
The sum of the pairs of all distances = 2 + 4 + 2 = 8.

Example 2:

Input: nums = [1,0], s = “RL”, d = 2
Output: 5
Explanation:
After 1 second, the positions are [2,-1].
After 2 seconds, the positions are [3,-2].
The distance between the two robots is abs(-2 – 3) = 5.

Constraints:

2 <= nums.length <= 105
-2 * 109 <= nums[i] <= 2 * 109
0 <= d <= 109
nums.length == s.length
s consists of 'L' and 'R' only
nums[i] will be unique.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

2731. Movement of Robots LeetCode Solution in C++

class Solution {
 public:
  int sumDistance(vector<int>& nums, string s, int d) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    int ans = 0;
    int prefix = 0;
    vector<int> pos;

    for (int i = 0; i < nums.size(); ++i)
      if (s[i] == 'L')
        pos.push_back(nums[i] - d);
      else
        pos.push_back(nums[i] + d);

    ranges::sort(pos);

    for (int i = 0; i < n; ++i) {
      ans =
          ((ans + static_cast<long>(i) * pos[i] - prefix) % kMod + kMod) % kMod;
      prefix = ((0L + prefix + pos[i]) % kMod + kMod) % kMod;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2731. Movement of Robots LeetCode Solution in Java

class Solution {
  public int sumDistance(int[] nums, String s, int d) {
    final int kMod = 1_000_000_007;
    final int n = nums.length;
    int ans = 0;
    int prefix = 0;
    int[] pos = new int[n];

    for (int i = 0; i < n; ++i)
      if (s.charAt(i) == 'L')
        pos[i] = nums[i] - d;
      else
        pos[i] = nums[i] + d;

    Arrays.sort(pos);

    for (int i = 0; i < n; ++i) {
      ans = (int) (((ans + 1L * i * pos[i] - prefix) % kMod + kMod) % kMod);
      prefix = (int) (((0L + prefix + pos[i]) % kMod + kMod) % kMod);
    }

    return ans;
  }
}
// code provided by PROGIEZ

2731. Movement of Robots LeetCode Solution in Python

class Solution:
  def sumDistance(self, nums: list[int], s: str, d: int) -> int:
    kMod = 1_000_000_007
    ans = 0
    prefix = 0
    pos = sorted([num - d if c == 'L' else num + d
                  for num, c in zip(nums, s)])

    for i, p in enumerate(pos):
      ans = ((ans + i * p - prefix) % kMod + kMod) % kMod
      prefix = ((prefix + p) % kMod + kMod) % kMod

    return ans
 # code by PROGIEZ