Movement of Robots — LeetCode 2731 Python Solution

The problem

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.

Example

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.

Python solution

class Solution:
    def sumDistance(self, nums: List[int], s: str, d: int) -> int:
        mod = 10**9 + 7
        for i, c in enumerate(s):
            nums[i] += d if c == "R" else -d
        nums.sort()
        ans = s = 0
        for i, x in enumerate(nums):
            ans += i * x - s
            s += x
        return ans % mod

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2731. Movement of Robots is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems