> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/stacks #leetcode/stacks ]
> [project group:: Neetcode 150]
> [difficulty:: easy]
> [status:: to begin]
> [link:: ]
> [up:: [[Leetcode MOC]]]
## Problem
There are `n` cars going to the same destination along a one-lane road. The destination is `target` miles away.
You are given two integer array `position` and `speed`, both of length `n`, where `position[i]` is the position of the `ith` car and `speed[i]` is the speed of the `ith` car (in miles per hour).
A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper **at the same speed**. The faster car will **slow down** to match the slower car's speed. The distance between these two cars is ignored (i.e., they are assumed to have the same position).
A **car fleet** is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
Return _the **number of car fleets** that will arrive at the destination_.
### Examples
Example 1
```
**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 car starting at 0 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.
Note that no other cars meet these fleets before the destination, so the answer is 3.
```
Example 2:
```
**Input:** target = 10, position = [3], speed = [3]
**Output:** 1
**Explanation:** There is only one car, hence there is only one fleet.
```
Example 3:
```
**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 fleet moves at speed 2.
Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.
```
**Constraints:**
- `n == position.length == speed.length`
- `1 <= n <= 10^5`
- `0 < target <= 10^6`
- `0 <= position[i] < target`
- All the values of `position` are **unique**.
- `0 < speed[i] <= 10^6`
## Solution
### Mine
#### Python
```python
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pairs = []
for i in range(len(position)):
pairs.append((position[i], speed[i]))
pairs.sort(reverse=True)
stack = [pairs[0]]
for pair in pairs[1:]:
stack.append(pair)
target_time_1 = (target - stack[-2][0])/stack[-2][1]
target_time_2 = (target - pair[0])/pair[1]
if target_time_2 <= target_time_1:
stack.pop()
return len(stack)
```
#### Rust
### LC's
## Things I Learned
### Neetcode Video
First, combined position and speed into a list of tuples.
Now if you see them this way, you're looking at a system of linear equations. If you plot them on time vs. position axes, the speed becomes the slope for that particular car.
![[Pasted image 20230627213459.png]]
For any given two cars, how will we know if they will intersect? While we could calculate the intersection point, an easier method would be to just calculate the time at which each car reaches the destination. If a car further back reaches the destination "first," that means it'll be in a fleet with the one ahead of it.
![[Pasted image 20230627214451.png]]
When removing "merged" vehicles from analysis (they've formed a fleet), you want to keep the closer one, since it is the slower one. The fleet keeps the slowest speed.
Start analysis from "right" to left, because it'll not get extraneous fleets.
Going through cars is $O(n)$, but sorting is $O(n log n)$.
Algorithm:
1. Create list of tuples, sort by position
2. For cars right to left:
1. add first car to stack
2. Then second
3. If they'll collide, pop off the stack
3. Return len(stack) to get number of fleets
## Scratchpad
Basically we need to collect cars into fleets if they meet before reaching the destination.
One way would be to increment each car's position based on its speed (with limits for target and)