We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Collisions on a Road

Number: 2317

Difficulty: Medium

Paid? No

Companies: Arcesium

Problem Description

Given a string representing the directions of n cars on an infinitely long road (where each car’s direction is either 'L' for left, 'R' for right, or 'S' for stationary), determine the total number of collisions that will occur. Two cars colliding while moving in opposite directions add 2 to the count; when a moving car hits a stationary car, the count increases by 1. After a collision, involved cars become stationary and subsequent collisions may happen with neighboring cars.

Key Insights

  • Cars moving left from the beginning and cars moving right at the end will never collide.
  • The effective region where collisions occur is between the first car that isn’t moving left from the start and the last car that isn’t moving right from the end.
  • Once a collision occurs, affected cars become stationary. Thus, every moving car within the effective region will eventually collide.
  • The solution can be derived by counting all moving cars (i.e. 'L' and 'R') within the effective region.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string, as we need to scan the string possibly twice. Space Complexity: O(1) as the solution uses a fixed amount of extra space.

Solution

The approach is as follows:

  1. Identify the first index from the left which is not a left-moving car ('L') because all preceding cars will never collide.
  2. Identify the last index from the right which is not a right-moving car ('R') because all succeeding cars will never collide.
  3. For the substring between these two indices (inclusive), every 'L' or 'R' represents a car that will eventually undergo a collision (even if some collisions add 2, the overall count is simply the sum of moving cars since cars turning stationary cancel future collisions).
  4. Return the total count of moving cars ('L' and 'R') in that effective region.

This solution neatly simulates the non-colliding parts and computes the final collision count without needing to simulate every collision event.

Code Solutions

# Python solution for Count Collisions on a Road

class Solution:
    def countCollisions(self, directions: str) -> int:
        n = len(directions)
        # Find the first index which is not 'L'
        left = 0
        while left < n and directions[left] == 'L':
            left += 1

        # Find the last index which is not 'R'
        right = n - 1
        while right >= 0 and directions[right] == 'R':
            right -= 1

        collisions = 0
        # Count moving cars ('L' or 'R') in the effective region
        for i in range(left, right + 1):
            if directions[i] != 'S':
                collisions += 1
        
        return collisions
← Back to All Questions