LeetCode Problem 2211

Difficulty: 🟡 Medium
Topics: String, Stack, Simulation

Solution

LeetCode 2211 - Count Collisions on a Road

Problem Understanding

The problem describes a one dimensional road containing cars positioned from left to right. Every car has one of three possible states:

• 'L', meaning the car moves left
• 'R', meaning the car moves right
• 'S', meaning the car stays stationary

All moving cars travel at the same speed. Whenever cars meet, collisions occur according to specific rules:

• A left moving car and a right moving car colliding contributes 2 collisions because both moving cars stop.
• A moving car colliding with a stationary car contributes 1 collision because only one moving car stops.

After a collision, every involved car becomes stationary forever.

The goal is to compute the total number of collisions that eventually happen after all motion resolves.

The input is a string directions, where each character represents the direction or state of one car. The output is a single integer representing the total number of collisions.

The constraints are important:

• The length can be as large as 10^5
• This rules out expensive simulation approaches that repeatedly update positions over time
• We need a linear or near linear solution

A key observation is that cars only move along a line, and every collision eventually creates stationary cars that can trigger additional collisions.

Several edge cases are important:

• Cars moving left at the very beginning can leave the road without colliding
• Cars moving right at the very end can also leave without colliding
• Consecutive stationary cars should not increase collisions
• Chains of right moving cars can all eventually collide with a stationary obstacle
• Multiple collisions can cascade after an initial collision creates a stationary car

Approaches

Brute Force Approach

A direct simulation approach would model the movement of every car over time. At each time step, we would update positions, detect collisions, convert collided cars into stationary cars, and continue until no movement remains.

This approach is correct because it literally follows the problem statement. However, it is far too slow for the given constraints. Since cars may require many updates before collisions happen, repeatedly simulating movement can become quadratic or worse.

For example, with 10^5 cars, repeatedly scanning and updating positions would exceed time limits.

Optimal Approach

The key insight is that we do not actually need to simulate positions over time.

Cars only avoid collisions in two situations:

• Left moving cars at the far left escape the road
• Right moving cars at the far right escape the road

Every other moving car will eventually collide.

We can think about the final stable configuration instead of simulating motion.

If we remove:

• all leading 'L' cars
• all trailing 'R' cars

then every remaining moving car must collide at some point.

Inside this trimmed section:

• every 'L' contributes one collision
• every 'R' contributes one collision
• 'S' contributes none

Therefore, the answer becomes the number of non stationary cars inside the valid collision region.

This gives a very clean linear solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) or worse	O(n)	Simulates car movement step by step
Optimal	O(n)	O(1)	Trim escaping cars, count remaining moving cars

Algorithm Walkthrough

1. Start from the left side of the string and skip every leading 'L'.

These cars move left forever and never meet another car because there is nothing to their left. 2. Start from the right side of the string and skip every trailing 'R'.

These cars move right forever and never meet another car because there is nothing to their right. 3. After trimming both sides, every remaining moving car must eventually collide.

This happens because:

• A remaining 'R' will eventually hit a stationary car or a left moving car
• A remaining 'L' must eventually encounter something on its left

4. Iterate through the remaining substring.
5. Count every character that is not 'S'.

Each moving car contributes exactly one collision:

• 'R' eventually stops after colliding
• 'L' eventually stops after colliding

6. Return the total count.

Why it works

The crucial invariant is that only cars escaping off the road can avoid collisions. Leading left moving cars and trailing right moving cars are the only escaping cars. Every other moving car is trapped between other cars or stationary obstacles, so it must eventually collide exactly once before becoming stationary. Therefore, counting all non stationary cars in the trimmed region gives the exact number of collisions.

Python Solution

class Solution:
    def countCollisions(self, directions: str) -> int:
        n = len(directions)

        left = 0
        while left < n and directions[left] == 'L':
            left += 1

        right = n - 1
        while right >= 0 and directions[right] == 'R':
            right -= 1

        collisions = 0

        for i in range(left, right + 1):
            if directions[i] != 'S':
                collisions += 1

        return collisions

The implementation begins by finding the first car from the left that cannot freely escape. Every leading 'L' is skipped because those cars move away from the road without interacting.

Next, the code scans from the right side and skips all trailing 'R' cars for the same reason.

Once the valid collision region is identified, the algorithm simply counts every moving car inside that range. Any 'L' or 'R' within this region must eventually stop because of a collision, so each contributes exactly one to the final answer.

The solution uses only a few integer variables and scans the string at most once from each side, making it highly efficient.

Go Solution

func countCollisions(directions string) int {
	n := len(directions)

	left := 0
	for left < n && directions[left] == 'L' {
		left++
	}

	right := n - 1
	for right >= 0 && directions[right] == 'R' {
		right--
	}

	collisions := 0

	for i := left; i <= right; i++ {
		if directions[i] != 'S' {
			collisions++
		}
	}

	return collisions
}

The Go implementation follows exactly the same logic as the Python version. Since Go strings are byte indexed and the input only contains ASCII characters ('L', 'R', 'S'), direct indexing is safe and efficient.

No special handling for integer overflow is needed because the maximum number of collisions is at most 10^5, which easily fits inside Go's int type.

Worked Examples

Example 1

Input:

directions = "RLRSLL"

First, trim leading 'L' cars:

Index	Character	Action
0	R	Stop trimming

So left = 0.

Now trim trailing 'R' cars:

Index	Character	Action
5	L	Stop trimming

So right = 5.

Now examine indices [0, 5].

Index	Character	Collision Count
0	R	1
1	L	2
2	R	3
3	S	3
4	L	4
5	L	5

Final answer:

5

Example 2

Input:

directions = "LLRR"

Trim leading 'L' cars:

Index	Character	Action
0	L	Skip
1	L	Skip
2	R	Stop

So left = 2.

Trim trailing 'R' cars:

Index	Character	Action
3	R	Skip
2	R	Skip
1	L	Stop

So right = 1.

Now left > right, meaning there is no collision region.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is scanned at most once
Space	O(1)	Only a few integer variables are used

The algorithm performs three linear scans:

• one from the left
• one from the right
• one through the middle section

Even combined, this remains linear time complexity. No auxiliary data structures proportional to input size are required.

Test Cases

solution = Solution()

assert solution.countCollisions("RLRSLL") == 5  # Provided example with chain collisions
assert solution.countCollisions("LLRR") == 0  # Cars escape without collisions

assert solution.countCollisions("S") == 0  # Single stationary car
assert solution.countCollisions("L") == 0  # Single left-moving car escapes
assert solution.countCollisions("R") == 0  # Single right-moving car escapes

assert solution.countCollisions("RS") == 1  # Right-moving car hits stationary car
assert solution.countCollisions("SL") == 1  # Left-moving car hits stationary car
assert solution.countCollisions("RL") == 2  # Opposite directions collide

assert solution.countCollisions("RRRLLL") == 6  # All cars eventually collide
assert solution.countCollisions("SSSS") == 0  # All stationary cars

assert solution.countCollisions("LLLSRRR") == 0  # Escaping cars only
assert solution.countCollisions("RRSLL") == 4  # Multiple collisions after stationary formation

assert solution.countCollisions("LSR") == 0  # Outer cars escape
assert solution.countCollisions("RSRLRS") == 4  # Mixed interactions

assert solution.countCollisions("LRSLR") == 2  # Internal collision region

# Large repeated pattern
large_input = "L" * 1000 + "R" * 1000 + "S" + "L" * 1000 + "R" * 1000
assert solution.countCollisions(large_input) == 2001  # Stress test

Test	Why
"RLRSLL"	Verifies chain collision behavior
"LLRR"	Verifies escaping cars produce zero collisions
"S"	Smallest stationary case
"L"	Single escaping left car
"R"	Single escaping right car
"RS"	Right-moving car hitting stationary car
"SL"	Left-moving car hitting stationary car
"RL"	Opposite-direction collision
"RRRLLL"	Large central collision region
"SSSS"	No movement anywhere
"LLLSRRR"	All moving cars escape
"RRSLL"	Cascading stationary collisions
"LSR"	Trimmed edges leave no collisions
"RSRLRS"	Mixed states and interactions
Large repeated pattern	Stress test for performance and correctness

Edge Cases

Leading Left Moving Cars

A sequence like "LLLR" can easily confuse a naive simulation. The left moving cars never collide because there are no cars to their left. Only the final 'R' exists, and it also escapes right. The implementation handles this by trimming all leading 'L' cars before counting collisions.

Trailing Right Moving Cars

A sequence like "SRRR" contains right moving cars that leave the road forever. A naive counting approach might incorrectly assume they eventually collide. The algorithm correctly removes all trailing 'R' cars before processing the collision region.

Entire String Has No Collisions

Inputs like "LLRR" or "SSSS" are important because no collisions occur at all. After trimming escaping cars, the valid region becomes empty or contains only stationary cars. The implementation naturally returns 0 in these situations.

Chain Reactions After Initial Collision

Cases like "RRRL" are tricky because the first collision creates a stationary obstacle, causing additional collisions behind it. A naive implementation might only count the first impact. The optimal insight avoids simulation entirely by recognizing that every moving car trapped in the middle region eventually contributes exactly one collision.