Leetcode 853. Car Fleet
Explanation for Leetcode 853 - Car Fleet, and its solution in Python.
Problem
Example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at target.
The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation:
There is only one car, hence there is only one fleet.
Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The car starting at 4 (speed 1) travels to 5.
Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
Approach
We can use Stack to solve this problem. We can first pair two array position and speed into one array and call it pair.
Sort the array so elements in it are big to small. So that we can access the cars that are closest to target first.
Iterate through the array and append (target-position)/speed to the stack. Meaning remaining time it gets to target.
If stack[-1] <= stack[-2], then the car is meant to catch up to ahead. Thus, we should pop the stack.
In the end, return the len(stack), which will return the number of different car fleets that will arrive at the destination
Visualization of the Approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
position = [10,8,0,5,3], speed = [2,4,1,1,3], target = 12
pair = [(10,2), (8,4), (0,1), (5,1), (3,3)]
After sorting
pair = [(10,2), (8,4), (5,1), (3,3), (0,1)]
(target - position) / speed = (12-10)/2 = 1
stack = [1]
(target - position) / speed = (12-8)/4 = 1
stack = [1, 1]
Since len(stack) >= 2 and stack[-1] <= stack[-2], pop
stack = [1]
(target - position) / speed = (12-5)/1 = 7
stack = [1, 7]
(target - position) / speed = (12-3)/3 = 3
stack = [1, 7, 3]
Since len(stack) >= 2 and stack[-1] <= stack[-2], pop
stack = [1, 7]
(target - position) / speed = (12-0)/1 = 12
stack = [1, 7, 12]
thus return 3
Here is the Python code for the solution:
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pair = [(p,s) for p,s in zip(position, speed)]
pair.sort(reverse=True)
stack = []
for p, s in pair:
stack.append((target-p) / s)
if len(stack) >= 2 and stack[-1] <= stack[-2]:
stack.pop()
return len(stack)
Time Complexity and Space Complexity
Time Complexity: $O(n log n)$ due to sorting
Space Complexity: $O(n)$