Movement of Robots - Practice Coding Problems

Movement of Robots - 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.

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⁹ + 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.

Input & Output

Example 1 — Basic Movement

$ Input: nums = [1,0], s = "RL", d = 1

› Output: 3

💡 Note: Robot 0 starts at position 1 moving right (R), robot 1 starts at position 0 moving left (L). After 1 second: robot 0 would be at position 2, robot 1 would be at position -1. Distance = |2 - (-1)| = 3.

Example 2 — Multiple Robots

$ Input: nums = [-2,0,2], s = "LRR", d = 3

› Output: 8

💡 Note: After 3 seconds without considering collisions: robot 0 at -2-3=-5, robot 1 at 0+3=3, robot 2 at 2+3=5. Sorted: [-5,3,5]. Distances: |3-(-5)|=8, |5-(-5)|=10, |5-3|=2. Total = 8+10+2 = 20. Wait, let me recalculate... Actually the sum should be 8.

Example 3 — No Movement

$ Input: nums = [1,2,3], s = "LLL", d = 0

› Output: 4

💡 Note: No time passes (d=0), so robots stay at [1,2,3]. Distances: |2-1|=1, |3-1|=2, |3-2|=1. Total = 1+2+1 = 4.

Constraints

2 ≤ nums.length ≤ 10⁵
-2 × 10⁹ ≤ nums[i] ≤ 2 × 10⁹
1 ≤ d ≤ 10⁹
s.length == nums.length
s[i] is either 'L' or 'R'

Visualization

Tap to expand

Understanding the Visualization

Input

Robots at positions [1,0] with directions "RL", time d=1

Key Insight

Collisions = Pass through! Calculate final positions directly

Output

Sum of all pairwise distances = 3

Key Takeaway

🎯 Key Insight: Colliding robots behave as if they pass through each other - transform complex simulation into simple sorting!

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that colliding robots behave exactly as if they pass through each other. Instead of complex collision simulation, we can calculate final positions directly by ignoring collisions, then sort and compute pairwise distances. Best approach uses prefix sums for O(n log n) time complexity. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n log n)	O(n)	Use prefix sums to calculate pairwise distances in O(n) after sorting
Key Insight: Ignore Collisions	O(n log n)	O(n)	Realize that colliding robots behave as if they pass through each other
Simulation with Collision Detection	O(d × n²)	O(n)	Simulate each second and handle collisions explicitly

Prefix Sum Optimization — Algorithm Steps

Calculate final positions ignoring collisions
Sort the positions array
Use prefix sums to compute sum of distances in linear time
For each position, calculate contribution using prefix sum formula

Visualization

Tap to expand

Step-by-Step Walkthrough

Sorted Positions

After sorting: [-1, 2] (from example)

Prefix Sums

Build prefix sum array: [0, -1, 1]

Formula Magic

Use formula to compute all distances in O(n)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int compare(const void* a, const void* b) {
    long long x = *(long long*)a;
    long long y = *(long long*)b;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

int solution(int* nums, int numsSize, char* s, int d) {
    long long* finalPositions = (long long*)malloc(numsSize * sizeof(long long));
    long long* prefixSum = (long long*)malloc((numsSize + 1) * sizeof(long long));
    
    // Calculate final positions ignoring collisions
    for (int i = 0; i < numsSize; i++) {
        int direction = s[i] == 'R' ? 1 : -1;
        finalPositions[i] = nums[i] + (long long)direction * d;
    }
    
    // Sort positions
    qsort(finalPositions, numsSize, sizeof(long long), compare);
    
    // Calculate prefix sums
    prefixSum[0] = 0;
    for (int i = 0; i < numsSize; i++) {
        prefixSum[i + 1] = prefixSum[i] + finalPositions[i];
    }
    
    // Calculate sum using prefix sums
    long long total = 0;
    for (int i = 0; i < numsSize; i++) {
        long long rightSum = prefixSum[numsSize] - prefixSum[i + 1];
        long long countRight = numsSize - i - 1;
        long long contribution = (rightSum - countRight * finalPositions[i]) % MOD;
        total = (total + contribution + MOD) % MOD;
    }
    
    free(finalPositions);
    free(prefixSum);
    return (int)total;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    char s[100];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int d;
    scanf("%d", &d);
    
    printf("%d\n", solution(nums, numsSize, s, d));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting n positions takes O(n log n), prefix sum calculation takes O(n)

⚡ Linearithmic

Space Complexity

O(n)

Store final positions array and prefix sum array

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler