Move from brute-force thinking to an efficient approach using stack strategy.
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 summary: 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
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Stack
"RLRSLL"
"LLRR"
asteroid-collision)car-fleet)last-moment-before-all-ants-fall-out-of-a-plank)car-fleet-ii)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2211: Count Collisions on a Road
class Solution {
public int countCollisions(String directions) {
char[] s = directions.toCharArray();
int n = s.length;
int l = 0, r = n - 1;
while (l < n && s[l] == 'L') {
++l;
}
while (r >= 0 && s[r] == 'R') {
--r;
}
int ans = r - l + 1;
for (int i = l; i <= r; ++i) {
ans -= s[i] == 'S' ? 1 : 0;
}
return ans;
}
}
// Accepted solution for LeetCode #2211: Count Collisions on a Road
func countCollisions(directions string) int {
s := strings.TrimRight(strings.TrimLeft(directions, "L"), "R")
return len(s) - strings.Count(s, "S")
}
# Accepted solution for LeetCode #2211: Count Collisions on a Road
class Solution:
def countCollisions(self, directions: str) -> int:
s = directions.lstrip("L").rstrip("R")
return len(s) - s.count("S")
// Accepted solution for LeetCode #2211: Count Collisions on a Road
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)
}
}
// Accepted solution for LeetCode #2211: Count Collisions on a Road
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;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.