Count Collisions on a Road

medium stack simulation string

Problem

Cars sit on a road, numbered left to right. A string directions tells whether each car moves Left (L), Right (R), or Stays (S). All moving cars share one speed. A head-on R/L crash adds 2 collisions; a moving car hitting a stopped car adds 1. Collided cars stop forever. Return the total number of collisions.

Inputdirections = "RLRSLL"

Output5

R/L head-on (+2), then three more cars each pile into the stopped cluster (+1 each) for a total of 5.

Inputdirections = "LLRR"

Output0

The L's drive off to the left and the R's drive off to the right, so nothing ever meets.

directions (letters L, R, S)

def count_collisions(directions):
    stack = []
    collisions = 0
    for ch in directions:
        if ch == "R":
            stack.append("R")
        elif ch == "S":
            while stack and stack[-1] == "R":
                collisions += 1
                stack.pop()
            stack.append("S")
        else:
            if not stack or stack[-1] == "L":
                stack.append("L")
            else:
                collisions += 1
                if stack[-1] == "R":
                    collisions += 1
                stack.pop()
                while stack and stack[-1] == "R":
                    collisions += 1
                    stack.pop()
                stack.append("S")
    return collisions

function countCollisions(directions) {
  const stack = [];
  let collisions = 0;
  for (const ch of directions) {
    if (ch === "R") {
      stack.push("R");
    } else if (ch === "S") {
      while (stack.length && stack[stack.length - 1] === "R") {
        collisions++;
        stack.pop();
      }
      stack.push("S");
    } else {
      if (!stack.length || stack[stack.length - 1] === "L") {
        stack.push("L");
      } else {
        collisions++;
        if (stack[stack.length - 1] === "R") collisions++;
        stack.pop();
        while (stack.length && stack[stack.length - 1] === "R") {
          collisions++;
          stack.pop();
        }
        stack.push("S");
      }
    }
  }
  return collisions;
}

int countCollisions(String directions) {
    Deque<Character> stack = new ArrayDeque<>();
    int collisions = 0;
    for (char ch : directions.toCharArray()) {
        if (ch == 'R') {
            stack.push('R');
        } else if (ch == 'S') {
            while (!stack.isEmpty() && stack.peek() == 'R') {
                collisions++;
                stack.pop();
            }
            stack.push('S');
        } else {
            if (stack.isEmpty() || stack.peek() == 'L') {
                stack.push('L');
            } else {
                collisions++;
                if (stack.peek() == 'R') collisions++;
                stack.pop();
                while (!stack.isEmpty() && stack.peek() == 'R') {
                    collisions++;
                    stack.pop();
                }
                stack.push('S');
            }
        }
    }
    return collisions;
}

int countCollisions(string directions) {
    vector<char> stk;
    int collisions = 0;
    for (char ch : directions) {
        if (ch == 'R') {
            stk.push_back('R');
        } else if (ch == 'S') {
            while (!stk.empty() && stk.back() == 'R') {
                collisions++;
                stk.pop_back();
            }
            stk.push_back('S');
        } else {
            if (stk.empty() || stk.back() == 'L') {
                stk.push_back('L');
            } else {
                collisions++;
                if (stk.back() == 'R') collisions++;
                stk.pop_back();
                while (!stk.empty() && stk.back() == 'R') {
                    collisions++;
                    stk.pop_back();
                }
                stk.push_back('S');
            }
        }
    }
    return collisions;
}

Explanation

We sweep the cars from left to right and keep a stack of the cars that are still "live" to the left of where we are — each is either moving right (R) or already stopped (S). A car flying left (L) that has nothing live behind it just escapes off the road.

Pushing is easy: an R always goes onto the stack, since it might still catch up to something later. The interesting moments are when motion gets blocked.

When an S arrives, any cars driving right that are stacked right behind it pile into it one by one — that is the while loop popping every R on top, adding 1 collision each. After the pile-up, this position is a permanent wall, so we push an S.

When an L arrives and there is something live behind it, it crashes: +1 for the L stopping, plus an extra +1 if it met an R head-on. That spot becomes a wall, and just like the S case, every R queued behind now slams into the wall too, each adding 1. We then push a single S for the merged stopped cluster.

Every collision is counted exactly once as a car comes to rest against a wall, so a single linear pass over the string gives the answer. Equivalently, after trimming leading L's and trailing R's (which escape), every remaining non-S car contributes one collision.

Time: O(n) Space: O(n)