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:
2.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 <= 105directions[i] is either 'L', 'R', or 'S'.This approach simulates the process of collisions using a two-pointer technique, starting from each end of the string towards the center.
We count potential collisions by looking for patterns where a right-moving car ('R') encounters a left-moving ('L') or stationary ('S') car.
We use two pointers to trim non-colliding 'L' cars at the beginning and non-colliding 'R' cars at the end. The remaining cars will result in collisions unless they are stationary ('S').
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) - We traverse the string at most twice.
Space Complexity: O(1) - Constant space is used irrespective of input size.
This approach directly counts collisions as cars are processed in a single pass. It increments collision counts for situations where left-moving cars hit right-moving or stationary cars.
The function counts 'R' cars until a 'L' or 'S' is encountered, adding the number of 'R' cars counted to the total collisions for each 'L' or 'S'.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Two-Pointer Simulation | Time Complexity: O(n) - We traverse the string at most twice. |
| Direct Collision Counting | Time Complexity: O(n) |
How to EASILY solve LeetCode problems • NeetCode • 427,724 views views
Watch 9 more video solutions →Practice Count Collisions on a Road with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor