Leetcode #2211: Count Collisions on a Road
In this guide, we solve Leetcode #2211 Count Collisions on a Road in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Stack, String, Simulation
Intuition
The problem has a natural nested or last-in-first-out structure.
A stack lets us resolve matches in the correct order as we scan.
Approach
Push items as they appear and pop when you can finalize a decision.
The stack captures the unresolved part of the input.
Steps:
- Push elements as you scan.
- Pop when a rule or match is satisfied.
- Use the stack to compute results.
Example
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.
Python Solution
class Solution:
def countCollisions(self, directions: str) -> int:
s = directions.lstrip("L").rstrip("R")
return len(s) - s.count("S")
Complexity
The time complexity is , and the space complexity is or . The space complexity is or .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.