grid47 Exploring patterns and algorithms
Mar 30, 2024
5 min read
You have n cars on a straight road, each numbered from 0 to n-1 from left to right, with each car positioned at a unique location. You are given a string directions where each character represents the direction of a car (‘L’ for left, ‘R’ for right, and ‘S’ for stationary). Each moving car has the same speed, and the cars can collide under the following conditions: Two cars moving in opposite directions (‘L’ and ‘R’) will collide, counting as 2 collisions. A moving car colliding with a stationary car (‘S’) will result in 1 collision. After a collision, the cars involved stay at the collision point and no longer move. Your task is to calculate the total number of collisions that will happen.
Problem
Approach
Steps
Complexity
Input: The input is a 0-indexed string `directions` of length `n`, where each character is one of 'L', 'R', or 'S', denoting the direction of each car.
Example: "RSLSRL"
Constraints:
• 1 <= directions.length <= 10^5
• directions[i] is one of 'L', 'R', or 'S'.
Output: Return the total number of collisions that will happen.
Example: 4
Constraints:
• The output will be an integer representing the total number of collisions.
Goal: The goal is to count the number of collisions by checking when cars move in opposite directions or when moving cars collide with stationary cars.
Steps:
• Find the first car that moves towards the left and the last car that moves towards the right.
• Count the number of cars between them that collide based on the direction of movement and whether they are stationary.
Goal: The string `directions` is at least 1 character long and at most 10^5 characters long. Each character in `directions` is one of 'L', 'R', or 'S'.
Steps:
• 1 <= directions.length <= 10^5
• directions[i] is one of 'L', 'R', or 'S'.
Assumptions:
• The input string `directions` represents valid data with no other characters apart from 'L', 'R', or 'S'.
• Input: "RSLSRL"
• Explanation: The cars move in opposite directions, causing collisions between moving cars and stationary cars as they meet, and we count these interactions to get the total number of collisions.
Approach: The approach involves scanning the `directions` string and identifying the range of cars that will collide based on their movement directions, counting the number of collisions based on specific rules.
Observations:
• Cars moving in opposite directions (R and L) will collide.
• Cars moving towards a stationary car will cause a collision.
• We need to identify collisions between moving cars and stationary cars, and count collisions where two cars move towards each other.
Steps:
• Find the range of cars moving towards each other.
• Count collisions based on the direction of movement, considering stationary cars as well.
Empty Inputs:
• The input is guaranteed to have at least one car.
Large Inputs:
• The solution should handle strings of length up to 10^5 efficiently.
Special Values:
• The string may contain only 'L', 'R', or 'S'.
Constraints:
• The string should not contain any other characters apart from 'L', 'R', or 'S'.
intcountCollisions(string dir) {
int l =0, r = dir.size() -1;
int n = dir.size();
while(l < n && dir[l] =='L')
l++;
while(r >=0&& dir[r] =='R')
r--;
int cnt =0;
for(int i = l; i <= r; i++)
if(dir[i] !='S')
cnt++;
return cnt;
}
1 : Function Definition
intcountCollisions(string dir) {
Function definition starts. The function takes a string `dir` that represents the direction of cars ('L' for left, 'R' for right, 'S' for stopped) and returns an integer indicating the number of collisions.
2 : Variable Initialization
int l =0, r = dir.size() -1;
Initialize two variables `l` and `r` to track the leftmost and rightmost car positions in the string `dir`.
3 : Size Calculation
int n = dir.size();
Calculate the size of the input string `dir` and store it in the variable `n`.
4 : Left Pointer Movement
while(l < n && dir[l] =='L')
Move the left pointer `l` to the right while the car is moving left ('L').
5 : Left Pointer Update
l++;
Increment the left pointer `l` to skip over all left-moving cars ('L').
6 : Right Pointer Movement
while(r >=0&& dir[r] =='R')
Move the right pointer `r` to the left while the car is moving right ('R').
7 : Right Pointer Update
r--;
Decrement the right pointer `r` to skip over all right-moving cars ('R').
8 : Collision Counter Initialization
int cnt =0;
Initialize the collision counter `cnt` to 0. This will be used to count the number of collisions.
9 : Loop through Middle Cars
for(int i = l; i <= r; i++)
Loop through the cars between the left and right pointers (from `l` to `r`).
10 : Collision Check
if(dir[i] !='S')
Check if the car at position `i` is not stationary ('S'). If it's moving ('L' or 'R'), it's a collision.
11 : Increment Collision Counter
cnt++;
If the car at position `i` is moving ('L' or 'R'), increment the collision counter `cnt`.
12 : Return Collision Count
return cnt;
Return the final count of collisions detected.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: We scan the directions string only once to determine the collisions.
Best Case: O(1)
Worst Case: O(1)
Description: The solution uses a constant amount of extra space as we only need a few variables for the calculation.
