Robot Collisions - Practice Coding Problems

Robot Collisions - Problem

There are n robots positioned on a line, each with a unique position, health value, and movement direction.

You are given three inputs:

positions: array of robot positions (0-indexed, unsorted)
healths: array of robot health values
directions: string where each character is 'L' (left) or 'R' (right)

All robots move simultaneously at the same speed. When two robots collide:

The robot with lower health is removed
The surviving robot's health decreases by 1
If both have equal health, both are removed

Return the final health values of surviving robots in their original input order. If no robots survive, return an empty array.

Input & Output

Example 1 — Basic Collision

$ Input: positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"

› Output: [2,17,9,15,10]

💡 Note: All robots move right in same direction, so no collisions occur. All survive with original health.

Example 2 — Head-on Collision

$ Input: positions = [3,5,2,6], healths = [10,10,15,12], directions = "RLRL"

› Output: [14]

💡 Note: After sorting by position: R(H:15) at pos 2, L(H:10) at pos 3, R(H:10) at pos 5, L(H:12) at pos 6. Multiple collisions result in one survivor with health 14.

Example 3 — No Survivors

$ Input: positions = [1,2,3,4,5], healths = [1,1,1,1,1], directions = "RLRLR"

› Output: []

💡 Note: Alternating directions with equal health cause all robots to destroy each other in collisions.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ positions[i] ≤ 10⁹
1 ≤ healths[i] ≤ 10⁹
directions[i] is either 'L' or 'R'
All values in positions are distinct

Visualization

Tap to expand

Understanding the Visualization

Initial Setup

Robots positioned on line with health and direction

Collision Detection

Find robots moving toward each other

Battle Resolution

Weaker robot removed, survivor's health decreases

Final Survivors

Return remaining robots' health in original order

Key Takeaway

🎯 Key Insight: Only R→L collisions matter - use stack to efficiently process robots by position

Asked in

G Google 35 a Amazon 28 M Microsoft 22 f Facebook 18

The key insight is that only robots moving toward each other can collide - specifically right-moving robots meeting left-moving robots. The optimal stack-based approach sorts robots by position and processes collisions efficiently in a single pass. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n³)	O(n)	Simulate robot movement and detect all collisions iteratively
Stack-Based Collision Detection	O(n log n)	O(n)	Sort by position and use stack to efficiently handle right-moving robots colliding with left-moving ones

Brute Force Simulation — Algorithm Steps

Step 1: Simulate robot movement for each time step
Step 2: Check all pairs for collisions (same position)
Step 3: Remove weaker robots and damage survivors
Step 4: Repeat until no collisions occur

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

All robots with positions, health, and directions

Check Collisions

Find all pairs that will collide

Resolve First Collision

Remove weaker robot, damage survivor

Repeat

Continue until no more collisions

Code -

solution.c — C

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

typedef struct {
    int pos, health, origIndex;
    char dir;
} Robot;

int* solution(int* positions, int* healths, char* directions, int n, int* returnSize) {
    Robot* robots = malloc(n * sizeof(Robot));
    int robotCount = n;
    
    for (int i = 0; i < n; i++) {
        robots[i] = (Robot){positions[i], healths[i], i, directions[i]};
    }
    
    while (1) {
        int collisionFound = 0;
        int ci = -1, cj = -1;
        
        for (int i = 0; i < robotCount && !collisionFound; i++) {
            for (int j = i + 1; j < robotCount; j++) {
                if (robots[i].pos == robots[j].pos || 
                   (robots[i].pos < robots[j].pos && robots[i].dir == 'R' && robots[j].dir == 'L')) {
                    ci = i; cj = j;
                    collisionFound = 1;
                    break;
                }
            }
        }
        
        if (!collisionFound) break;
        
        if (robots[ci].health > robots[cj].health) {
            robots[ci].health--;
            for (int k = cj; k < robotCount - 1; k++) {
                robots[k] = robots[k + 1];
            }
            robotCount--;
        } else if (robots[cj].health > robots[ci].health) {
            robots[cj].health--;
            for (int k = ci; k < robotCount - 1; k++) {
                robots[k] = robots[k + 1];
            }
            robotCount--;
        } else {
            int maxIdx = ci > cj ? ci : cj;
            int minIdx = ci < cj ? ci : cj;
            for (int k = maxIdx; k < robotCount - 1; k++) {
                robots[k] = robots[k + 1];
            }
            robotCount--;
            for (int k = minIdx; k < robotCount - 1; k++) {
                robots[k] = robots[k + 1];
            }
            robotCount--;
        }
    }
    
    int* survivors = calloc(n, sizeof(int));
    for (int i = 0; i < robotCount; i++) {
        survivors[robots[i].origIndex] = robots[i].health;
    }
    
    int* result = malloc(n * sizeof(int));
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (survivors[i] > 0) {
            result[count++] = survivors[i];
        }
    }
    
    *returnSize = count;
    free(robots);
    free(survivors);
    return result;
}

int main() {
    // Input parsing for arrays and string
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int positions[1000], posCount = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        positions[posCount++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    int healths[1000], healthCount = 0;
    token = strtok(line + 1, ",]");
    while (token) {
        healths[healthCount++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    char directions[1001];
    fgets(directions, sizeof(directions), stdin);
    directions[strcspn(directions, "\n")] = 0;
    
    int returnSize;
    int* result = solution(positions, healths, directions, posCount, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Multiple simulation rounds with O(n²) collision checks each

⚠ Quadratic Growth

Space Complexity

O(n)

Store robot states and track survivors

⚡ Linearithmic Space

32.4K Views

Medium-High Frequency

~35 min Avg. Time

892 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

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler