Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 2211. Count Collisions on a Road

Given a string of directions for cars moving at equal speed on an infinite road, compute the total collisions where opposite-moving cars collide (+2) and moving cars hitting stationary ones add +1, with collided cars becoming stationary. The challenge is to identify which moving cars will inevitably collide (excluding those that move away off the ends) and count collisions efficiently for up to 1e5 cars.

DESCRIPTION

Input:

directions = "RLS"

Output:

Explanation: The 'R' at position 0 collides with 'L' at position 1 (+2) and 'S' at position 2 (+1). Total: 3 collisions

Constraints:

1 <= directions.length <= 10^5
directions[i] is either 'R', 'L', or 'S'
All moving cars travel at equal speed
The road is infinite (cars moving away from each other never collide)

Understanding the Problem

Let's understand what we're being asked to do. We have a string representing cars on an infinite road, where each character indicates a car's direction: 'R' means moving right, 'L' means moving left, and 'S' means stationary.

All moving cars travel at the same speed. When two cars collide, they both become stationary. We need to count the total number of collisions.

Collision rules: When a right-moving car 'R' meets a left-moving car 'L', they collide (add +2 to count, since both cars collide). When a moving car hits a stationary car 'S', add +1 to count (only the moving car collides).

Key constraint: Cars can only collide if they're moving toward each other. An 'R' at position i can only collide with 'L' or 'S' at positions j > i. An 'L' at position i can only collide with 'R' or 'S' at positions j < i.

Edge cases to consider: What if all cars move in the same direction? (no collisions). What if there are only stationary cars? What if the string is very long (up to 1e5 characters)?

Brute Force Approach

The straightforward approach is to simulate the collisions step-by-step. In each time step, check every pair of adjacent cars to see if they collide (R followed by L or S, or L preceded by R or S). When a collision occurs, mark both cars as stationary and increment the collision counter. Repeat until no more collisions occur. This approach is intuitive but very slow for large inputs because it requires multiple passes through the string.

Visualization

def count_collisions(directions):
    """
    Simulate car collisions step-by-step on an infinite road.
    R = moving right, L = moving left, S = stationary.
    Collisions: R+L or R+S or L+R or S+L (opposite or moving into stationary).
    Returns total collision count.
    """
    # Convert string to list for mutability
    cars = list(directions)
    total_collisions = 0
    
    # Keep simulating until no more collisions occur
    collision_occurred = True
    
    while collision_occurred:
        collision_occurred = False
        
        # Check each adjacent pair for collisions
        i = 0
        while i < len(cars) - 1:
            left_car = cars[i]
            right_car = cars[i + 1]
            
            # Check if collision happens between adjacent cars
            if (left_car == 'R' and right_car == 'L') or \
               (left_car == 'R' and right_car == 'S') or \
               (left_car == 'S' and right_car == 'L'):
                
                # Collision detected - both become stationary
                cars[i] = 'S'
                cars[i + 1] = 'S'
                
                # Count collision points
                if left_car == 'R' and right_car == 'L':
                    # Opposite directions: +2 collision
                    total_collisions += 2
                else:
                    # Moving into stationary: +1 collision
                    total_collisions += 1
                
                collision_occurred = True
                # Skip next position since we just processed it
                i += 2
            else:
                # No collision, move to next pair
                i += 1
    
    return total_collisions

Start collision simulation

0 / 99

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n²) In the worst case, we need O(n) passes through the string, and each pass takes O(n) time to check all positions

Space Complexity: O(n) We need O(n) space to store the modified string as cars become stationary after collisions

Building Intuition

A right-moving car 'R' at position i will collide with every left-moving or stationary car to its right. Similarly, a left-moving car 'L' will collide with every right-moving or stationary car to its left.

The key insight: we don't need to simulate the actual collisions step-by-step. We can count how many collisions will happen by analyzing the string structure.

Simulating each collision individually would be very slow for large inputs (imagine 1e5 cars all colliding). But if we recognize the pattern, we can count collisions in a single pass.

For example, if we see 'RLS', the 'R' will collide with both the 'L' (adding +2) and the 'S' (adding +1), for a total of +3 collisions from this 'R' alone.

Think about a right-moving car 'R' as a 'collision generator'. As you scan left-to-right, every 'R' you encounter will eventually hit all the 'L' and 'S' cars ahead of it.

Similarly, scanning right-to-left, every 'L' will hit all the 'R' and 'S' cars behind it. But be careful not to double-count! If an 'R' and 'L' collide, that's one collision event (worth +2), not two separate events.

Common Mistakes

Double-counting collisions: when R and L collide, that's one event worth +2, not two separate collisions. Be careful not to count it twice when scanning from different directions

Forgetting that cars moving away from each other never collide: an 'L' at position i cannot collide with 'R' or 'S' at positions j > i (they're moving apart)

Attempting to simulate collisions step-by-step for large inputs: this leads to O(n²) or worse time complexity and will timeout for n = 1e5

Not handling stationary cars correctly: 'S' can be hit by both 'R' (from left) and 'L' (from right), and each collision with 'S' adds +1 (not +2)

Off-by-one errors when counting: make sure to correctly track which cars have already collided and become stationary to avoid counting impossible collisions

Optimal Solution

The optimal approach counts collisions in a single pass without simulation. Scan left-to-right: for each 'R', count how many 'L' and 'S' appear to its right (these will all collide with this 'R'). For 'R' hitting 'L', add +2 (both collide). For 'R' hitting 'S', add +1. We can optimize further by maintaining a running count of 'R's seen so far, and when we encounter 'L' or 'S', we know how many 'R's to the left will collide with it. This eliminates the need for nested loops.

Visualization

def count_collisions(directions):
    """
    Count total collisions on an infinite road.
    R = moving right, L = moving left, S = stationary.
    R-L collision adds +2, R-S or L-S collision adds +1.
    """
    # Initialize collision counter
    total_collisions = 0
    
    # Count moving right cars seen so far
    right_count = 0
    
    # Scan left to right
    for i in range(len(directions)):
        car = directions[i]
        
        if car == 'R':
            # Track this R car - it will collide with L/S to its right
            right_count += 1
        elif car == 'L':
            # This L collides with all R's to its left
            # Each R-L collision adds +2
            total_collisions += right_count * 2
            # After collision, this L becomes stationary
            # So it acts like an S for future R's
            right_count += 1
        else:  # car == 'S'
            # This S collides with all R's to its left
            # Each R-S collision adds +1
            total_collisions += right_count
            # S stays stationary, acts as barrier for future R's
            right_count += 1
    
    return total_collisions

Start counting collisions on road

0 / 31

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We make a single pass through the string, processing each character once with constant-time operations

Space Complexity: O(1) We only need a few variables to track counts (number of R's seen, total collisions), regardless of input size

What We've Learned

Boundary elimination pattern: When dealing with collision/interaction problems on a linear structure, first eliminate elements that escape boundaries - cars moving 'L' from the left edge and 'R' from the right edge never collide, so strip leading 'L's and trailing 'R's to focus only on the collision zone.
State transition counting: Instead of simulating each collision step-by-step (which could be O(n²)), recognize that any 'R' or 'L' between the first 'S' or 'L' and last 'S' or 'R' will eventually become stationary - count these transitions directly for O(n) performance.
Collision value calculation: Different collision scenarios produce different counts: 'R' meeting 'L' creates 2 collisions (both cars stop), while a moving car ('R' or 'L') hitting stationary 'S' creates 1 collision - track the pattern of what's already stationary versus still moving.
Single-pass optimization with state tracking: Use one linear scan to identify the collision zone boundaries and count affected cars, avoiding multiple passes or complex data structures - the key insight is that all cars between certain boundaries must collide.
Directional flow analysis: In problems involving opposing movements, recognize that collisions only occur when there's a 'flow reversal' (R followed by L or S) - cars moving in the same direction as their neighbors never interact, simplifying the logic significantly.
Real-world traffic modeling: This pattern applies to packet collision detection in networks, traffic flow optimization, particle physics simulations, and any scenario where entities moving in opposite directions on a constrained path must interact - the boundary elimination technique reduces computational overhead in real-time systems.

Test Your Understanding

Why is string the right data structure for this problem?

string provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 2211. Count Collisions on a Road

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact