Count Collisions on a Road
MedPrompt
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 <= 105directions[i]is either'L','R', or'S'.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the collision process. It repeatedly scans the road and resolves any immediate collisions between adjacent cars. The simulation continues in passes until no more collisions can occur in a full pass, at which point the road is stable.
Algorithm
- Convert the input string
directionsto a character arraycarsfor easy modification. - Initialize
totalCollisions = 0. - Use a
whileloop that continues as long as collisions are detected in a pass. A boolean flag,changed, can track this. - Inside the loop, iterate through the
carsarray to find and resolve collisions:- Scan for adjacent
'R'and'L'cars (RL). For each pair found, add 2 tototalCollisionsand change both cars to'S'. Setchangedtotrue. - Scan for adjacent
'R'and'S'cars (RS). For each, add 1 tototalCollisions, change'R'to'S', and setchangedtotrue. - Scan for adjacent
'S'and'L'cars (SL). For each, add 1 tototalCollisions, change'L'to'S', and setchangedtotrue.
- Scan for adjacent
- The loop terminates when a full pass over the cars results in no changes (
changedremainsfalse). - Return
totalCollisions.
Walkthrough
The core idea is to mimic the physical interactions on the road. We treat the string of directions as the state of the road and update it iteratively. In each step of the simulation, we look for pairs of cars that are about to collide, such as an 'R' car followed by an 'L' car, or a moving car next to a stationary one. When a collision is found, we update the total collision count and change the state of the involved cars to 'S' (stationary). This process is repeated until a complete scan of the road reveals no new collisions. While intuitive, this method is slow because collisions might propagate one by one, requiring many passes over the entire string.
class Solution { public int countCollisions(String directions) { char[] cars = directions.toCharArray(); int n = cars.length; int collisions = 0; boolean changedInPass = true; // Repeat passes as long as collisions are happening while (changedInPass) { changedInPass = false; // Check for R-L head-on collisions first for (int i = 0; i < n - 1; i++) { if (cars[i] == 'R' && cars[i+1] == 'L') { collisions += 2; cars[i] = 'S'; cars[i+1] = 'S'; changedInPass = true; } } // Check for moving cars hitting stationary cars for (int i = 0; i < n - 1; i++) { if (cars[i] == 'R' && cars[i+1] == 'S') { collisions += 1; cars[i] = 'S'; changedInPass = true; } } // Check from right to left for 'L' cars hitting 'S' cars for (int i = n - 1; i > 0; i--) { if (cars[i] == 'L' && cars[i-1] == 'S') { collisions += 1; cars[i] = 'S'; changedInPass = true; } } } return collisions; }}Complexity
Time
O(N^2). In the worst case, like `"RR...RL...LL"`, collisions propagate from the center outwards one car at a time. This could take up to O(N) passes, and each pass takes O(N) time.
Space
O(N), to store the character array representing the road state. If the input string is mutable, it could be O(1). In Java, strings are immutable, so a char array is needed for modifications.
Trade-offs
Pros
It's a very direct and intuitive translation of the problem description.
Cons
Inefficient, with a quadratic time complexity in the worst-case scenario.
The implementation can be tricky. The order of checking and updating collisions matters and can lead to subtle bugs if not handled carefully.
A more optimized approach uses a stack to process the cars in a single pass from left to right. The stack keeps track of cars that are moving right ('R') and haven't collided yet. When we encounter a stationary ('S') or left-moving ('L') car, we can resolve any pending collisions with the 'R' cars on the stack and update the collision count accordingly.
Algorithm
- Initialize
totalCollisions = 0and an emptyStack<Character>. - Iterate through each car's direction
cfrom left to right. - If
cis'R', push it onto the stack. These are potential future collisions. - If
cis'S':- A stationary car acts as a wall. Any
'R'cars on the stack will collide with it. - Pop all
'R'cars from the stack, incrementingtotalCollisionsfor each one. - Push
'S'onto the stack to represent the (now potentially larger) stationary block.
- A stationary car acts as a wall. Any
- If
cis'L':- Check the top of the stack.
- If it's
'R', a head-on collision occurs. Add 2 tototalCollisions, pop the'R'. Then, pop any other'R'cars, adding 1 for each (as they pile up). Finally, push'S'to mark the collision spot. - If it's
'S', the'L'car hits the stationary block. Add 1 tototalCollisions. - If the stack is empty or the top is
'L', this car doesn't collide with anything to its left, so we ignore it.
- Return
totalCollisionsafter iterating through all cars.
Walkthrough
This method avoids the repeated scans of the simulation approach. As we iterate through the cars, the stack maintains a record of cars whose final fate is not yet determined (primarily 'R' cars). When an 'L' or 'S' car is encountered, it provides the 'obstacle' that resolves the movement of the 'R' cars waiting on the stack.
- 'R' car: Pushed onto the stack, as it might collide with something to its right.
- 'L' car: If the stack has 'R' cars, they collide. A head-on
R-Lcollision adds 2 to the count, and any subsequent 'R' cars on the stack pile into the wreckage, each adding 1. If the stack has an 'S', the 'L' car hits it, adding 1. Otherwise, the 'L' car moves away freely. - 'S' car: Acts as a wall, causing all 'R' cars on the stack to collide and pile up, each adding 1 to the count.
This correctly calculates all collisions in one pass.
import java.util.Stack; class Solution { public int countCollisions(String directions) { Stack<Character> stack = new Stack<>(); int collisions = 0; for (char dir : directions.toCharArray()) { if (dir == 'R') { stack.push('R'); } else { if (!stack.isEmpty()) { if (dir == 'L') { if (stack.peek() == 'R') { collisions += 2; // R-L collision stack.pop(); // Other R's pile up while (!stack.isEmpty() && stack.peek() == 'R') { collisions += 1; stack.pop(); } stack.push('S'); // Collision creates a stationary block } else if (stack.peek() == 'S') { collisions += 1; // L hits a stationary block } } else { // dir == 'S' // All R's on stack will hit this S while (!stack.isEmpty() && stack.peek() == 'R') { collisions += 1; stack.pop(); } stack.push('S'); } } } } return collisions; }}Complexity
Time
O(N). We iterate through the input string once. Each car is pushed onto and popped from the stack at most once, leading to linear time performance.
Space
O(N). In the worst case, for a string like `"RRR..."`, the stack's size can grow to be equal to the length of the string.
Trade-offs
Pros
Efficient O(N) time complexity, as it processes each car only once.
Handles complex chain reactions correctly without repeated full scans of the road.
Cons
Requires extra space for the stack, which can be up to O(N) in the worst case.
This is the most efficient approach, achieving optimal time and space complexity. It's based on a key insight: any cars moving left ('L') at the absolute beginning of the road and any cars moving right ('R') at the absolute end will never collide with anything. Collisions are confined to the cars between these two groups. By identifying this 'active' segment of the road, we can simply count all the moving cars within it, as each one is guaranteed to be involved in exactly one collision event.
Algorithm
- Find the index of the first car that is not moving left. Initialize a pointer
left = 0and increment it whiledirections.charAt(left) == 'L'. - Find the index of the last car that is not moving right. Initialize a pointer
right = n - 1and decrement it whiledirections.charAt(right) == 'R'. - These
leftandrightpointers define the 'active zone' where all collisions will occur. - If
left >= right, it means no cars are in the active zone, so there are no collisions. Return 0. - Otherwise, iterate from
lefttoright. - Count every car in this range that is not stationary (i.e., its direction is
'L'or'R'). This count is the total number of collisions. - Return the final count.
Walkthrough
The logic is to first eliminate the cars that cannot possibly collide. A car at index i moving left ('L') can only collide with cars at indices less than i. If all cars to its left are also moving left, it will never collide. Thus, any prefix of 'L' cars can be ignored. Similarly, a car at index j moving right ('R') can only collide with cars at indices greater than j. If all cars to its right are also moving right, it will never collide. Thus, any suffix of 'R' cars can be ignored.
After trimming these non-colliding cars from the left and right ends, we are left with a central segment. Within this segment, every single moving car (either 'L' or 'R') is guaranteed to collide. Why? An 'R' car in this segment must eventually encounter an 'S' or an 'L' to its right (otherwise it would have been part of the trimmed suffix). An 'L' car must eventually encounter an 'S' or an 'R' to its left (otherwise it would have been part of the trimmed prefix).
Therefore, the total number of collisions is simply the number of moving cars in this active segment.
class Solution { public int countCollisions(String directions) { int n = directions.length(); int left = 0; // Skip all 'L' cars from the left as they will never collide while (left < n && directions.charAt(left) == 'L') { left++; } int right = n - 1; // Skip all 'R' cars from the right as they will never collide while (right >= 0 && directions.charAt(right) == 'R') { right--; } int collisionCount = 0; // Iterate through the active zone for (int i = left; i <= right; i++) { // Every moving car in this zone will cause a collision if (directions.charAt(i) != 'S') { collisionCount++; } } return collisionCount; }}Complexity
Time
O(N). The algorithm involves a few passes over the string (one to find the left boundary, one for the right, and one to count), which sums to a linear time complexity.
Space
O(1). We only use a few integer variables for the pointers and the collision count, regardless of the input size.
Trade-offs
Pros
Optimal O(N) time complexity.
Optimal O(1) space complexity, as it only uses a few variables.
Very simple and clean implementation.
Cons
The underlying logic might be less immediately obvious than a direct simulation.
Solutions
Solution
class Solution {public int countCollisions(String directions) { char[] ds = directions.toCharArray(); int n = ds.length; int l = 0; int r = n - 1; while (l < n && ds[l] == 'L') { ++l; } while (r >= 0 && ds[r] == 'R') { --r; } int ans = 0; for (int i = l; i <= r; ++i) { if (ds[i] != 'S') { ++ans; } } return ans; }}/** * @param {string} directions * @return {number} */ var countCollisions = function (directions) { const n = directions.length; let [l, r] = [0, n - 1]; while (l < n && directions[l] == " L ") { ++l; } while (r >= 0 && directions[r] == " R ") { --r; } let ans = r - l + 1; for (let i = l; i <= r; ++i) { if (directions[i] === " S ") { --ans; } } return ans; };class Solution {public: int countCollisions(string directions) { int l = 0, r = directions.size() - 1, count = 0; while (l <= r && directions[l] == 'L') { l++; } while (l <= r && directions[r] == 'R') { r--; } for (int i = l; i <= r; i++) { count += directions[i] != 'S'; } return count; }};class Solution: def countCollisions(self, directions: str) -> int: d = directions . lstrip('L'). rstrip('R') return len(d) - d . count('S')Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.