### View *Car Fleet* on LeetCode

## Statistics

**Time Complexity**

O(n log n) - We must sort the array, and the built-in sorting algorithm takes O(n log n), and since this operation takes the longest time, it results in our O(n log n) time complexity.

**Space Complexity**

O(n) - We store each element from `position`

and `speed`

in a new list, resulting in the O(n) space complexity. Although technically, it requires O(2 * n) space, the big O complexity only represents the growth rate, and multiplying a linearly increasing function by two does not alter it.

**Runtime Beats**

99.92% of other submissions

**Memory Beats**

21.16% of other sumbissions

## Explanation

We must perform a few operations on the `position`

and `speed`

lists to prepare our list for iteration. The first is `zip(),`

which combines the elements at the same index from each list, creates a tuple of those values, and then returns a generator of the tuples. We then must convert the generator into a list by performing the `list()`

function on it.

Once we have a list of each car’s position and speed, we can execute the `.sort()`

method to re-arrange the data in a way that allows us to solve the problem the easiest.

We must also declare and initialize `fleets`

and `front_speed`

to 0.

We can now begin iterating through each car’s position and speed, starting from the end and ending at the front; this can be done by adding `[::-1]`

to our list `pos_speed`

.

We will approach this problem by calculating the car’s time (`(target-pos)/speed`

) to reach the target. Since the list was sorted in increasing order using the cars’ positions, we can determine which cars will combine into a fleet; this is determined by `if time > front_speed:`

.

- If the car’s time is faster, it will combine into a fleet and does not affect the number of
`fleets`

. - If the car’s time is
**not**faster, it will create a new fleet (`fleets += 1`

) and re-assign`font_speed`

to the new speed cars can not surpass without becoming a fleet.

Once all the cars have been iterated through, we simply `return fleets.`

## Data Structure Used

**Stack -** A stack is similar to an array, except you are only allowed to push/pop (add/remove) from the end of the stack. A stack follows the first in, last out, or FILO theme.

Since Python already has O(1) push (append) and pop (pop) operations, we do not need to use any libraries.

**Visual Examples** Visual of a stack being mutated, click to view

NeetCode is a YouTuber who has a very comprehensive video on this question and has plenty of visuals that help with the comprehension of this problem, click to view.

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pos_speed = list(zip(position,speed))
pos_speed.sort()
fleets = 0
front_speed = 0
for pos,speed in pos_speed[::-1]:
time = (target-pos)/speed
if time > front_speed:
fleets += 1
front_speed = time
return fleets