Count Collisions on a Road

Medium

Asked by:

37 views

Topics:

ArraysStringsTwo Pointers

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.

Example 1:

Input: directions = "RLRSLL"
Output: 5
Explanation:
The collisions that will happen on the road are:
- Cars 0 and 1 will collide with each other. Since they are moving in opposite directions, the number of collisions becomes 0 + 2 = 2.
- Cars 2 and 3 will collide with each other. Since car 3 is stationary, the number of collisions becomes 2 + 1 = 3.
- Cars 3 and 4 will collide with each other. Since car 3 is stationary, the number of collisions becomes 3 + 1 = 4.
- Cars 4 and 5 will collide with each other. After car 4 collides with car 3, it will stay at the point of collision and get hit by car 5. The number of collisions becomes 4 + 1 = 5.
Thus, the total number of collisions that will happen on the road is 5.

Example 2:

Input: directions = "LLRR"
Output: 0
Explanation:
No cars will collide with each other. Thus, the total number of collisions that will happen on the road is 0.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What characters are allowed in the input string `directions` beyond 'L', 'R', and 'S'? Should I expect invalid characters, and if so, how should I handle them?
What is the maximum possible length of the `directions` string?
If no collisions occur, should I return 0?
Are the cars considered to be points or do they have a physical size?
Does the road have any boundaries or is it infinitely long in both directions?

Brute Force Solution

Approach

The brute force approach to counting collisions involves simulating every car's movement one step at a time. We track each car and check for crashes after each simulated step. This is like watching a slow-motion replay of the entire road to see every potential collision.

Here's how the algorithm would work step-by-step:

Start by looking at the first car and where it's going.
Then, look at the second car and see where it's going.
Compare the directions of the first and second cars. If they are headed towards each other, or if the car behind is faster and in the same direction then they will eventually crash.
Keep track of how many crashes you find.
Continue this process of comparing each car with every other car. Make sure you don't count the same crash twice (e.g., car 1 crashing into car 2 is the same collision as car 2 crashing into car 1).
The total number of crashes you've counted is your answer.

Code Implementation

def count_collisions_brute_force(directions):
    total_collisions = 0
    road_length = len(directions)

    # Iterate through each car
    for first_car_index in range(road_length):
        for second_car_index in range(first_car_index + 1, road_length):
            first_car_direction = directions[first_car_index]
            second_car_direction = directions[second_car_index]

            # Check if cars are moving towards each other
            if (first_car_direction == 'R' and second_car_direction == 'L'):
                total_collisions += 1

            # Check if the first car is going RIGHT and the second car is stopped.
            elif (first_car_direction == 'R' and second_car_direction == 'S'):
                total_collisions += 1

            # Check if the first car is stopped and the second car is going LEFT.
            elif (first_car_direction == 'S' and second_car_direction == 'L'):
                total_collisions += 1

    return total_collisions

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach involves comparing each car with every other car to detect potential collisions. For an input of n cars, the algorithm iterates through each car and compares it with the remaining n-1 cars. This results in nested iterations where the outer loop runs n times and the inner loop (on average) runs n/2 times. Therefore, the total number of operations is proportional to n * (n/2), which simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The described brute force approach iterates through the input string of car directions, comparing each car's direction with every other car's direction. It only uses a few integer variables to keep track of the indices of the cars being compared and the total number of collisions. Therefore, the auxiliary space required does not depend on the input size N (the length of the directions string). The space used remains constant regardless of the number of cars, resulting in O(1) space complexity.

Optimal Solution

Approach

The optimal strategy avoids simulating every car movement. Instead, we focus on the stable parts of the road where no collisions occur, and count collisions at the boundaries. This drastically reduces the amount of work needed.

Here's how the algorithm would work step-by-step:

Look at the road from the beginning. Keep going until you see the first car going right.
Keep track of all the cars moving in the same direction to the right. These cars will not collide with each other.
Once you see a car that is *not* moving to the right, it means that the previous cars going to the right will eventually collide with it. Count those collisions.
Treat all the cars after the collision as stopped cars, because after the collision no car can move away from this point.
Look at the road from the end. Keep going until you see the first car going left.
Keep track of all the cars moving in the same direction to the left. These cars will not collide with each other.
Once you see a car that is *not* moving to the left, it means that the previous cars going to the left will eventually collide with it. Count those collisions.
Treat all the cars after the collision as stopped cars, because after the collision no car can move away from this point.
Add up all the collisions you've counted. Also, count the cars still going right and left, these will stop. Add these to the count too.

Code Implementation

def count_collisions(directions):
    number_of_cars = len(directions)
    collisions = 0
    left_index = 0

    while left_index < number_of_cars and directions[left_index] == 'L':
        left_index += 1

    right_index = number_of_cars - 1

    while right_index >= 0 and directions[right_index] == 'R':
        right_index -= 1

    # Eliminate cars that will not collide
    directions = directions[left_index:right_index+1]
    number_of_cars = len(directions)

    for direction in directions:
        if direction != 'S':
            # Any moving car will collide and stop
            collisions += 1

    return collisions

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the road (represented as a string or array) from the beginning and then from the end, each time stopping after the first collision point. This involves traversing the input of size n at most twice. Therefore, the time complexity is determined by a constant number of linear traversals, resulting in O(n) time complexity. The operations performed within the loops are constant-time operations.

Space Complexity

O(1) – The algorithm iterates through the input string 'road' without using any auxiliary data structures that scale with the input size N (length of the road). It uses a few variables to keep track of collision counts and the current state (direction), but the number of these variables remains constant regardless of N. Therefore, the space complexity is O(1) as the extra space used does not depend on the input size.

Edge Cases

Case	How to Handle
Null or empty directions string	Return 0, as there are no cars and thus no collisions.
Directions string with a single character	Return 0, as a single car cannot collide with anything.
Directions string with only 'S' characters	Return 0, since stationary cars cannot collide with each other.
Directions string with only 'L' characters	Return 0, all cars are moving left, no collisions are possible in an open road setting.
Directions string with only 'R' characters	Return 0, all cars are moving right, no collisions are possible in an open road setting.
Very long directions string to test for efficiency	Iterate through the string once, ensuring O(n) time complexity to avoid timeouts.
A sequence of 'R' followed by 'L'	Increment collision count by 2, as both cars will collide and become stationary.
A sequence of 'R' followed by 'S' followed by 'L'	Increment collision count by 2, the 'R' will collide with 'S', and the 'L' will collide with 'S'.

Null or empty directions string

How to Handle:

Return 0, as there are no cars and thus no collisions.

Directions string with a single character

How to Handle:

Return 0, as a single car cannot collide with anything.

Directions string with only 'S' characters

How to Handle:

Return 0, since stationary cars cannot collide with each other.

Directions string with only 'L' characters

How to Handle:

Return 0, all cars are moving left, no collisions are possible in an open road setting.

Directions string with only 'R' characters

How to Handle:

Return 0, all cars are moving right, no collisions are possible in an open road setting.

Very long directions string to test for efficiency

How to Handle:

Iterate through the string once, ensuring O(n) time complexity to avoid timeouts.

A sequence of 'R' followed by 'L'

How to Handle:

Increment collision count by 2, as both cars will collide and become stationary.

A sequence of 'R' followed by 'S' followed by 'L'

How to Handle:

Increment collision count by 2, the 'R' will collide with 'S', and the 'L' will collide with 'S'.