#2211

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Count Collisions on a Road

Count Collisions on a Road is a problem where you calculate the number of car collisions based on their movements in a simulation.

string stack simulation

Problem Statement

You are given a string representing the movements of cars on an infinitely long road. The cars are indexed from 0 to n-1, where each car can either move left ('L'), right ('R'), or stay in place ('S'). The problem is to compute the total number of collisions that occur based on these movements.

A collision occurs when two cars moving in opposite directions ('L' and 'R') meet. If a car is stationary, it may also collide with moving cars that pass by. The solution should simulate the movements of the cars and track how many collisions happen, considering the interactions between moving and stationary cars.

Examples

Example 1

Input: directions = "RLRSLL"

Output: 5

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

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 <= 105
directions[i] is either 'L', 'R', or 'S'.

Solution Approach

Simulate Car Movements with a Stack

We can model the problem using a stack to manage the state of the cars. As we iterate through the directions string, we'll push cars into the stack based on their movements. When a car moving right ('R') encounters a car moving left ('L'), a collision will occur. We'll use the stack to track collisions as the cars meet and adjust the count accordingly.

Handle Stationary Cars Efficiently

Stationary cars ('S') do not move and only collide with moving cars. We'll need to check if a stationary car is hit by another car and update the collision count. Since stationary cars do not change direction, they provide a simple scenario where only a moving car's action matters.

Final Calculation of Collisions

Once the cars are processed through the stack, the number of collisions will be the result of the interactions between moving cars ('R' and 'L') and the stationary cars ('S'). A careful simulation ensures that all conditions are checked, and the total number of collisions is calculated based on the final state of the stack.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the length of the input string, as we process each character once. The space complexity depends on the stack size, which in the worst case can store all cars if they are moving in a way that does not result in early collisions.

What Interviewers Usually Probe

Tests understanding of stack-based state management in simulating real-world interactions.
Evaluates the candidate's ability to manage multiple car states (moving left, right, stationary).
Assesses the candidate's approach to handling edge cases, such as all cars moving in the same direction or all cars stationary.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding when collisions happen—confusing collisions between stationary cars and moving cars.
Overcomplicating the simulation without efficiently managing the cars' states with a stack.
Not accounting for edge cases like cars moving in the same direction or all cars being stationary.

Follow-up variants

Consider a scenario where no cars are moving; how does this affect the collision count?
What happens when all cars move in the same direction? How would you adjust the algorithm?
Extend the problem to track additional states, such as car speeds or varying collision impacts.

FAQ

How do I approach the Count Collisions on a Road problem?

Start by simulating car movements using a stack-based approach. Track the cars' directions and handle collisions efficiently by considering each car's interaction with others.

What is the pattern used in Count Collisions on a Road?

The problem uses stack-based state management to track car movements and calculate collisions. It involves simulating car interactions based on their directions.

Can a car stay stationary and still cause a collision?

Yes, a stationary car can collide with a moving car that passes by. The stationary car itself does not move, but the moving cars affect the collision count.

How should I handle edge cases like all cars moving in the same direction?

If all cars are moving in the same direction, no collisions will occur. You should check for this case early and return 0 as the result.

How does GhostInterview help me solve this problem?

GhostInterview helps you break down the problem into manageable parts, ensuring you understand how to simulate the car movements and handle collisions using a stack-based approach.

terminal

Solution

Solution 1: Brain Teaser

According to the problem description, when two cars moving in opposite directions collide, the collision count increases by $2$, meaning both cars stop, and the answer increases by $2$. When a moving car collides with a stationary car, the collision count increases by $1$, meaning one car stops, and the answer increases by $1$.

1

2

3

4

class Solution:
    def countCollisions(self, directions: str) -> int:
        s = directions.lstrip("L").rstrip("R")
        return len(s) - s.count("S")

Continue Practicing

#2296 design a text editor #2390 removing stars from a string #1910 remove all occurrences of a substring