{x}
blog image

Count Collisions on a Road

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 ith 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 <= 105
  • directions[i] is either 'L', 'R', or 'S'.

Solution Explanation

This problem can be efficiently solved by focusing on the cars that will actually collide. Cars moving in the same direction will not collide. Cars moving towards the left ('L') from the left end and cars moving towards the right ('R') from the right end will never collide with any other car. Therefore, we can eliminate these cars from consideration.

The collisions will only occur within the remaining substring of cars. Every car in this substring that is not stationary ('S') will be involved in at least one collision.

Algorithm

  1. Trim the ends: Remove all leading 'L's and trailing 'R's from the directions string. This leaves us with a substring where collisions are possible.

  2. Count non-stationary cars: Count the number of cars in the remaining substring that are not 'S'. These are the cars involved in collisions.

  3. Return the count: The count of non-stationary cars in the trimmed substring is the total number of collisions.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the directions string. Trimming the string and counting non-stationary cars take linear time.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space, regardless of the input size. The trimming operation in some languages (like Python) might create new strings, but the overall space usage is still considered constant in terms of input size.

Code Implementation with Detailed Explanations

Python:

class Solution:
    def countCollisions(self, directions: str) -> int:
        # Remove leading 'L's and trailing 'R's
        trimmed_directions = directions.lstrip('L').rstrip('R')
 
        # Count non-stationary cars ('L' or 'R')
        collisions = len(trimmed_directions) - trimmed_directions.count('S')
 
        return collisions

The Python solution leverages the built-in string methods lstrip() and rstrip() for efficient trimming. The count() method easily determines the number of 'S' characters.

Java:

class Solution {
    public int countCollisions(String directions) {
        char[] ds = directions.toCharArray();
        int n = ds.length;
        int l = 0;
        int r = n - 1;
 
        // Find the start index of the relevant substring (after leading 'L's)
        while (l < n && ds[l] == 'L') {
            l++;
        }
        
        // Find the end index of the relevant substring (before trailing 'R's)
        while (r >= 0 && ds[r] == 'R') {
            r--;
        }
 
        int ans = 0;
        // Count non-stationary cars in the relevant substring
        for (int i = l; i <= r; ++i) {
            if (ds[i] != 'S') {
                ans++;
            }
        }
        return ans;
    }
}

The Java solution uses a two-pointer approach to find the start and end indices of the relevant substring, iterating through it to count the collisions.

C++, Go, TypeScript: The other languages follow a similar approach, adapting the string manipulation and counting techniques specific to each language. The core logic remains the same, offering an efficient solution to the problem.