Count Collisions on a Road solution and explanation
Google
9 more videos on this problem
Count Collisions on a Road | Asked in Online Assessment | Dry Run | Leetcode 2211 | codestorywithMIKcodestorywithMIK · 17:40 · 7K views
Count Collisions on a Road | Leetcode 2211 | Arrays | Contest 285 | 🔥🔥Coding Decoded · 11:14 · 1K views
Count Collisions on a Road | LeetCode 2211 | Complete Intuition ExplainedSanyam IIT Guwahati · 16:16 · 759 views
Leetcode Weekly 285 | 2211. Count Collisions on a RoadcodingMohan · 8:32 · 693 views
2211. Count Collisions on a Road | Leetcode Daily - PythonLeetcode Daily · 10:05 · 637 views
2211. Count Collisions on a Road (Leetcode Medium)Programming Live with Larry · 6:53 · 609 views
Count Collisions on a Road | Leetcode 2211 | DSA | Hindi | Code With DeepakCode with Deepak · 6:57 · 340 views
Count Collisions on a Road | LeetCode 2211 - Python (2 Solutions)impoldev · 15:42 · 235 views
question no.-2211|| Count Collision On a Road || Leetcode Daily ProblemLeetCodewithManish · 4:02 · 217 views
2211 Count Collisions on a Road LeetCodeR Sai Siddhu · 9:24 · 177 views
The problem
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'.
Approach overview
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 1: Two-Pointer Simulation
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.
def countCollisions(directions: str) -> int:
left, right = 0, len(directions) - 1
collisions = 0
while left < right and directions[left] == 'L':
left += 1
while right > left and directions[right] == 'R':
right -= 1
for i in range(left, right + 1):
if directions[i] != 'S':
collisions += 1
return collisions
print(countCollisions('RLRSLL'))public class CountCollisions {
public static int countCollisions(String directions) {
int left = 0, right = directions.length() - 1;
int collisions = 0;
while (left < right && directions.charAt(left) == 'L') left++;
while (right > left && directions.charAt(right) == 'R') right--;
for (int i = left; i <= right; i++) {
if (directions.charAt(i) != 'S') collisions++;
}
return collisions;
}
public static void main(String[] args) {
String directions = "RLRSLL";
System.out.println(countCollisions(directions));
}
}#include <iostream>
#include <string>
using namespace std;
int countCollisions(string directions) {
int left = 0, right = directions.size() - 1;
int collisions = 0;
while (left < right && directions[left] == 'L') left++;
while (right > left && directions[right] == 'R') right--;
for (int i = left; i <= right; i++) {
if (directions[i] != 'S') collisions++;
}
return collisions;
}
int main() {
string directions = "RLRSLL";
cout << countCollisions(directions) << endl;
return 0;
}function countCollisions(directions) {
let left = 0, right = directions.length - 1;
let collisions = 0;
while (left < right && directions[left] === 'L') left++;
while (right > left && directions[right] === 'R') right--;
for (let i = left; i <= right; i++) {
if (directions[i] !== 'S') collisions++;
}
return collisions;
}
console.log(countCollisions('RLRSLL'));#include <stdio.h>
#include <string.h>
int countCollisions(char *directions) {
int left = 0, right = strlen(directions) - 1;
int collisions = 0;
while (left < right && directions[left] == 'L') left++;
while (right > left && directions[right] == 'R') right--;
for (int i = left; i <= right; i++) {
if (directions[i] != 'S') collisions++;
}
return collisions;
}
int main() {
char directions[] = "RLRSLL";
printf("%d\n", countCollisions(directions));
return 0;
}using System;
public class CountCollisions {
public static int CountCollisions(string directions) {
int left = 0, right = directions.Length - 1;
int collisions = 0;
while (left < right && directions[left] == 'L') left++;
while (right > left && directions[right] == 'R') right--;
for (int i = left; i <= right; i++) {
if (directions[i] != 'S') collisions++;
}
return collisions;
}
public static void Main(string[] args) {
string directions = "RLRSLL";
Console.WriteLine(CountCollisions(directions));
}
}Counts the number of non-stationary cars in the central segment of interest, where potential collisions are unavoidable if they exist in the string post trimming.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Direct Collision Counting
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.
def countCollisions(directions: str) -> int:
collisions = 0
right_moving = 0
for direction in directions:
if direction == 'R':
right_moving += 1
elif direction == 'L' and right_moving > 0:
collisions += right_moving + 1
right_moving = 0
elif direction == 'S':
collisions += right_moving
right_moving = 0
return collisions
print(countCollisions('RLRSLL'))public class CountCollisions {
public static int countCollisions(String directions) {
int collisions = 0, rightMoving = 0;
for (char dir : directions.toCharArray()) {
if (dir == 'R') {
rightMoving++;
} else if (dir == 'L' && rightMoving > 0) {
collisions += rightMoving + 1;
rightMoving = 0;
} else if (dir == 'S') {
collisions += rightMoving;
rightMoving = 0;
}
}
return collisions;
}
public static void main(String[] args) {
System.out.println(countCollisions("RLRSLL"));
}
}#include <iostream>
#include <string>
using namespace std;
int countCollisions(string directions) {
int collisions = 0;
int rightMoving = 0;
for (char dir : directions) {
if (dir == 'R') {
rightMoving++;
} else if (dir == 'L' && rightMoving > 0) {
collisions += rightMoving + 1;
rightMoving = 0;
} else if (dir == 'S') {
collisions += rightMoving;
rightMoving = 0;
}
}
return collisions;
}
int main() {
string directions = "RLRSLL";
cout << countCollisions(directions) << endl;
return 0;
}function countCollisions(directions) {
let collisions = 0;
let rightMoving = 0;
for (let direction of directions) {
if (direction === 'R') {
rightMoving++;
} else if (direction === 'L' && rightMoving > 0) {
collisions += rightMoving + 1;
rightMoving = 0;
} else if (direction === 'S') {
collisions += rightMoving;
rightMoving = 0;
}
}
return collisions;
}
console.log(countCollisions('RLRSLL'));#include <stdio.h>
#include <string.h>
int countCollisions(char *directions) {
int collisions = 0;
int rightMoving = 0;
for (int i = 0; i < strlen(directions); i++) {
if (directions[i] == 'R') {
rightMoving++;
} else if (directions[i] == 'L' && rightMoving > 0) {
collisions += rightMoving + 1;
rightMoving = 0;
} else if (directions[i] == 'S') {
collisions += rightMoving;
rightMoving = 0;
}
}
return collisions;
}
int main() {
char directions[] = "RLRSLL";
printf("%d\n", countCollisions(directions));
return 0;
}using System;
public class CountCollisions {
public static int CountCollisions(string directions) {
int collisions = 0, rightMoving = 0;
foreach (char dir in directions) {
if (dir == 'R') {
rightMoving++;
} else if (dir == 'L' && rightMoving > 0) {
collisions += rightMoving + 1;
rightMoving = 0;
} else if (dir == 'S') {
collisions += rightMoving;
rightMoving = 0;
}
}
return collisions;
}
public static void Main(string[] args) {
Console.WriteLine(CountCollisions("RLRSLL"));
}
}This function accumulates the number of potential collisions by keeping track of right-moving cars and responding when they meet opposing cars.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Brain Teaser
According to the problem description, when two cars moving in opposite directions collide, the collision count increases by 2, meaning both cars stop, and the answer increases by 2. When a moving car collides with a stationary car, the collision count increases by 1, meaning one car stops, and the answer increases by 1.
Obviously, the prefix L and the suffix R will not collide, so we only need to count the number of characters in the middle that are not S.
The time complexity is O(n), and the space complexity is O(n) or O(1). Here, n is the length of the string directions.
function countCollisions(directions: string): number {
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;
}func countCollisions(directions string) int {
s := strings.TrimRight(strings.TrimLeft(directions, "L"), "R")
return len(s) - strings.Count(s, "S")
}impl Solution {
pub fn count_collisions(directions: String) -> i32 {
let s = directions.trim_start_matches('L').trim_end_matches('R');
(s.len() as i32) - (s.matches('S').count() as i32)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Simulation | Time Complexity: O(n) |
| Direct Collision Counting | Time Complexity: O(n) |
| Brain Teaser | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Count Collisions on a Road easy or hard?
The problem is rated Medium because the naive simulation seems complex at first. The difficulty lies in recognizing the observation that cars moving outward never collide and that remaining moving cars must eventually crash, which simplifies the solution to linear counting.
How to solve Count Collisions on a Road in O(n)?
Scan the string with two pointers. Skip all leading 'L' cars and trailing 'R' cars since they move away from traffic. In the remaining section, count every 'L' and 'R' because each moving car must eventually collide and become stationary. This produces the collision count in a single pass.
What is the best approach for Count Collisions on a Road?
The most efficient approach is direct collision counting. Trim all leading 'L' cars and trailing 'R' cars because they never collide. In the remaining substring, every 'L' or 'R' eventually collides, so counting those characters gives the total collisions. This runs in O(n) time and O(1) space.
What data structure is used in Count Collisions on a Road?
Most optimized solutions only use pointers and counters while scanning the string. Some explanations model the process with a stack-like idea where right-moving cars accumulate and collide with incoming cars, but the final optimized implementation does not require an explicit stack.
What is the time complexity of Count Collisions on a Road?
Both common solutions run in O(n) time where n is the length of the directions string. Each character is processed at most once. The optimized counting approach also uses O(1) additional space since it only maintains counters and pointers.
Count Collisions on a Road Python or Java solution approach?
The typical Python or Java solution trims leading 'L' and trailing 'R' using two pointers, then iterates through the remaining substring counting all 'L' and 'R'. Each of those represents one collision. The algorithm runs in O(n) time with constant extra space.
Is Count Collisions on a Road asked at Google, Amazon, or Meta?
This style of problem appears in interviews at large tech companies including Amazon and Google, especially in rounds focused on string processing and simulation. The question tests pattern recognition, edge-case reasoning, and the ability to simplify a simulation into counting logic.