Count Collisions on a Road - Practice Coding Problems

Count Collisions on a Road - Problem

There are n cars on an infinitely long road. The cars are numbered from 0 to n - 1 from left to right and each car is present at a unique point.

You are given a 0-indexed string directions of length n. directions[i] can be either 'L', 'R', or 'S' denoting whether the i-th car is moving towards the left, towards the right, or staying at its current point respectively. Each moving car has the same speed.

The number of collisions can be calculated as follows:

When two cars moving in opposite directions collide with each other, the number of collisions increases by 2.
When a moving car collides with a stationary car, the number of collisions increases by 1.

After a collision, the cars involved can no longer move and will stay at the point where they collided. Other than that, cars cannot change their state or direction of motion.

Return the total number of collisions that will happen on the road.

Input & Output

Example 1 — Basic Collision

$ Input: directions = "RLRSLL"

› Output: 5

💡 Note: Cars move: R→, ←L, R→, S, ←L, ←L. The R at index 0 collides with L at index 1 (2 collisions). The R at index 2 collides with L at index 4 and L at index 5, and the stationary car gets hit (3 more collisions). Total = 5.

Example 2 — No Collisions

$ Input: directions = "LLRR"

› Output: 0

💡 Note: All L cars move left, all R cars move right. Since L cars are on the left and R cars are on the right, they move away from each other. No collisions occur.

Example 3 — Stationary Cars

$ Input: directions = "RLSR"

› Output: 2

💡 Note: R at index 0 moves right and collides with L at index 1 (2 collisions). They stop. The R at index 3 continues moving right without hitting anything.

Constraints

1 ≤ directions.length ≤ 10⁵
directions[i] is either 'L', 'R', or 'S'

Visualization

Tap to expand

Understanding the Visualization

Input

String with R (right), L (left), S (stationary) cars

Process

Cars move and collide, creating stationary masses

Output

Total number of collision events

Key Takeaway

🎯 Key Insight: Only cars between the leftmost R and rightmost L will be involved in collisions

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that only cars between the leftmost R and rightmost L will be involved in collisions. The optimal approach counts moving cars in this collision zone without simulation. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Approach	O(n)	O(n)	Use a stack to process cars from left to right, handling collisions immediately
Counting Approach	O(n)	O(1)	Count cars that will be involved in collisions without simulation
Simulation Approach	O(n²)	O(n)	Simulate the movement of cars step by step and count collisions as they happen

Stack-Based Approach — Algorithm Steps

Step 1: Iterate through cars from left to right
Step 2: Use stack to track right-moving and stationary cars
Step 3: When left-moving car is found, process collisions with stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Push R/S

Add right-moving and stationary cars to stack

Process L

Left-moving car collides with stack contents

Count & Update

Count collisions and create stationary mass

Code -

solution.c — C

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

int solution(char* directions) {
    int n = strlen(directions);
    char* stack = (char*)malloc(n * sizeof(char));
    int stackSize = 0;
    int collisions = 0;
    
    for (int i = 0; i < n; i++) {
        char c = directions[i];
        if (c == 'R') {
            stack[stackSize++] = c;
        } else if (c == 'S') {
            stack[stackSize++] = c;
        } else { // c == 'L'
            int collisionCount = 0;
            while (stackSize > 0 && stack[stackSize - 1] == 'R') {
                stackSize--;
                collisionCount++;
            }
            
            if (collisionCount > 0) {
                collisions += collisionCount + 1;
                stack[stackSize++] = 'S';
            } else if (stackSize > 0 && stack[stackSize - 1] == 'S') {
                collisions += 1;
            }
        }
    }
    
    free(stack);
    return collisions;
}

int main() {
    char directions[100001];
    fgets(directions, sizeof(directions), stdin);
    directions[strcspn(directions, "\n")] = 0;
    
    int result = solution(directions);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, each car is pushed and popped at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n cars in worst case

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Stack-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler