Count Collisions on a Road

Medium
852.

Count Collisions on a Road

Count Collisions on a Road is a medium coding problem on strings, greedy and simulation, asked in Amazon, Google, Ola and Arcesium interviews.

Cars stand on an infinite road. directions[i] is 'L', 'R' or 'S' — moving left, moving right, or staying still.

When two moving cars meet head-on, both stop and that counts as two collisions. When a moving car hits a stationary one, it stops and that counts as one collision. Return the total number of collisions.

Example 1

Input
directions = "RLRSLL"
Output
5
Explanation
Every car except the ones that escape ends up stopped.

Example 2

Input
directions = "LLRR"
Output
0
Explanation
The left-movers drive away leftwards and the right-movers rightwards.

Example 3

Input
directions = "SSRSSRLLRSLLRSRSSRLRRRRLLRRLSSRR"
Output
20

Constraints

  • 1 <= directions.length <= 100000
  • directions[i] is 'L', 'R' or 'S'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} directions
 * @return {number}
 */
var countCollisions = function(directions) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Collisions on a Road — Solution in Python, Java & C++

Count Collisions on a Road solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Collisions on a Road is a medium coding problem on strings, greedy and simulation, asked in Amazon, Google, Ola and Arcesium interviews.

Problem statement

Cars stand on an infinite road. directions[i] is 'L', 'R' or 'S' — moving left, moving right, or staying still.

When two moving cars meet head-on, both stop and that counts as two collisions. When a moving car hits a stationary one, it stops and that counts as one collision. Return the total number of collisions.

Example 1

Input: directions = "RLRSLL"
Output: 5
Explanation: Every car except the ones that escape ends up stopped.

Example 2

Input: directions = "LLRR"
Output: 0
Explanation: The left-movers drive away leftwards and the right-movers rightwards.

Example 3

Input: directions = "SSRSSRLLRSLLRSRSSRLRRRRLLRRLSSRR"
Output: 20

Constraints

  • 1 <= directions.length <= 100000
  • directions[i] is 'L', 'R' or 'S'

Hints for Count Collisions on a Road

  1. Hint 1

    A car on the far left moving left never meets anything, and likewise on the far right moving right.

  2. Hint 2

    Strip that leading run of 'L' and trailing run of 'R' — those cars escape.

  3. Hint 3

    Every moving car that remains eventually collides, contributing exactly one.

How to solve Count Collisions on a Road

Only the cars that can escape avoid a collision: a prefix of left-movers and a suffix of right-movers. Everything else is trapped, and each trapped moving car stops exactly once — contributing one collision apiece.

Approach

  1. Advance i past the leading 'L' characters.
  2. Retreat j past the trailing 'R' characters.
  3. Count the characters in [i, j] that are not 'S'.

Why it works

Inside the trapped region there is a stationary car or an opposing car in both directions, so every moving car there must eventually stop — and the problem's scoring gives one collision per car that stops, whether it stopped against a moving or a stationary car. Cars that already stand still never move and so never collide.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Counting each head-on meeting as one collision halves the answer — it is two, one per car.
  • Only the leading 'L' run and trailing 'R' run escape; an 'L' in the middle is trapped.
  • Stationary cars inside the region contribute nothing.

Reference solution

Python

def countCollisions(directions: str) -> int:
    n = len(directions)
    i, j = 0, n - 1
    while i < n and directions[i] == "L":
        i += 1
    while j >= 0 and directions[j] == "R":
        j -= 1
    return sum(1 for k in range(i, j + 1) if directions[k] != "S")

Java

public static int countCollisions(String directions) {
    int n = directions.length();
    int i = 0, j = n - 1;
    while (i < n && directions.charAt(i) == 'L') i++;
    while (j >= 0 && directions.charAt(j) == 'R') j--;
    int count = 0;
    for (int k = i; k <= j; k++) if (directions.charAt(k) != 'S') count++;
    return count;
}

C++

int countCollisions(string directions) {
    int n = (int) directions.size();
    int i = 0, j = n - 1;
    while (i < n && directions[i] == 'L') i++;
    while (j >= 0 && directions[j] == 'R') j--;
    int count = 0;
    for (int k = i; k <= j; k++) if (directions[k] != 'S') count++;
    return count;
}

JavaScript

var countCollisions = function(directions) {
    var n = directions.length;
    var i = 0, j = n - 1;
    while (i < n && directions.charAt(i) === "L") i++;
    while (j >= 0 && directions.charAt(j) === "R") j--;
    var count = 0;
    for (var k = i; k <= j; k++) if (directions.charAt(k) !== "S") count++;
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Greedy Algorithms