Car Fleet

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

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