Movement of Robots
Problem Description
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 10^9 + 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.
Explanation
We have robots on a number line:
- Each robot starts at a specific position given in the array nums.
- Robots move in the direction specified by the string s:
- 'R' → Right (position increases).
- 'L' → Left (position decreases).
- If two robots meet at the same position (collision), they instantly reverse their directions.
Our goal is:
- Simulate this movement for d seconds.
- Compute the total sum of distances between every pair of robots after d seconds.
- Return the result modulo 10^9 + 7.
Examples
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.
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 <= 10^5
- -2 * 10^9 <= nums[i] <= 2 * 10^9
- 0 <= d <= 10^9
- nums.length == s.length
- s consists of 'L' and 'R' only
- nums[i] will be unique.
The solution for the given problem statement can be solved using the Brute Force approach/prefix sum approach and each of the approach has its own benefits on the specified constraints.
Brute Force Approach
Intuition
The instant approach that came to our mind is , let's simulate the movement of each robot i.e for every second, we will update the position of each robot based on its direction. If two or more robots share the same position at any moment, they collide and reverse their directions.
But how can we detect collision of two robots ?
Can we think of a way in which we get to know whether two robots collide at an index ?
Before knowing the data structure, we have to detect the position of the collision and the robots that collide. This requirement gives the intuition of using a Map/HashMap data structure!!
What is a HashMap ?
HashMap is a data structure that stores key-value pairs.
If any duplicate Key enters the map, it just updates the value of that particular key to the newly entered value.
The Map data structure exactly aligns with our needs.
Operations we can perform on a map are:-
- Insertion
- Updation
- Search
- Removal
Since, we figured out the data structure to be used to know about the collision. Let's now think what shall we assign as the key-value pairs to be stored.
We know that the collision will happen among two robots in a single index/position. So, let's define the map with index (Integer) as the key and the robots value as the values (list of robot indices).
That means a key-value pair in the map will contain <index, array/list of robot indices>.
Once, we get to know the robots that collide at a particular index we have to reverse their directions.
Once the robots have moved for d seconds, we will compute the absolute distance between every pair of robots using two nested loops.
Approach
Initialize: MOD to 10^9+7 , positionsMap.
Simulate movement for d seconds:
- Loop for t from 0 to d - 1:
- Create a positionMap (dictionary) to track robots' positions.
- For each robot i (0 to n - 1): If directions[i] is 'R', increment nums[i] (move right).
If directions[i] is 'L', decrement nums[i] (move left).
Add nums[i] as a key in positionMap, mapping to a list of robot indices at that position.
- Handle collisions:
- For each group of indices in positionMap: If more than one robot is in the same position:
For each robot in the group, reverse its direction ('R' → 'L', 'L' → 'R').
- For each group of indices in positionMap: If more than one robot is in the same position:
Calculate the sum of distances between all pairs of robots:
- Initialize sumDistances = 0.
- For each pair of robots (i, j) where i<j:
- Add the absolute distance |nums[i] - nums[j]| to sumDistances.
- Take modulo MOD to avoid overflow.
Return the final result: Cast sumDistances to an integer and return.
Dry-Run
nums = [5, 10, 15, 20, 25], s = "RLLRR", d = 3
Output: 114
Initial Setup:
- Positions: nums = [5, 10, 15, 20, 25]
- Directions: s = "RLLRR" → directions = ['R', 'L', 'L', 'R', 'R']
- Simulation Time: d = 3
- MOD: 10^9+7
Step-by-Step SimulationBefore Simulation (Initial State):
- Positions: nums = [5, 10, 15, 20, 25]
- Directions: ['R', 'L', 'L', 'R', 'R']
At t = 1 (First Second):
Update Positions:
- Robot 0 (nums[0]): Moving right → nums[0] = 5 + 1 = 6
- Robot 1 (nums[1]): Moving left → nums[1] = 10 - 1 = 9
- Robot 2 (nums[2]): Moving left → nums[2] = 15 - 1 = 14
- Robot 3 (nums[3]): Moving right → nums[3] = 20 + 1 = 21
- Robot 4 (nums[4]): Moving right → nums[4] = 25 + 1 = 26
Positions After Update: nums = [6, 9, 14, 21, 26]
Detect Collisions:
Build positionMap: positionMap = {
6: [0],
9: [1],
14: [2],
21: [3],
26: [4]
}
No collisions (each position is unique).
Directions After Collision Handling: ['R', 'L', 'L', 'R', 'R']
At t = 2 (Second Second):
Update Positions:
- Robot 0 (nums[0]): Moving right → nums[0] = 6 + 1 = 7
- Robot 1 (nums[1]): Moving left → nums[1] = 9 - 1 = 8
- Robot 2 (nums[2]): Moving left → nums[2] = 14 - 1 = 13
- Robot 3 (nums[3]): Moving right → nums[3] = 21 + 1 = 22
- Robot 4 (nums[4]): Moving right → nums[4] = 26 + 1 = 27
Positions After Update: nums = [7, 8, 13, 22, 27]
Detect Collisions:
Build positionMap:yamlCopy codepositionMap = {
7: [0],
8: [1],
13: [2],
22: [3],
27: [4]
}
No collisions (each position is unique).
Directions After Collision Handling: ['R', 'L', 'L', 'R', 'R']
At t = 3 (Third Second):
Update Positions:
- Robot 0 (nums[0]): Moving right → nums[0] = 7 + 1 = 8
- Robot 1 (nums[1]): Moving left → nums[1] = 8 - 1 = 7
- Robot 2 (nums[2]): Moving left → nums[2] = 13 - 1 = 12
- Robot 3 (nums[3]): Moving right → nums[3] = 22 + 1 = 23
- Robot 4 (nums[4]): Moving right → nums[4] = 27 + 1 = 28
Positions After Update: nums = [8, 7, 12, 23, 28]
Detect Collisions:
Build positionMap: positionMap = {
8: [0],
7: [1],
12: [2],
23: [3],
28: [4]
}
No collisions (each position is unique).
Directions After Collision Handling: ['R', 'L', 'L', 'R', 'R']
Calculate the Sum of Distances:
The final positions are: nums = [8, 7, 12, 23, 28]
Calculate the distances between all pairs:
- Pair (0,1): |8 - 7| = 1
- Pair (0,2): |8 - 12| = 4
- Pair (0,3): |8 - 23| = 15
- Pair (0,4): |8 - 28| = 20
- Pair (1,2): |7 - 12| = 5
- Pair (1,3): |7 - 23| = 16
- Pair (1,4): |7 - 28| = 21
- Pair (2,3): |12 - 23| = 11
- Pair (2,4): |12 - 28| = 16
- Pair (3,4): |23 - 28| = 5
Sum of distances: 1 + 4 + 15 + 20 + 5 + 16 + 21 + 11 + 16 + 5 = 114
114 % 1,000,000,007 = 114
Output: 114
Brute Force in all Languages
1. C++ Try on Compiler
class Solution {
public:
int sumDistance(vector<int>& nums, string s, int d) {
int n = nums.size();
const long MOD = 1'000'000'007;
// Convert string s to a character array for easier manipulation
vector<char> directions(s.begin(), s.end());
// Simulate the movement of robots for d seconds
for (int t = 0; t < d; t++) {
unordered_map<int, vector<int>> positionMap;
// Update positions based on directions
for (int i = 0; i < n; i++) {
if (directions[i] == 'R') {
nums[i]++;
} else {
nums[i]--;
}
// Record positions for potential collision detection
positionMap[nums[i]].push_back(i);
}
// Handle collisions
for (auto& entry : positionMap) {
if (entry.second.size() > 1) {
for (int index : entry.second) {
// Reverse direction
directions[index] = (directions[index] == 'R') ? 'L' : 'R';
}
}
}
}
// Calculate the sum of distances between all pairs
long sumDistances = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
sumDistances += abs(nums[i] - nums[j]);
sumDistances %= MOD; // Avoid overflow
}
}
return static_cast<int>(sumDistances);
}
};2. Java Try on Compiler
class Solution {
public int sumDistance(int[] nums, String s, int d) {
int n = nums.length;
long MOD = 1_000_000_007;
// Convert string s to an array for easier manipulation
char[] directions = s.toCharArray();
// Simulate the movement of robots for d seconds
for (int t = 0; t < d; t++) {
Map<Integer, List<Integer>> positionMap = new HashMap<>();
// Update positions based on directions
for (int i = 0; i < n; i++) {
if (directions[i] == 'R') {
nums[i]++;
} else {
nums[i]--;
}
// Record positions for potential collision detection
positionMap.putIfAbsent(nums[i], new ArrayList<>());
positionMap.get(nums[i]).add(i);
}
// Handle collisions
for (List<Integer> collisionGroup : positionMap.values()) {
if (collisionGroup.size() > 1) {
for (int index : collisionGroup) {
// Reverse direction
directions[index] = directions[index] == 'R' ? 'L' : 'R';
}
}
}
}
// Calculate the sum of distances between all pairs
long sumDistances = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
sumDistances += Math.abs(nums[i] - nums[j]);
sumDistances %= MOD; // Avoid overflow
}
}
return (int) sumDistances;
}
}3. Python Try on Compiler
class Solution:
def sumDistance(self, nums: List[int], s: str, d: int) -> int:
n = len(nums)
MOD = 1_000_000_007
# Convert string s to a list of characters for easier manipulation
directions = list(s)
# Simulate the movement of robots for d seconds
for t in range(d):
position_map = {}
# Update positions based on directions
for i in range(n):
if directions[i] == 'R':
nums[i] += 1
else:
nums[i] -= 1
# Record positions for potential collision detection
if nums[i] not in position_map:
position_map[nums[i]] = []
position_map[nums[i]].append(i)
# Handle collisions
for positions in position_map.values():
if len(positions) > 1:
for index in positions:
# Reverse direction
directions[index] = 'L' if directions[index] == 'R' else 'R'
# Calculate the sum of distances between all pairs
sum_distances = 0
for i in range(n):
for j in range(i + 1, n):
sum_distances += abs(nums[i] - nums[j])
sum_distances %= MOD # Avoid overflow
return sum_distances4. JavaScript Try on Compiler
var sumDistance = function(nums, s, d) {
const n = nums.length;
const MOD = 1_000_000_007;
// Convert string s to an array of characters for easier manipulation
const directions = [...s];
// Simulate the movement of robots for d seconds
for (let t = 0; t < d; t++) {
const positionMap = new Map();
// Update positions based on directions
for (let i = 0; i < n; i++) {
if (directions[i] === 'R') {
nums[i]++;
} else {
nums[i]--;
}
// Record positions for potential collision detection
if (!positionMap.has(nums[i])) {
positionMap.set(nums[i], []);
}
positionMap.get(nums[i]).push(i);
}
// Handle collisions
for (const [_, positions] of positionMap) {
if (positions.length > 1) {
for (const index of positions) {
// Reverse direction
directions[index] = directions[index] === 'R' ? 'L' : 'R';
}
}
}
}
// Calculate the sum of distances between all pairs
let sumDistances = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
sumDistances += Math.abs(nums[i] - nums[j]);
sumDistances %= MOD; // Avoid overflow
}
}
return sumDistances;
};Time Complexity: O(d*n + n^2)
Outer Loop (Simulating Movement for d Seconds):
- Runs for d iterations, updating positions of robots.
- Time Complexity: O(d).
Inner Loop (Updating Positions and Handling Collisions):
- For each robot, we update its position and track it in positionMap.
- Time Complexity per iteration: O(n).
Collision Handling:
- For each position in positionMap, we check for multiple robots and reverse their directions.
- Time Complexity per iteration: O(n).
Final Distance Calculation:
- Calculate the sum of distances between all pairs of robots using a nested loop.
- Time Complexity: O(n^2).
Overall Time complexity is :
O(d)*O(n) + O(n) + O(n^2) = O( d*n + n^2)
Space Complexity: O(n)
Auxiliary Space Complexity:
- Position Map: Stores positions and indices of robots. Worst case: O(n).
- Direction Array: Stores the directions of robots, with space complexity of O(n).
Thus, the auxiliary space complexity is O(n).
Total Space Complexity:
- Input Storage: nums array and the converted directions array both take O(n).
- Auxiliary Space: The positionMap and directions array contribute O(n).
Therefore, the total space complexity is O(n).
The Brute Force solution is close to O(n^2) runtime solution which will result in Time Limit Exceeded if the n is less than or equal to 100000.
The interviewer won't be happy with the solution , so we need to figure out a optimal approach in order to move further in the interview.
Optimal Approach
Intuition
Before moving to the optimal approach , if we take a look at the constraints where the array size is >=2 and less than or equal to 10^5, we cant go for O(n^2) solution , so the we need to figure out an optimal approach whose runtime is lesser than O(n^2).
Alright, this means we have to figure out either a linear solution or a logarithmic solution.
In the given question , we are given two tasks in order to return the output , those are:-
- Finding the final position of robots after d seconds including the rules of collision.
- Finding the sum of the absolute difference between all the final position of robots.
Let's analyse how we can optimize each of the objectives!!
Moving to the first objective which is to find the final position of each robot after d seconds.
For instance,
nums = [2, 4] (initial positions of two robots).
s = "RL" (Robot 0 moves right, Robot 1 moves left).
d = 3 (time in seconds).
What happens with the simulation ?
After 1 second: Robot 0 moves to 3 (right). Robot 1 moves to 3 (left). They collide at position 3.
When robots collide: Robot 0 reverses direction and starts moving left. Robot 1 reverses direction and starts moving right.
After 1 more second: Robot 0 moves from 3 to 2 (left). Robot 1 moves from 3 to 4 (right).
After the final 1 second: Robot 0 moves from 2 to 1 (left). Robot 1 moves from 4 to 5 (right).
Final positions considering collisions: [1, 5] of robot 0 and robot 1 respectively.
The robots changed their direction when they collided. But, don't you think that if they wouldn't have change the directions after the collision , the distance between both would be the same ?
Let's simulate the example ignoring the collisions ?
Robot 0 starts at 2. Robot 1 starts at 4.
After 1 second: Robot 0 moves to 3 (right). Robot 1 moves to 3 (left).
Ignore the collision rules !!
After 1 more second: robot 0 moves from 3 to 4 (right direction) and the robot 1 moves from 3 to 2 (left direction).
After final 1 second: robot 0 moves form 4 to 5 (right direction) and the robot 1 moves from 2 to 1 (left direction).
Final positions without considering collisions: [5, 1] of robot 0 and robot 1 respectively.
If we observe the absolute difference between the two robots considering collision is |1-5| =5
and, the absolute difference between the two robots excluding the collision is |5-1|=5.
5=5? Yes, this means collision have no role in finding the answer.
The first task we need to do is to calculate the final positions of each robot of nums array and store it into a list/array.
Why can't we just modify the same array and store the updated value in the given array ?
If we see the constraints that each value of the nums array is -2 * 10^9 <= nums[i] <= 2 * 10^9. There, will be a edge case which wont fit inside the nums array of int data type.
When,
- nums[0]==2000000000 && nums[1]==-2000000000
- nums[2]==2000000000 && nums[1]==0 && nums[0]==-2
We will be unable to modify the original array because these cases results in overflow of int data-type size.
Our first objective is sorted !!
Moving to our next objective i.e to find the sum of distances between all pairs of robots after d seconds.
If we take a naive approach to move with pairwise calculation using nested loops will end up in a time complexity of O(n^2) which will result in Time Limit Exceeded as the constraints are limited to, array size >=2 and less than or equal to 10^5.
The runtime is O(n^2) because of repeatedly calculating the previous numbers again and again !!
Wait !! Did we just say previous checks ?? What approach/technique comes to our mind when we say "previous checks" ?
Yes , it's the prefix sum approach. Now , we have to figure out the algorithm for the data to be stored in the prefix array.
Before moving to the algorithm, shall we sort the position array? Yes.
Why to sort the position array ?
Sorted positions make this easier because for any robot at position i, all the robots to its left are guaranteed to have a smaller position value. This avoids needing to calculate pairwise distances repeatedly.
Using prefix sums, we can compute the contributions in a single pass without calculating pairwise distances manually. That is we will achieve a linear runtime.
For a robot at index i, the sum of distances to all robots to its left is:
distance=(distance+(i * position[i]−prefix))%modulo
What does "i⋅position[i]-prefix" mean?
This term represents the total distance if all iii robots to the left were at the same position as position[i].
- For example, if position[i]=10 and there are i=3 robots to the left, the total distance from these robots to position[i] would be 3⋅10=30.
"prefix" is the actual sum of the positions of all robots to the left of position[i].
- The prefix sum helps us avoid recalculating the sum of left positions for every robot.
The difference: i⋅position[i]−prefix gives the total contribution to the distance between position[i] and all robots to its left.
Confused with the formula ?
For instance
Input: nums = [2, 4, 6] , s = "RRL" , d = 2
After d=2 seconds, Final positions: [4, 6, 4] -> sort -> [4,4,6]
The formula we will be using is : distance=(distance+(i * position[i]−prefix))%modulo
For i = 0 (position[i] = 4):
There are no robots to the left, so: Contribution = 0 • 4
• Update prefix: prefix = 0 + 4
• Total distance remains: distance = 0
For i=1 (position[i]=4):
Contribution from the left: Contribution=1⋅4−4=0
• Update prefix: prefix=4+4=8
• Total distance remains: distance=0
For i=2(position[i]=6):
Contribution from the left: Contribution=2⋅6−8=4.
• Update prefix: prefix=8+6=14.
• Update total distance: distance=0+4=4
The answer is 4.
Approach
Define constants and initialize variables:
- Set modulo to 10^9+7 for modular arithmetic.
- Determine the number of robots n.
Calculate final positions:
- Create an array position to store the final positions of the robots after d seconds.
- For each robot:
- If the robot is moving left ('L'), subtract d from its position in nums.
- If the robot is moving right ('R'), add d to its position in nums.
Sort the final positions:
- Sort the position array in non-decreasing order.
Initialize variables for distance calculation:
- Set distance to 0 (to accumulate the total distance between pairs).
- Set prefix to 0 (to track the sum of positions to the left).
Iterate over sorted positions:
- For each robot at index i:
- Calculate its contribution to the total distance:
- Multiply its position by the number of robots to its left (i).
- Subtract the prefix sum of left positions.
- Add this contribution to distance and take modulo .
- Update the prefix sum to include the current robot’s position.
- Calculate its contribution to the total distance:
Return the result: Return the value of distance modulo 10^9 + 7.
Dry-Run
nums = [3, 7, 1, 5] s = "RLLR" d = 3
Step 1: Calculate Final Positions
For each robot:
- If the direction is 'R', add d to the position.
- If the direction is 'L', subtract d from the position.
Iteration:
- Robot 0: nums[0] = 3, s[0] = 'R' → 3 + 3 = 6
- Robot 1: nums[1] = 7, s[1] = 'L' → 7 - 3 = 4
- Robot 2: nums[2] = 1, s[2] = 'L' → 1 - 3 = -2
- Robot 3: nums[3] = 5, s[3] = 'R' → 5 + 3 = 8
Final Positions (Unsorted): [6, 4, -2, 8]
Step 2: Sort the Positions
Sort the position array in ascending order:
Sorted Positions: [-2, 4, 6, 8]
Step 3: Initialize Variables
- Initialize distance = 0 (this accumulates the total sum of distances).
- Initialize prefix = 0 (this stores the sum of positions to the left).
Step 4: Iterate Over the Sorted Positions
We calculate the contribution of each robot to the total distance using:
distance = (distance + (i * position[i] - prefix)) % modulo
Update the prefix sum as:
prefix = prefix + position[i]
Iteration 1 (i = 0):
- position[0] = -2
- Contribution:
distance = (0 + (0 * -2 - 0)) % modulo = 0 - Update prefix:
prefix = 0 + (-2) = -2
Iteration 2 (i = 1):
- position[1] = 4
- Contribution:
distance = (0 + (1 * 4 - (-2))) % modulo
distance = (0 + (4 + 2)) % modulo = 6 - Update prefix:
prefix = -2 + 4 = 2
Iteration 3 (i = 2):
- position[2] = 6
- Contribution:
distance = (6 + (2 * 6 - 2)) % modulo
distance = (6 + (12 - 2)) % modulo = 16 - Update prefix:
prefix = 2 + 6 = 8
Iteration 4 (i = 3):
- position[3] = 8
- Contribution:
distance = (16 + (3 * 8 - 8)) % modulo
distance = (16 + (24 - 8)) % modulo = 32 - Update prefix:
prefix = 8 + 8 = 16
Step 5: Return the Result
The final value of distance is 32. Since it is already less than 10^9 + 7, no further adjustments are needed.
Output: 32
Final Summary of Contributions:
For each position:
- -2: No contribution (it’s the first position).
- 4: Adds 6 to the total distance.
- 6: Adds 10 to the total distance.
- 8: Adds 16 to the total distance.
Total Distance: 6 + 10 + 16 = 32
Optimal Code in all Languages.
1. C++ Try on Compiler
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int sumDistance(vector<int>& nums, string s, int d) {
// Define modulo constant for the result
const int modulo = 1e9 + 7;
// Get the size of the input array
int n = nums.size();
// Create an array to store final positions
vector<long> position(n);
// Calculate final positions based on direction and distance
for (int i = 0; i < n; i++) {
position[i] = (s[i] == 'L' ? -1L : 1L) * d + nums[i];
}
// Sort the position array
sort(position.begin(), position.end());
// Initialize variables for distance sum and prefix sum
long distance = 0;
long prefix = 0;
// Iterate through sorted positions to calculate the total distance
for (int i = 0; i < n; i++) {
distance = (distance + (i * position[i] - prefix)) % modulo;
prefix += position[i];
}
// Return the total distance as an integer
return (int) distance;
}
};
2. Java Try on Compiler
class Solution {
public int sumDistance(int[] nums, String s, int d) {
// Define modulo constant for the result
final int modulo = (int) 1e9 + 7;
// Get the size of the input array
final int n = nums.length;
// Create an array to store final positions
long[] position = new long[n];
// Calculate final positions based on direction and distance
for (int i = 0; i < n; i++) {
position[i] = (s.charAt(i) == 'L' ? -1L : 1L) * d + nums[i];
}
// Sort the position array
Arrays.sort(position);
// Initialize variables for distance sum and prefix sum
long distance = 0;
long prefix = 0;
// Iterate through sorted positions to calculate the total distance
for (int i = 0; i < n; i++) {
distance = (distance + (i * position[i] - prefix)) % modulo;
prefix += position[i];
}
// Return the total distance as an integer
return (int) distance;
}
}
3. Python Try on Compiler
class Solution:
def sumDistance(self, nums: List[int], s: str, d: int) -> int:
# Define modulo constant for the result
MOD = int(1e9 + 7)
# Get the size of the input array
n = len(nums)
# Create an array to store final positions
position = [0] * n
# Calculate final positions based on direction and distance
for i in range(n):
position[i] = (d if s[i] == 'R' else -d) + nums[i]
# Sort the position array
position.sort()
# Initialize variables for distance sum and prefix sum
distance = 0
prefix = 0
# Iterate through sorted positions to calculate the total distance
for i in range(n):
distance = (distance + (i * position[i] - prefix)) % MOD
prefix += position[i]
# Return the total distance as an integer
return distance4. JavaScript Try on Compiler
var sumDistance = function(nums, s, d) {
// Define modulo constant for the result
const MOD = 1e9 + 7;
// Get the size of the input array
const n = nums.length;
// Create an array to store final positions
const position = new Array(n);
// Calculate final positions based on direction and distance
for (let i = 0; i < n; i++) {
position[i] = (s[i] === 'R' ? d : -d) + nums[i];
}
// Sort the position array
position.sort((a, b) => a - b);
// Initialize variables for distance sum and prefix sum
let distance = 0;
let prefix = 0;
// Iterate through sorted positions to calculate the total distance
for (let i = 0; i < n; i++) {
distance = (distance + (i * position[i] - prefix)) % MOD;
prefix += position[i];
}
// Return the total distance as an integer
return distance;
};Time Complexity: O(nlogn)
Final Position Calculation:
- The loop that computes the position array iterates over the input array nums of size n.
- Time complexity: O(n).
Sorting the Position Array:
- Sorting the array of size n requires O(nlogn) time.
- Time complexity: O(nlogn).
Distance Calculation:
- The loop to calculate the total distance iterates over the sorted position array of size n.
- Time complexity: O(n).
Overall Time Complexity: The dominant term is the sorting step, so the overall time complexity is: O(nlogn)
Space Complexity: O(n)
Auxiliary Space Complexity refers to the extra space or temporary storage that an algorithm uses, apart from the input data.
Intermediate Array (position): A array is created of size n which accounts for O(n)
So the total auxiliary space is O(n).
Total Space Complexity
Input Storage: The input array nums and string s are stored in memory: nums: O(n), string for direction accounts for O(n) and d accounts for O(1).
Auxiliary Space: Includes the position array and sorting space: O(n).
Total Space Complexity: The total space complexity is: O(n)+O(n)= O(2n) = O(n)
Learning Tip
We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with a speed of 1 unit per second. Some of the ants move to the left, the other move to the right.
When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions does not take any additional time.
When an ant reaches one end of the plank at a time t, it falls out of the plank immediately.
Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right, return the moment when the last ant(s) fall out of the plank.
You are given a 0-indexed integer array nums of size n and a positive integer k.
We call an index i in the range k <= i < n - k good if the following conditions are satisfied:
- The k elements that are just before the index i are in non-increasing order.
- The k elements that are just after the index i are in non-decreasing order.
Return an array of all good indices sorted in increasing order.