Watch 10 video solutions for Count Collisions on a Road, a medium level problem involving String, Stack, Simulation. This walkthrough by codestorywithMIK has 6,658 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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'.Problem Overview: You are given a string where each character represents a car moving on a road: L (left), R (right), or S (stationary). When cars moving in opposite directions meet, they collide and become stationary. The task is to count the total number of collisions that occur after all movements stabilize.
Approach 1: Two-Pointer Simulation (O(n) time, O(1) space)
This method simulates the road state while scanning the string once. Track cars moving to the right and resolve collisions when encountering L or S. If a left-moving car meets previously seen right-moving cars, multiple collisions occur: the first collision converts both to stationary and the remaining right-moving cars collide with the stationary car. Two pointers or counters help track pending R cars and update the collision count as you iterate. This approach models the physical process explicitly, which makes the logic intuitive during interviews and aligns well with simulation style problems.
Approach 2: Direct Collision Counting (O(n) time, O(1) space)
The key observation: cars that move left at the very beginning and cars that move right at the very end never collide with anything. After trimming those segments, every remaining moving car must eventually collide. Remove leading L and trailing R using two pointers. In the remaining substring, every L and R contributes exactly one collision because each moving car eventually crashes into another car or a stationary one. The answer becomes the count of all non-stationary cars in this trimmed range. This turns the problem into simple counting on a string, avoiding explicit simulation.
Recommended for interviews: The direct collision counting approach is the optimal and most elegant solution. Interviewers expect you to recognize that edge cars moving outward never collide and that all remaining moving cars must eventually stop due to collisions. Explaining the simulation first demonstrates understanding of the mechanics, while the optimized counting insight shows strong pattern recognition. Problems like this often appear in discussions involving stack-like collision behavior or directional simulations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Simulation | O(n) | O(1) | When you want to explicitly model collisions and explain the process step by step during interviews. |
| Direct Collision Counting | O(n) | O(1) | Best for optimized solutions once you recognize that edge cars moving outward never collide. |