2211. Count Collisions on a Road

MediumStackString

Problem Description

In this problem, we are given a number n representing the number of cars on an infinitely long road. The cars are indexed from 0 to n - 1. Each car is at a distinct position and moves in either left, right, or stays stationary as indicated by the characters 'L', 'R', and 'S' in the given string directions.

Our task is to calculate the total number of collisions on this road given the rule that:

When two cars moving in opposite directions collide, the collision count goes up by 2.
When a moving car hits a stationary car, the collision count increases by 1.

A collision causes the involved cars to stop moving and stay at their collision point. Cars continue to move in their initial direction or stay still unless they collide.

We are asked to return the total number of collisions that will occur according to these rules.

Intuition

To solve this problem, the rstrip('R') and lstrip('L') methods come in handy because cars moving outwards towards the right or left indefinitely without facing each other will never collide with other cars. By stripping 'L' characters from the beginning and 'R' characters from the end of the string, we disregard those cases where no collisions will occur ever. What we are left with is the central part of the string where all potential collisions may happen.

Here's the intuition behind the solution:

Cars that move out of the scene immediately (those moving to the right at the end and to the left at the start) won't be involved in any collisions.
For the remaining cars (that might collide), each car will be involved in at least one collision except for those marked with 'S' which represent staying stationary. If a car is staying stationary, it will cause at most one collision (when hit by a moving car).

The provided solution counts the length of the stripped directions string (after removing the non-colliding 'L's at the start and 'R's at the end) to get the total number of cars that will be involved in collisions. From this, subtracting the count of 'S' characters gives us the total number of cars actually moving and therefore the total number of collisions since moving cars either hit another car or get hit.

Therefore, the total collision count is the number of actionable cars (moving cars) in the middle segment of the road since stationary cars will only add to the count when being hit, which the moving cars will guarantee. This solution ensures an efficient way to calculate the total number of collisions without having to simulate each car's movement or potential collisions explicitly.

Learn more about Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Solution Approach

The solution to this problem is quite straightforward and does not require complex data structures or algorithms. The Python code provided leverages the language's built-in string manipulation methods to efficiently compute the result.

String Trimming: Using the lstrip('L') and rstrip('R') methods, we trim the 'L' characters from the starting of the directions string and 'R' characters from the ending. This represents removing the non-interacting cars that are moving indefinitely to the left from the start or to the right at the end without any potential for collision.
Counting Moving Cars: Once we have the trimmed string d, which now contains only cars that will definitely be involved in collisions or will stay stationary, we need to find out the total number of moving cars. This is because each moving car will eventually collide with another car or a stationary object, resulting in a collision.
Calculating Collisions: The collision count can be calculated by taking the length of the trimmed string len(d) (which represents the number of cars that are either moving or staying) and subtracting the number of 'S' characters d.count('S') from it. The reason for this subtraction is that 'S' represents stationary cars, which do not actively cause collisions but rather are the targets of collisions by moving cars. Each 'S' reduces the collision count by 1 because a stationary car paired with a moving car results in only one collision, not two as with two moving cars.

The final line return len(d) - d.count('S') gives the total number of collisions as required.

In summary, the solution approach is to exclude cars that will not participate in any collisions and then to calculate the number of collisions based on the reduced set of cars that have the potential to collide. This solution is efficient as it avoids unnecessary iteration and complex logic, instead relying on simple string operations to achieve the desired result.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x1 2 3 x x x 6 x x1 2 6 x x x 3 x x

I don’t know

Example Walkthrough

Let's consider a small example with n = 7 cars and the directions string as "LRSRLRR". We'll follow the steps outlined in the solution approach to calculate the total number of collisions.

1. String Trimming

By trimming the string, we remove any 'L' from the start and any 'R' from the end that won't be involved in collisions. Trimming 'LRSRLRR' would result in 'RSRL'.

Original string: LRSRLRR After trimming: RSRL

2. Counting Moving Cars

Now, we need to count how many moving cars there are in the trimmed string. We look at the string after trimming and see two 'R's and one 'L', making a total of three moving cars. The single 'S' represents a stationary car that will not initiate a collision.

Trimmed string: RSRL Moving cars: R, R, L (3 in total) Stationary cars: S (1 in total)

3. Calculating Collisions

To calculate the number of collisions, we take the length of the trimmed string, which is 4, and subtract the number of 'S' characters, which is 1. This leaves us with 4 - 1 = 3 collisions.

Length of trimmed string: 4 (RSRL) Count of 'S': 1 Total collisions: 4 - 1 = 3

By following the above steps, we determine that there will be a total of 3 collisions according to the rules given in the problem description for our example string "LRSRLRR".

Solution Implementation

1class Solution:
2    def countCollisions(self, directions: str) -> int:
3        # Strip 'L' from the left end and 'R' from the right end of the directions string
4        # because 'L' at the start or 'R' at the end won't cause any collisions.
5        sanitized_directions = directions.lstrip('L').rstrip('R')
6
7        # Count the number of collisions:
8        # Total number of cars that can collide is the length of the sanitized directions
9        # subtracted by the number of 'S' (stationary) cars since 'S' cars do not move.
10        collisions = len(sanitized_directions) - sanitized_directions.count('S')
11
12        return collisions
13

1class Solution {
2
3    public int countCollisions(String directions) {
4        // Convert the input string to a character array for easier processing.
5        char[] directionChars = directions.toCharArray();
6      
7        // Get the length of the directionChars array.
8        int length = directionChars.length;
9      
10        // Initialize pointers for left and right.
11        int leftPointer = 0;
12        int rightPointer = length - 1;
13      
14        // Skip all the 'L' cars from the start as they do not contribute to collisions.
15        while (leftPointer < length && directionChars[leftPointer] == 'L') {
16            leftPointer++;
17        }
18      
19        // Skip all the 'R' cars from the end as they do not contribute to collisions.
20        while (rightPointer >= 0 && directionChars[rightPointer] == 'R') {
21            rightPointer--;
22        }
23      
24        // Initialize a counter for collisions to zero.
25        int collisionsCount = 0;
26      
27        // Iterate over the remaining cars between leftPointer and rightPointer.
28        for (int i = leftPointer; i <= rightPointer; ++i) {
29            // Count only the cars that are not 'S' (since 'S' means stopped and will not collide).
30            if (directionChars[i] != 'S') {
31                collisionsCount++;
32            }
33        }
34      
35        // Return the total count of collisions.
36        return collisionsCount;
37    }
38}
39

1class Solution {
2public:
3    int countCollisions(string directions) {
4        // Variables to keep track of the left and right pointers
5        int leftIndex = 0, rightIndex = directions.size() - 1;
6      
7        // Variable to count the number of collisions
8        int collisionCount = 0;
9
10        // Skip all cars moving out of bounds to the left at the beginning
11        while (leftIndex <= rightIndex && directions[leftIndex] == 'L') {
12            leftIndex++;
13        }
14
15        // Skip all cars moving out of bounds to the right at the end
16        while (leftIndex <= rightIndex && directions[rightIndex] == 'R') {
17            rightIndex--;
18        }
19
20        // Count collisions - all cars in the middle will collide, except those stationary ('S')
21        for (int i = leftIndex; i <= rightIndex; i++) {
22            if (directions[i] != 'S') {
23                collisionCount++;
24            }
25        }
26
27        // Return the total collision count
28        return collisionCount;
29    }
30};
31

1function countCollisions(directions: string): number {
2  // Determine the length of the directions string.
3  const directionsLength: number = directions.length;
4
5  // Initialize pointers to the start and end of the string.
6  let leftPointer: number = 0,
7      rightPointer: number = directionsLength - 1;
8
9  // Skip all 'L' from the start as they do not contribute to collisions.
10  while (leftPointer < directionsLength && directions[leftPointer] === 'L') {
11    leftPointer++;
12  }
13
14  // Skip all 'R' from the end as they do not contribute to collisions.
15  while (rightPointer >= 0 && directions[rightPointer] === 'R') {
16    rightPointer--;
17  }
18
19  // Initialize the collision count.
20  let collisionCount: number = 0;
21
22  // Check the remaining part of the string for 'L' or 'R' which will collide.
23  for (let index = leftPointer; index <= rightPointer; index++) {
24    if (directions[index] !== 'S') {
25      // Increment collision count for each 'L' or 'R' as they result in a collision.
26      collisionCount++;
27    }
28  }
29
30  // Return the total number of collisions.
31  return collisionCount;
32}
33

Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the given code is primarily determined by three operations:

lstrip('L'): This must check each character from the left until a non-L character is found. In the worst case, all characters are 'L', having a complexity of O(n) where n is the total number of characters in the string.
rstrip('R'): Similarly, this function must check each character from the right until a non-R character is encountered. This also has a worst-case complexity of O(n) when all characters are 'R'.
count('S'): This operation counts the number of 'S' characters in the modified string. This takes O(m) time where m is the length of the modified string. However, since m <= n, we also consider it O(n) for the worst case.

When these operations are added together, despite being sequential and not nested, the complexity is still governed by the longest operation which is O(n).

So, the overall time complexity of the code is O(n).

Space Complexity

The space complexity of the code is determined by the storage required for the modified string d.

d is a substring of the original input directions. However, it does not require additional space proportional to the input size; it uses the slices (which are views in Python) to reference parts of the original string without creating a new copy.
Thus, the extra space used is for a fixed number of variables which do not grow with the size of the input.

Hence, the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2211. Count Collisions on a Road

Problem Description

Intuition

Solution Approach

Example Walkthrough

1. String Trimming

2. Counting Moving Cars

3. Calculating Collisions

Solution Implementation

Time and Space Complexity

Time Complexity