Problem Statement in English

You are given a string directions, where each character is either ‘L’, ‘R’, or ‘S’, representing the direction a car is moving:

  • ‘L’ indicates the car is moving to the left.
  • ‘R’ indicates the car is moving to the right.
  • ‘S’ indicates the car is stationary.

All the cars are moving on an infinite road. When two cars collide, they become stationary (i.e., their direction changes to ‘S’). A collision occurs when:

  • A car moving to the right (‘R’) meets a car moving to the left (‘L’).
  • A car moving to the right (‘R’) meets a stationary car (‘S’).
  • A car moving to the left (‘L’) meets a stationary car (‘S’).

Return the total number of collisions that will occur on the road.

Approach

Since the cars can only collide when they are moving towards each other or when one of them is stationary, we can use a stack to keep track of the cars as we iterate through the directions string.

When we encounter a car moving to the right (‘R’), we push it onto the stack. When we encounter a car moving to the left (‘L’) or a stationary car (‘S’), we check the top of the stack to see if there are any cars that can collide with it. If there are, we count the collisions and update the state of the cars accordingly.

Sometimes the current value changes after a collision, so we use a while loop to keep checking the stack until no more collisions can occur.

Only then do we push the current car onto the stack.

Solution in Python


class Solution:
    def countCollisions(self, directions: str) -> int:
        count = 0
        directions = list(directions)
        stack = []

        for v in directions:
            if not stack:
                stack.append(v)
                continue

            curr = v
            added = False

            while stack:
                if curr == "S" and stack[-1] == "R":
                    count += 1
                    stack.pop()
                elif curr == "L" and stack[-1] == "S":
                    count += 1
                    curr = "S"
                elif curr == "L" and stack[-1] == "R":
                    count += 2
                    stack.pop()
                    curr = "S"
                else:
                    stack.append(curr)
                    added = True
                    break
            
            if not added:
                stack.append(curr)

        return count

Complexity

  • Time: O(n)O(n)
    We traverse the directions string once.

  • Space: O(n)O(n)
    Since we are using a stack to store the cars.

And we are done.