How do you solve Count Collisions on a Road on LeetCode?

Count Collisions on a Road (LeetCode #2211) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Cars moving in opposite directions always collide with a fixed pattern.

What is the brute force solution for Count Collisions on a Road?

The brute force approach for Count Collisions on a Road is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks every pair of cars to see if they collide. This is simple but inefficient, as it examines all possible pairs. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Count Collisions on a Road?

Count Collisions on a Road uses the following concepts: String, Stack, Simulation. The recommended patterns to study are: Simulation, Two Pointers.

What are the interview tips for Count Collisions on a Road?

Clarify the rules of collision before starting to code. Think about edge cases, such as all cars moving in the same direction. Explain your thought process clearly while coding to show your understanding.

What are common mistakes when solving Count Collisions on a Road?

Not considering the case where stationary cars are involved in collisions. Failing to update the state of cars after a collision.

#2211

Count Collisions on a Road

Medium

StringStackSimulationSimulationTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution processes the string in a single pass, counting collisions based on the direction of cars. This is efficient because it avoids unnecessary comparisons.

⚙️

Algorithm

3 steps

1Step 1: Initialize a collision counter to 0.
2Step 2: Traverse the directions string from left to right.
3Step 3: For each car, check its direction and update the collision counter based on the rules defined.

solution.py18 lines

1def countCollisions(directions):
2    collisions = 0
3    n = len(directions)
4    for i in range(n):
5        if directions[i] == 'R':
6            if i + 1 < n and directions[i + 1] == 'L':
7                collisions += 2
8                directions = directions[:i] + 'S' + directions[i + 1:]  # Mark as stationary
9            elif i + 1 < n and directions[i + 1] == 'S':
10                collisions += 1
11                directions = directions[:i] + 'S' + directions[i + 1:]  # Mark as stationary
12        elif directions[i] == 'L' and (i - 1 >= 0 and directions[i - 1] == 'R'):
13            collisions += 2
14            directions = directions[:i] + 'S'  # Mark as stationary
15        elif directions[i] == 'L' and (i - 1 >= 0 and directions[i - 1] == 'S'):
16            collisions += 1
17            directions = directions[:i] + 'S'  # Mark as stationary
18    return collisions

ℹ

Complexity note: The time complexity is O(n) because we only traverse the string once. The space complexity is O(n) due to the temporary storage of the characters in an array.

1Cars moving in opposite directions always collide with a fixed pattern.
2Stationary cars only contribute to collisions with moving cars, not with each other.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.