Medium
Car Fleet
There are n cars traveling to the same destination on a one-lane highway. You are given two arrays of integers position and speed, both of length n. position[i] is the position of the ith car (in miles) speed[i] is the speed of the ith car (in miles per hour) The destination is at position target miles. A car can not pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it. A car fleet is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet. If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet. Return the number of different car fleets that will arrive at the destination. Example 1: Input: target = 10, position = [1,4], speed = [3,2] Output: 1 Explanation: The cars starting at 1 (speed 3) and 4 (speed 2) become a fleet, meeting each other at 10, the destination. Example 2: Input: target = 10, position = [4,1,0,7], speed = [2,2,1,1] Output: 3 Explanation: The cars starting at 4 and 7 become a fleet at position 10. The cars starting at 1 and 0 never catch up to the car ahead of them. Thus, there are 3 car fleets that will arrive at the destination.
Constraints
n == position.length == speed.length. 1 <= n <= 1000 0 < target <= 1000 0 < speed[i] <= 100 0 <= position[i] < target All the values of position are unique.
The target time complexity for this problem is O(n log n) with a space of O(n). That could suggest a sorting operation along with a looping operation. If you were to graph each cars position and speed, what could you deduct from that? In our case when looping backwards, we only need to worry about the time it takes to reach the target: time = (target - position) / speed For any fleet of cars, we only need to worry about the slowest car in the fleet. Those values can be removed or 'popped' from a return list. Then return the length of the list.
*hover to un-blur*
class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: # first we zip both lists together into a single list of tuples # this list of tuples represents each car in the input pairs = [(p,s) for p,s in zip(position, speed)] # then we sort each car in the input depending on its position pairs = sorted(pairs, key=lambda tup: tup[0]) # you can use sort() for this, but this of technique using 'lambda' is # very effective for any array of objects # calculate the number of cars in the input pairsLen = len(pairs) - 1 # time = (target - position) / speed # create a return array which will hold speeds for each fleet. # a fleet is denoted by the slowest car in the fleet returnList = [] # we iterate backwards through the sorted array of cars # for each iteration we calculate the speed of the ith car # the time of the first car will be added to the returnList # if the 'time' of the ith car is faster than the the car ahead of it, # then it is apart of the fleet infront of it. we can forget this car and # continue with the next loop iteration. If a car is slower than the fleet # infront of it, we add it to the returnList and denote a new fleet for i in range(pairsLen, -1, -1): # calculate the completion time of the ith car time = (target - pairs[i][0]) / pairs[i][1] # if ith car is faster to target then the fleet infront, we ignore it if returnList and returnList[-1] >= time: continue # if ith car is slower, that denotes a new fleet and is added to the returnList else: returnList.append(time) # return the length of the new array # you can ignore returning the length of the list if you keep count # of the appends to returnList return(len(returnList))