Leetcode 2211. Count Collisions on a Road

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)?

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.

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

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.

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.

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

• 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.