# Count Collisions on a Road
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-collisions-on-a-road)
Canonical: https://scaleengineer.com/dsa/problems/count-collisions-on-a-road
**Data structures:** String, Stack
**Companies:** [Arcesium](https://scaleengineer.com/companies/arcesium)
---
## Problem
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.

You are given a **0-indexed** string `directions` of length `n`. `directions[i]` can be either `'L'`, `'R'`, or `'S'` denoting whether the `ith` car is moving towards the **left**, towards the **right**, or **staying** at its current point respectively. Each moving car has the **same speed**.

The number of collisions can be calculated as follows:

* When two cars moving in **opposite** directions collide with each other, the number of collisions increases by `2`.
* When a moving car collides with a stationary car, the number of collisions increases by `1`.

After a collision, the cars involved can no longer move and will stay at the point where they collided. Other than that, cars cannot change their state or direction of motion.

Return _the **total number of collisions** that will happen on the road_.

**Example 1:**

**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. 

**Example 2:**

**Input:** directions = "LLRR"
**Output:** 0
**Explanation:**
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'`.

# Approaches
## Iterative Simulation
This approach directly simulates the collision process. It repeatedly scans the road and resolves any immediate collisions between adjacent cars. The simulation continues in passes until no more collisions can occur in a full pass, at which point the road is stable.
**Time:** O(N^2). In the worst case, like `"RR...RL...LL"`, collisions propagate from the center outwards one car at a time. This could take up to O(N) passes, and each pass takes O(N) time. · **Space:** O(N), to store the character array representing the road state. If the input string is mutable, it could be O(1). In Java, strings are immutable, so a char array is needed for modifications.
**Pros:** It's a very direct and intuitive translation of the problem description.
**Cons:** Inefficient, with a quadratic time complexity in the worst-case scenario.; The implementation can be tricky. The order of checking and updating collisions matters and can lead to subtle bugs if not handled carefully.
### Explanation
The core idea is to mimic the physical interactions on the road. We treat the string of directions as the state of the road and update it iteratively. In each step of the simulation, we look for pairs of cars that are about to collide, such as an 'R' car followed by an 'L' car, or a moving car next to a stationary one. When a collision is found, we update the total collision count and change the state of the involved cars to 'S' (stationary). This process is repeated until a complete scan of the road reveals no new collisions. While intuitive, this method is slow because collisions might propagate one by one, requiring many passes over the entire string.

```java
class Solution {
    public int countCollisions(String directions) {
        char[] cars = directions.toCharArray();
        int n = cars.length;
        int collisions = 0;
        boolean changedInPass = true;

        // Repeat passes as long as collisions are happening
        while (changedInPass) {
            changedInPass = false;
            // Check for R-L head-on collisions first
            for (int i = 0; i < n - 1; i++) {
                if (cars[i] == 'R' && cars[i+1] == 'L') {
                    collisions += 2;
                    cars[i] = 'S';
                    cars[i+1] = 'S';
                    changedInPass = true;
                }
            }

            // Check for moving cars hitting stationary cars
            for (int i = 0; i < n - 1; i++) {
                if (cars[i] == 'R' && cars[i+1] == 'S') {
                    collisions += 1;
                    cars[i] = 'S';
                    changedInPass = true;
                }
            }
            // Check from right to left for 'L' cars hitting 'S' cars
            for (int i = n - 1; i > 0; i--) {
                if (cars[i] == 'L' && cars[i-1] == 'S') {
                    collisions += 1;
                    cars[i] = 'S';
                    changedInPass = true;
                }
            }
        }
        return collisions;
    }
}
```
### Algorithm
*   Convert the input string `directions` to a character array `cars` for easy modification.
*   Initialize `totalCollisions = 0`.
*   Use a `while` loop that continues as long as collisions are detected in a pass. A boolean flag, `changed`, can track this.
*   Inside the loop, iterate through the `cars` array to find and resolve collisions:
    *   Scan for adjacent `'R'` and `'L'` cars (`RL`). For each pair found, add 2 to `totalCollisions` and change both cars to `'S'`. Set `changed` to `true`.
    *   Scan for adjacent `'R'` and `'S'` cars (`RS`). For each, add 1 to `totalCollisions`, change `'R'` to `'S'`, and set `changed` to `true`.
    *   Scan for adjacent `'S'` and `'L'` cars (`SL`). For each, add 1 to `totalCollisions`, change `'L'` to `'S'`, and set `changed` to `true`.
*   The loop terminates when a full pass over the cars results in no changes (`changed` remains `false`).
*   Return `totalCollisions`.

## Stack-based Single Pass
A more optimized approach uses a stack to process the cars in a single pass from left to right. The stack keeps track of cars that are moving right ('R') and haven't collided yet. When we encounter a stationary ('S') or left-moving ('L') car, we can resolve any pending collisions with the 'R' cars on the stack and update the collision count accordingly.
**Time:** O(N). We iterate through the input string once. Each car is pushed onto and popped from the stack at most once, leading to linear time performance. · **Space:** O(N). In the worst case, for a string like `"RRR..."`, the stack's size can grow to be equal to the length of the string.
**Pros:** Efficient O(N) time complexity, as it processes each car only once.; Handles complex chain reactions correctly without repeated full scans of the road.
**Cons:** Requires extra space for the stack, which can be up to O(N) in the worst case.
### Explanation
This method avoids the repeated scans of the simulation approach. As we iterate through the cars, the stack maintains a record of cars whose final fate is not yet determined (primarily 'R' cars). When an 'L' or 'S' car is encountered, it provides the 'obstacle' that resolves the movement of the 'R' cars waiting on the stack.

*   **'R' car**: Pushed onto the stack, as it might collide with something to its right.
*   **'L' car**: If the stack has 'R' cars, they collide. A head-on `R-L` collision adds 2 to the count, and any subsequent 'R' cars on the stack pile into the wreckage, each adding 1. If the stack has an 'S', the 'L' car hits it, adding 1. Otherwise, the 'L' car moves away freely.
*   **'S' car**: Acts as a wall, causing all 'R' cars on the stack to collide and pile up, each adding 1 to the count.

This correctly calculates all collisions in one pass.

```java
import java.util.Stack;

class Solution {
    public int countCollisions(String directions) {
        Stack<Character> stack = new Stack<>();
        int collisions = 0;

        for (char dir : directions.toCharArray()) {
            if (dir == 'R') {
                stack.push('R');
            } else {
                if (!stack.isEmpty()) {
                    if (dir == 'L') {
                        if (stack.peek() == 'R') {
                            collisions += 2; // R-L collision
                            stack.pop();
                            // Other R's pile up
                            while (!stack.isEmpty() && stack.peek() == 'R') {
                                collisions += 1;
                                stack.pop();
                            }
                            stack.push('S'); // Collision creates a stationary block
                        } else if (stack.peek() == 'S') {
                            collisions += 1; // L hits a stationary block
                        }
                    } else { // dir == 'S'
                        // All R's on stack will hit this S
                        while (!stack.isEmpty() && stack.peek() == 'R') {
                            collisions += 1;
                            stack.pop();
                        }
                        stack.push('S');
                    }
                }
            }
        }
        return collisions;
    }
}
```
### Algorithm
*   Initialize `totalCollisions = 0` and an empty `Stack<Character>`.
*   Iterate through each car's direction `c` from left to right.
*   If `c` is `'R'`, push it onto the stack. These are potential future collisions.
*   If `c` is `'S'`:
    *   A stationary car acts as a wall. Any `'R'` cars on the stack will collide with it.
    *   Pop all `'R'` cars from the stack, incrementing `totalCollisions` for each one.
    *   Push `'S'` onto the stack to represent the (now potentially larger) stationary block.
*   If `c` is `'L'`:
    *   Check the top of the stack.
    *   If it's `'R'`, a head-on collision occurs. Add 2 to `totalCollisions`, pop the `'R'`. Then, pop any other `'R'` cars, adding 1 for each (as they pile up). Finally, push `'S'` to mark the collision spot.
    *   If it's `'S'`, the `'L'` car hits the stationary block. Add 1 to `totalCollisions`.
    *   If the stack is empty or the top is `'L'`, this car doesn't collide with anything to its left, so we ignore it.
*   Return `totalCollisions` after iterating through all cars.

## Two Pointers / Trim and Count
This is the most efficient approach, achieving optimal time and space complexity. It's based on a key insight: any cars moving left ('L') at the absolute beginning of the road and any cars moving right ('R') at the absolute end will never collide with anything. Collisions are confined to the cars between these two groups. By identifying this 'active' segment of the road, we can simply count all the moving cars within it, as each one is guaranteed to be involved in exactly one collision event.
**Time:** O(N). The algorithm involves a few passes over the string (one to find the left boundary, one for the right, and one to count), which sums to a linear time complexity. · **Space:** O(1). We only use a few integer variables for the pointers and the collision count, regardless of the input size.
**Pros:** Optimal O(N) time complexity.; Optimal O(1) space complexity, as it only uses a few variables.; Very simple and clean implementation.
**Cons:** The underlying logic might be less immediately obvious than a direct simulation.
### Explanation
The logic is to first eliminate the cars that cannot possibly collide. A car at index `i` moving left (`'L'`) can only collide with cars at indices less than `i`. If all cars to its left are also moving left, it will never collide. Thus, any prefix of `'L'` cars can be ignored. Similarly, a car at index `j` moving right (`'R'`) can only collide with cars at indices greater than `j`. If all cars to its right are also moving right, it will never collide. Thus, any suffix of `'R'` cars can be ignored.

After trimming these non-colliding cars from the left and right ends, we are left with a central segment. Within this segment, every single moving car (either `'L'` or `'R'`) is guaranteed to collide. Why? An `'R'` car in this segment must eventually encounter an `'S'` or an `'L'` to its right (otherwise it would have been part of the trimmed suffix). An `'L'` car must eventually encounter an `'S'` or an `'R'` to its left (otherwise it would have been part of the trimmed prefix). 

Therefore, the total number of collisions is simply the number of moving cars in this active segment.

```java
class Solution {
    public int countCollisions(String directions) {
        int n = directions.length();
        int left = 0;
        // Skip all 'L' cars from the left as they will never collide
        while (left < n && directions.charAt(left) == 'L') {
            left++;
        }

        int right = n - 1;
        // Skip all 'R' cars from the right as they will never collide
        while (right >= 0 && directions.charAt(right) == 'R') {
            right--;
        }

        int collisionCount = 0;
        // Iterate through the active zone
        for (int i = left; i <= right; i++) {
            // Every moving car in this zone will cause a collision
            if (directions.charAt(i) != 'S') {
                collisionCount++;
            }
        }

        return collisionCount;
    }
}
```
### Algorithm
*   Find the index of the first car that is not moving left. Initialize a pointer `left = 0` and increment it while `directions.charAt(left) == 'L'`.
*   Find the index of the last car that is not moving right. Initialize a pointer `right = n - 1` and decrement it while `directions.charAt(right) == 'R'`.
*   These `left` and `right` pointers define the 'active zone' where all collisions will occur.
*   If `left >= right`, it means no cars are in the active zone, so there are no collisions. Return 0.
*   Otherwise, iterate from `left` to `right`.
*   Count every car in this range that is not stationary (i.e., its direction is `'L'` or `'R'`). This count is the total number of collisions.
*   Return the final count.

# Solutions
### Java

```java
class Solution {
public
  int countCollisions(String directions) {
    char[] ds = directions.toCharArray();
    int n = ds.length;
    int l = 0;
    int r = n - 1;
    while (l < n && ds[l] == 'L') {
      ++l;
    }
    while (r >= 0 && ds[r] == 'R') {
      --r;
    }
    int ans = 0;
    for (int i = l; i <= r; ++i) {
      if (ds[i] != 'S') {
        ++ans;
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {string} directions * @return {number} */ var countCollisions =
  function (directions) {
    const n = directions.length;
    let [l, r] = [0, n - 1];
    while (l < n && directions[l] == " L ") {
      ++l;
    }
    while (r >= 0 && directions[r] == " R ") {
      --r;
    }
    let ans = r - l + 1;
    for (let i = l; i <= r; ++i) {
      if (directions[i] === " S ") {
        --ans;
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int countCollisions(string directions) {
    int l = 0, r = directions.size() - 1, count = 0;
    while (l <= r && directions[l] == 'L') {
      l++;
    }
    while (l <= r && directions[r] == 'R') {
      r--;
    }
    for (int i = l; i <= r; i++) {
      count += directions[i] != 'S';
    }
    return count;
  }
};

```

### Python

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

```