Abstract / Summary

Count how many times cars collide on a one-lane road with specific movement rules.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 58% (200k+ submissions).

Typical patterns to solve this problem:

• Simulation
• Stack
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the collision-counting problem for a one-dimensional traffic simulation. A string directions encodes the motion of cars: 'L' moves left, 'R' moves right, and 'S' is stationary. When cars moving toward each other meet, a collision occurs. The algorithm first discards cars that can never be involved in a collision because they travel outward beyond the road limits, then counts the remaining cars that are guaranteed to collide. The final result is the total number of collisions.

Key Steps

Removing cars that are guaranteed to escape

Cars that start at the far left and move left ('L') will never meet another vehicle, because there is no car on their left side. Likewise, cars that start at the far right and move right ('R') will exit the road without interaction. The code eliminates these irrelevant cars with two string-trimming operations:

mid = directions.lstrip("L").rstrip("R")

lstrip("L") removes a contiguous block of 'L' characters from the beginning of the string, while rstrip("R") removes a contiguous block of 'R' characters from the end. The resulting substring mid contains only the segment where collisions are possible.

Counting the cars that will collide

Within the trimmed segment, any 'R' will eventually meet a 'S' or an 'L' to its right, and any 'L' will eventually meet a 'S' or an 'R' to its left. Each such car contributes exactly one collision, except when a 'R' meets an 'L' directly; that situation is counted as two separate collisions (one for each car). Because the total number of collisions equals the sum of the occurrences of 'R' and 'L' in the trimmed segment, the algorithm computes:

return mid.count("R") + mid.count("L")

The built-in count method scans the string once per call, but both scans are performed in highly optimized C code, making the overall operation very fast.

Edge Cases Handled

When the input string consists solely of 'L' characters, the left-trim operation removes the entire string, leaving mid empty. The subsequent counts both return zero, correctly indicating no collisions. The symmetric situation with only 'R' characters is handled by the right-trim operation in the same way.

If the string contains only stationary cars ('S'), the trimming steps leave the string unchanged, and both counts return zero, reflecting the fact that stationary cars do not generate collisions on their own.

An empty input string is also processed safely: trimming an empty string yields another empty string, and the counts again return zero.

When the string begins with a mixture of 'L' and other characters, only the leading 'L' block is stripped; any 'L' that appears later, after a 'S' or 'R', remains in mid and is correctly counted as part of a collision. The same logic applies to trailing 'R' characters.

Performance Optimizations

The algorithm relies on native string operations that avoid explicit Python-level loops. The lstrip and rstrip functions execute in linear time but are implemented in C, reducing interpreter overhead. Likewise, the count method traverses the string at the C level, providing fast aggregation without allocating intermediate data structures. By limiting the work to three passes over the input (one for trimming, two for counting), the solution achieves high throughput even for very long strings.

Because the algorithm never creates additional copies of the original string beyond the trimmed view, memory usage stays minimal. The trimmed substring shares the underlying buffer with the original string, so the approach avoids unnecessary allocation. This design choice contributes to both speed and low memory footprint.

Imagine a long, narrow road where little toy cars are moving in different directions. Some cars are driving to the right, some are driving to the left, and some are parked perfectly still. The cars heading off the edge of the road will drive away into the sunset and never bump into anything, so they do not matter for this game. Once those cars are gone, the remaining ones are trapped in the middle of the road. Any car that is moving and hits another car or a parked car will cause a little crash. Even if cars keep crashing one after another, all those bumps add up to a big score. The code looks at the cars stuck in the middle and counts how many are moving left or right to figure out how many crashes happen during all the commotion.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python				TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++	JS	Java	Python		Go	Rust	TS
	Progiez	C++		Java	Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	suxrobGM					C#
	varunu28			Java
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality