Count Collisions on a Road
Count Collisions on a Road is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (trim the escaping cars), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from simulation (left to right with pending right-movers) up.
Problem
n cars stand at distinct points along an infinite straight road, numbered 0 to n - 1 from left to right. You are given a string directions where directions[i] is 'L' (car i drives left), 'R' (it drives right) or 'S' (it stays put). All moving cars have the same speed.
Collisions are scored like this: two cars driving towards each other add 2; a moving car hitting a stationary car adds 1. After any collision the cars involved stop where they are and never move again. Cars only pass each other by colliding.
Return the total number of collisions that will happen.
Examples
Example 1
- Input
directions = "RSLRL"- Output
4- Why
- Car 0 hits the parked car 1 (+1) and car 2 hits it from the other side (+1). Cars 3 and 4 meet head-on (+2). Total 4.
Example 2
- Input
directions = "LLSRR"- Output
0- Why
- The two left cars drive away to the left and the two right cars drive away to the right; nobody touches the parked car.
Example 3
- Input
directions = "RRRL"- Output
4- Why
- Cars 2 and 3 meet head-on (+2) and stop. Car 1 then runs into that pile (+1), and car 0 runs into it as well (+1).
Constraints
1 <= directions.length <= 10^5directions[i]is'L','R'or'S'
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Simulation (left to right with pending right-movers) | O(n) | O(1) |
| Optimal (trim the escaping cars) | O(n) | O(1) |
1Simulation (left to right with pending right-movers)
O(n)One pass over the string with O(1) work per car.O(1)A counter and a flag.Scan the road from left to right. Keep the number of 'R' cars that are still moving and waiting to hit something, and whether there is already a stopped car (or pile) to their left. An 'S' stops all pending 'R' cars (+1 each). An 'L' meeting pending 'R' cars causes a head-on hit (+2) and the other pending cars pile into it (+1 each); an 'L' with no pending 'R' crashes into a stopped car if one exists (+1), otherwise it escapes.
- collisions = 0, pendingRight = 0, stopped = false.
- 'R': pendingRight++.
- 'S': collisions += pendingRight, pendingRight = 0, stopped = true.
- 'L': if pendingRight > 0, collisions += 2 + (pendingRight - 1), pendingRight = 0, stopped = true; else if stopped, collisions += 1.
- Right-movers still pending at the end escape. Return collisions.
class Solution {
public int countCollisions(String directions) {
int collisions = 0, pendingRight = 0;
boolean stopped = false;
for (char c : directions.toCharArray()) {
if (c == 'R') {
pendingRight++;
} else if (c == 'S') {
collisions += pendingRight;
pendingRight = 0;
stopped = true;
} else if (pendingRight > 0) {
collisions += 2 + (pendingRight - 1);
pendingRight = 0;
stopped = true;
} else if (stopped) {
collisions += 1;
}
}
return collisions;
}
}class Solution:
def countCollisions(self, directions: str) -> int:
collisions = pending_right = 0
stopped = False
for c in directions:
if c == 'R':
pending_right += 1
elif c == 'S':
collisions += pending_right
pending_right = 0
stopped = True
elif pending_right > 0:
collisions += 2 + (pending_right - 1)
pending_right = 0
stopped = True
elif stopped:
collisions += 1
return collisionsclass Solution {
public:
int countCollisions(string directions) {
int collisions = 0, pendingRight = 0;
bool stopped = false;
for (char c : directions) {
if (c == 'R') {
pendingRight++;
} else if (c == 'S') {
collisions += pendingRight;
pendingRight = 0;
stopped = true;
} else if (pendingRight > 0) {
collisions += 2 + (pendingRight - 1);
pendingRight = 0;
stopped = true;
} else if (stopped) {
collisions += 1;
}
}
return collisions;
}
};function countCollisions(directions) {
let collisions = 0, pendingRight = 0, stopped = false;
for (const c of directions) {
if (c === 'R') {
pendingRight++;
} else if (c === 'S') {
collisions += pendingRight;
pendingRight = 0;
stopped = true;
} else if (pendingRight > 0) {
collisions += 2 + (pendingRight - 1);
pendingRight = 0;
stopped = true;
} else if (stopped) {
collisions += 1;
}
}
return collisions;
}2Optimal (trim the escaping cars)
O(n)Each character is looked at a constant number of times.O(1)Two indices and a counter.Every collision is worth exactly the number of moving cars it stops (2 for a head-on hit, 1 for hitting a stopped car), so the answer is the number of moving cars that eventually stop. The only cars that never stop are the run of 'L' cars at the left end and the run of 'R' cars at the right end. Skip those two runs and count every non-'S' car in between.
- l = 0; while l < n and directions[l] == 'L', l++.
- r = n - 1; while r >= 0 and directions[r] == 'R', r--.
- Count the characters in [l, r] that are not 'S'.
- Return that count.
class Solution {
public int countCollisions(String directions) {
int n = directions.length(), l = 0, r = n - 1;
while (l < n && directions.charAt(l) == 'L') l++;
while (r >= 0 && directions.charAt(r) == 'R') r--;
int count = 0;
for (int i = l; i <= r; i++) {
if (directions.charAt(i) != 'S') count++;
}
return count;
}
}class Solution:
def countCollisions(self, directions: str) -> int:
n = len(directions)
l, r = 0, n - 1
while l < n and directions[l] == 'L':
l += 1
while r >= 0 and directions[r] == 'R':
r -= 1
return sum(1 for i in range(l, r + 1) if directions[i] != 'S')class Solution {
public:
int countCollisions(string directions) {
int n = directions.size(), l = 0, r = n - 1;
while (l < n && directions[l] == 'L') l++;
while (r >= 0 && directions[r] == 'R') r--;
int count = 0;
for (int i = l; i <= r; i++) {
if (directions[i] != 'S') count++;
}
return count;
}
};function countCollisions(directions) {
const n = directions.length;
let l = 0, r = n - 1;
while (l < n && directions[l] === 'L') l++;
while (r >= 0 && directions[r] === 'R') r--;
let count = 0;
for (let i = l; i <= r; i++) {
if (directions[i] !== 'S') count++;
}
return count;
}Edge cases to test
- Only left-moving cars at the start, which escape
- Only right-moving cars at the end, which escape
- No stationary car but a head-on meeting
- All cars stationary (answer 0)
- A single car
Hints
Hint 1
Each collision stops the cars involved. Count, for every car, whether it will ever be stopped.
Hint 2
A head-on hit adds 2 and a moving car hitting a stopped one adds 1: so the total is just the number of moving cars that end up stopped.
Hint 3
Which moving cars never stop? Only the 'L' cars at the very start and the 'R' cars at the very end.
FAQ
What is the best time complexity for Count Collisions on a Road?
Optimal (trim the escaping cars) runs in O(n) time and O(1) extra space. Each character is looked at a constant number of times.
Which pattern does Count Collisions on a Road use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Count Collisions on a Road?
Yes. Simulation (left to right with pending right-movers) takes O(n) time and O(1) space. Scan the road from left to right.
Which edge cases should I test for Count Collisions on a Road?
Only left-moving cars at the start, which escape; Only right-moving cars at the end, which escape; No stationary car but a head-on meeting; All cars stationary (answer 0); A single car.