Car Fleet - Leetcode 853 - Python

[@Grawlix99]

As others mentioned, you don't need a stack. Simple code: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: pairs = [(position[i], speed[i]) for i in range(len(position))] fleets = curtime = 0 # a car's position is always < than target at the start, so it's fine to start curtime at 0 (no fleet will be at target at time 0) for dist, speed in sorted(pairs, reverse=True): destination_time = (target - dist)/speed if curtime < destination_time: fleets += 1 curtime = destination_time return fleets

[@albertd7658]

I did the same exact way, but wasn’t passing all the tests using python (not python3). Then I tried on python3 after seeing yours, and both of them work! do you know why it doesn’t;t work on python tho?

[@Grawlix99]

@@albertd7658 no idea, unfortunately... Perhaps some syntax change?

[@albertd7658]

@@Grawlix99 yea I guess so... But thanks anyway!

[@AlexAlex-bb8db]

@@albertd7658 FYI: It's a difference in how division works in Python2 and Python3. Here is the correct code for Python 2: class Solution(object): def carFleet(self, target, position, speed): pairs = [(position[i], speed[i]) for i in range(len(position))] fleets = curtime = 0 for dist, speed in sorted(pairs, reverse=True): destination_time = float((target - dist))/speed if curtime < destination_time: fleets += 1 curtime = destination_time return fleets Pay attention to the difference how we calculate the destination_time. I hope it helps you!

[@albertd7658]

@@AlexAlex-bb8db thanks a lot for the explanation!

[@pogchamper228]

This medium problem feels like hard one.

[@dk20can86]

For most of these stack questions i've been finding that a simple counter variable is my intuition and is more space efficient than a stack

[@Trizzi2931]

Like in this question all you need to do is take a counter and increment it whenever you find a higher time take to reach the target

[@stardrake691]

same, I don't like when solutions use stacks just for the sake of using a stack.

[@Tyler-jd3ex]

I just did that instead. It was a little more difficult just to arrange things in a way as to avoid having too many if statements but I managed. counter = 0 cars = [[p, s] for p, s in zip(position, speed)] last = -1 for p, s in sorted(cars)[::-1]: cur = (target - p) / s if last != -1 and cur

[@MTX1699]

I just never get an intuition naturally to use a stack. My only weaknesses are stacks and heaps. Others I could still manage.😢

[@ta32dev]

@@stardrake691 His approach indexes the second element of a stack - which wont work in most languages that implement a stack idiomatically and doesn't allow developers to index a stack. If you need indexing to access any element of the stack why are you using a stack?

[@brianevans4975]

Did anyone else find this problem pretty hard?

[@symbol767]

This problem sucks honestly

[@mk-19memelauncher65]

Especially when youre not using python so sorting array of tuples is a pain

[@tanaykamath1415]

@@mk-19memelauncher65 especially while using Java😭😭

[@leeroymlg4692]

finding it hard just to understand what the problem is asking!

[@jodo6329]

No, it was fine. Pretty easy actually if you're not a brainlet.

[@AmanSingh-ou6tq]

Very well explained. Like others also explained, we don't really need a stack here. I spent a lot of time trying to think of a linear approach as this was listed in the stack category. Regardless, you are doing very good work man. Thanks again.

[@ta32dev]

Yeah I don't see why its a "stack problem" especially since most languages don't allow any access to the second element of the stack. Since you should only referencing or using the top of the stack.

[@symbol767]

I hate problems like this, honestly it just makes me feel beyond dumb. This was a difficult one, I hate how interviewers ask this stuff

[@princeofexcess]

It is just a matter of solving a lot of problems.

[@ssuriset]

I love physics more than computer science.

[@princeofexcess]

@@ssuriset are you just as good at both?

[@ssuriset]

@@symbol767 Physics, I am really really good, but computer science…. not sure

[@princeofexcess]

@saisurisetti6278 we prefer what we are good at. People who hate math are usually terrible at it. Once they get good at it, they don't hate it anymore.

[@codeitaviral3]

the c++ code for the above: class Solution { public: static bool cmp(paira,pairb) { return (a.first >b.first); } int carFleet(int target, vector& position, vector& speed) { int n = position.size(); vector ps; stack st; for (int i = 0; i < n; i++) { ps.push_back({position[i], speed[i]}); } sort(ps.begin(), ps.end(),cmp); for(int i=0;i st.top()) { st.push(time_to_reach_des); } } return st.size(); } };

[@HrishikeshDeshpande]

No need to use stack, just use a variable to keep track of slowest arrival time and increase the counter if we find new slower.

[@director8656]

that's what i was thking, regardless i don't think you have to be spot on for most of these questions. It's a negligible change in efficiency .

[@director8656]

yeah just checked it 92 ms diff on average not too big of a deal from better than 89% to better than 99.7%

[@HrishikeshDeshpande]

Sometimes interviewers don't like extra space 😅

[@shivamgarg4201]

We need extra space for pairs array anyways so its not like we are reducing from O(n) to O(1)

[@VarunMittal-viralmutant]

This approach would work with right to left only, correct ? # Change position array, in place, to avoid an extra O(n) array for index, s in enumerate(speed): position[index] = (position[index], s) position.sort() if len(position) == 1: return 1 slowest_car = -1 car_fleet = 0 for p, s in position[::-1]: if (target - p)/s > slowest_car: slowest_car = (target-p)/s car_fleet += 1 return car_fleet

[@OrkhanAlizade]

I rarely leave any comment but I could not resist. The explanation was on top! You chewed the problem so well!

[@ryanmc1279]

if you're failing the test cases make sure you're using python3 and not python. python 3 allows for true division, meaning (target - position) / speed will be a floating point number. Before python3, you have to manually convert one of the values to a float, otherwise it will round down to the nearest integer.

[@kiss_my_axe]

Bingo

[@calebwalters1151]

I don't think I ever would've come-up with this solution on my own. Excited to take my DS & A class this Fall to better understand these concepts. Thanks so much for the explanation!

[@vineethsai1575]

I used time as a parameter to determine if one car can catch another. # POSITION, SPEED, TIME # [(10, 2, 1.0), (8, 4, 1.0), (5, 1, 7.0), (3, 3, 3.0), (0, 1, 12.0)] Now use this time parameter, if previous car has time

[@Ynno2]

You can do list(zip(position, speed)) to convert the zip iterator to a list, which is a bit shorter. Although you don't really need it because you can call sorted() directly on the zip iterator.

[@EthanRamos1203]

I'm going through the neetcode roadmap. I could not figure out why a stack was used, until this video. thank you Neetcode thank you

[@gregoryvan9474]

If you are using a stack, you can actually go from left to right (smallest position to biggest position) using a while loop to pop values out, see my code below. However, as others stated in the comments, you can just use a counter variable if going from right to left and avoid using a stack at all. def carFleet(target, position, speed): pair = [[p, s] for p,s in zip(position, speed)] stack = [] for p, s in sorted(pair): eta = (target-p)/s if not stack: stack.append(eta) else: while stack and eta >= stack[-1]: stack.pop() print(stack) stack.append(eta) return len(stack)

[@davidkang833]

Here's a solution without using a stack: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: combined = sorted(zip(position, speed)) prev_time = 0 num_fleets = 0 for pos, speed in combined[: : -1]: curr_time = (target - pos) / speed if curr_time > prev_time: num_fleets += 1 prev_time = curr_time return num_fleets

[@etonemoilogin]

@@davidkang833 you might fail on floating point operations. Its better to compare times multiplied by distance: ... if curr_distance * prev_speed > prev_distance * curr_speed: ...

[@chair_smesh]

@@davidkang833 Very nice, you're hired ✅

[@yt-sh]

the understanding portion of this video is well made!

[@kartikhegde533]

Was able to come up with this solution relatively easily using priority queue. I did submit 4 wrong answers before getting the right logic. Probably because I am solving the neetcode 150 stack series, it became relatively easier. I often find these problems to be solvable by IMAGINING HOW A PERSON WOULD SOLVE THIS MANUALLY.

[@ritiksaxenaofficial]

Good explanation, we can also calculate time taken by current car and last car in stack and if current car is taking more time then append current car in the stack. Time Complexity for me was 718ms. Note: append last element in pair in the stack first and then check for further elements via loop.

[@akshaygoel2184]

Really nice explanation and video! Just a Python comment I think using sorted( ..., reverse=True) or reversed( (sorted(...)) is more optimal here. This prevents you from duplicating memory.

[@shakthivelcr7]

I did not understand why we have to sort it

[@himanshusoni1512]

@@shakthivelcr7 so you get the cars on track according to their positions first. Given data is not sorted if you see it. Consider cars with positions 20, 10, 5. So if speed of car 5 is greater than both other cars 10, 20. 5 will only collide with 10 and then make a fleet but will not collide to 20. Its just real world mapping, so sorting scene is here.We need to put cars as per the position so that fleet can only be made with adjacent objects. Hope m not confusing you more [20,5, 10] --> after sorting [ 5 --> 10 --> 20], see 5 can make fleet with 10 not 20, similarly 10 can make fleet with 20. So when we sort and traverse on reversed list, we can easily create fleets.

[@abhinavsingh4221]

Great Video! Also one improvement. We don't need stack. If two cars collide then we can simply change the position and speed of current car to be same as the next car. Below is the C++ code: class Solution { public: class Cmp { public: bool operator()(const vector &v1, const vector &v2) const { return v1[0] < v2[0]; } }; int carFleet(int target, vector& position, vector& speed) { vector cars; for(int i = 0; i < position.size(); i++) { cars.push_back({position[i], speed[i]}); } sort(cars.begin(), cars.end(), Cmp()); int n = cars.size(); int fleetsCount = 1; for(int i = n-2; i >= 0; i--) { double speedNext = cars[i+1][1], speedCurr = cars[i][1]; double posNext = cars[i+1][0], posCurr = cars[i][0]; // time it will take to reach the target double timeNext = (double) (target - posNext) / speedNext; double timeCurr = (double) (target - posCurr) / speedCurr; // if speedNext > speedCurr then it will never form a fleet // if timeCurr

[@XxM1G3xX]

In case anyone wants to know how would the answer look using a hashmap here it is: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: hm = {position[i]: speed[i] for i in range(len(position))} stack = [] for pos in sorted(hm.keys(), reverse = True): time = (target - pos) / hm[pos] if not stack or time > stack[-1]: stack.append(time) return len(stack)

[@karandeepparashar9310]

Is it not that the time complexity is O(n*logn) instead of linear time as we sorted the array as well?

[@zac4ice]

Yeah i saw that python sorted() on the entire array is O(nlogn) ...

[@_carrbgamingjr]

11:00

[@tempestofsouls5693]

The solution makes sense in hindsight. How do we come up with this on the spot though? The problem seems pretty ad-hoc and no obvious signs as to what data structure or algorithm can be used

[@PlayingCode]

I loved the fact that you demonstrated the process and then jumped on the actual solution! Kudos doing a great job!!

[@tejas8211]

I really appreciate the fast that it's a physics problem. That's exactly how these problems should be - based on real world problem not these simple put the object in array kinda.

[@problemsolver4464]

Thanks for the video, based on your explanation, I think we don't need stack DS at all for this problem. Here is my solution with C++ which works fine without stack: class Solution { public: int carFleet(int target, vector& position, vector& speed) { vector availCarFleet; for (int i=0; i

[@ocoocososococosooooosoococoso]

One of the best explanations from this channel!

[@PIYUSH-lz1zq]

why we are not counting whenever stack[-1]

[@bltgz]

Here is a solution without reversing for p,s in sorted(pair): arrival = (target-p)/s while stack: if stack[-1]

[@sitronco]

I did this problem in a very similar way but on forward order using a decreasing monotonic stack. n = len(position) stack = [] cars = sorted( [(position[i], speed[i]) for i in range(n)] ) for pos, sped in cars: units_to_reach = (target-pos)/sped while stack and stack[-1]

[@elab4d140]

yes, this was clear after solving daily temperatures problem

[@VarunMittal-viralmutant]

Left to right works too: pos_speed = sorted(zip(position, speed)) car_fleet = [] for p, s in pos_speed: if not car_fleet: car_fleet.append((target - p) / s) continue # Next car is slower speed than previous one while car_fleet and (target - p)/s >= car_fleet[-1]: car_fleet.pop(-1) car_fleet.append((target - p)/s) return len(car_fleet)

[@arkamukherjee457]

Won't the reverse order be a tad bit faster because of not having the while loop (for large inputs)?

[@VarunMittal-viralmutant]

@@arkamukherjee457 It may impact the number of comparison like >= or

[@minciNashu]

@@VarunMittal-viralmutant but you dont really need a stack

[@VarunMittal-viralmutant]

@@minciNashu If you are working from left to right, then you do. From right to left, it is not

[@EranM]

you could substract the target from the positions to get the graph start from 0, 0 :>

[@СергейЛюбимов-у3ф]

This problems seems hard at first, because it obfuscates the "meat" of the problem with considerations for arrival time, position of the car if it catches up and so on. While in reality, you can solve it just by counting arrival time and increasing the fleet_counter when you got slower time

[@ladydimitrescu1155]

this is the best video on this channel, love how you broke it down to the end, top tier content!

[@sheepixy]

I really need to draw more diagrams, I was sure time played a role, but I couldn't figure out how until i saw this. great video and explanation ❤

[@Sundance2468]

I will be a loyal neetcode user for the rest of my swe career. Thank you, Sir!

[@FreeStuff4TheWorld]

I guess you could call this one fleetcode heh

[@NeetCode]

lol

[@sdegueldre]

There is no need for a stack to solve this problem, you can just track the number of fleets and the last arrival, as you only ever look at the top of the stack. If when you see a car, you only add it to the stack when its arrival time is larger than the previous arrival time, you will never pop from the stack. An append only list on which you only ever look at the last element is just a variable.

[@oldumvolley]

Thank you for all your content! I would advise you to emphasize the word 'not' more when forming a negative statement while talking, as I got confused at some point. btw No stack.pop() solution: def carFleet(target: int, position: list, speed: list[int]) -> int: fleets_stack = [] pairs = [(p, s) for p, s in zip(position, speed)] for p, s in sorted(pairs, reverse=True): # descending by position (the first el in the tuples) trt = (target - p) / s # current t-ime to r-each the t-arget if fleets_stack and fleets_stack[-1] >= trt: continue fleets_stack.append(trt) return len(fleets_stack)

[@Forever7Gamer]

It's also possible to solve this in O(n + target). It depends on the input but wouldn't this be preferrable compared to O(nlogn)? Here's the code: class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: road = [None] * (target + 1) for i, pos in enumerate(position): road[target - pos] = (pos, speed[i]) road = [v for v in road if v is not None] last = None res = 0 for pos, vel in road: t = (target - pos) / vel if last is None or t > last: last = t res += 1 return res

[@АртёмКурышкин-ж8ъ]

Thanks a lot for the video, but I don't understand the while instead of if. If we will use the example described below, the answer with if for it will be 2, but the correct answer is 1 (3, 3), (5,2), (7,1), (8,1), target = 12

[@josetovar3721]

You don't even need to sort the array, you can just use the initial car positions as as the index to an array that maps to how long it takes each car to arrive at the destination. making it O(n). This problem would definitely fit better on the arrays and hashing section.

[@ВладиславСоловйов-д2м]

Thank you!

[@LogviNata]

Now, this is good!

[@Bagunka]

Wow that linear equation visualization was just 👌👌

[@nguyen-dev]

We don't need a stack. We only need to keep track indices of 2 cars and check if these 2 cars can meet before the target. So, space complexity is O(1).

[@zaffa12]

This one made me cry in my sleep, no way this is medium

[@srikanthp5758]

Without stack class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: pairs = [[pos,spe] for pos, spe in zip(position, speed)] prev_time = None res = 0 for pos,speed in sorted(pairs)[::-1]: cur_time = (target-pos)/speed if not(prev_time and cur_time

[@dreadknot66]

Is it still a stack if we're accessing the top element and the element after that?

[@rahulsbhatt]

You make these questions look so easy, great explanation. Thank you so much!

[@b9944236]

Very difficult concept but easy and short for codes, amazing.

[@AlexRoy-h9s]

I just went super geek mode and google if pair.reverse( ) and pair[ : : -1] have the same time complexity in python and realized that pair.reverse( ) is done in O(1) space complexity while [ : : -1] is done in O(n) space complexity in python (Both have the same time complexity). So it would be technically more efficient to use pair.reverse( ) instead of pair[ : : -1], but for this problem it is not that much relevant. I couldn't come up with this solution so thank you very much for making this video explaining it super well. Always a huge fan of this channel. Please don't misunderstand my comment as trying to teach you or find faults in your code. I just was curious 😅

[@akshaychavan5511]

We don't really need a stack to solve this problem. The approach remains the same but without using a stack. Here's a python implementation for it - def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: pair = [[pos, speed] for pos, speed in zip(position, speed)] prevMaxTime = float('-inf') counter = 0 for pos, speed in sorted(pair, reverse = True): time = (target - pos)/speed if (target - pos)/speed > prevMaxTime: prevMaxTime = time counter += 1 return counter

[@nizarahamed.m1004]

They havent mentioned time for float values.We should only check for time if they collide or not in whole values.

[@AniruddhaShahapurkar-wu3ed]

A little modified version: 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 position, speed in pair: travel_time = (target - position) / speed if not stack or travel_time > stack[-1]: stack.append(travel_time) return len(stack) Note: We are appending to stack only when the car will be a part of a different fleet, as we have to return the number of fleets. # Eventually, every car will reach the destination any ways, we just need to figure out how many fleets we can form

[@RivaldiANS]

here is the modified solution without the need to do sorting based on the solution provided in the video (although this is slower compared to the solution provided by neetcode when I submitted this on leetcode) def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: hashmap = {} stack = [] for i in range(len(position)): hashmap[position[i]] = speed[i] for i in range(target - 1, -1, -1): if i not in hashmap: continue stack.append((target - i) / hashmap[i]) if len(stack) >= 2 and stack[-1]

[@michaelbrock1414]

Here's my linear O(target) time and space complexity solution in JS. No stacks necessary. FWIW I found the trick behind this solution really similar to that of Leetcode 347. var carFleet = function(target, position, speed) { const arrivalTimesByPosition = new Array(target).fill(-1); for (let i = 0; i < position.length; i++) { const distanceToTravel = target - position[i]; const arrivalTime = distanceToTravel / speed[i]; arrivalTimesByPosition[position[i]] = arrivalTime; } // arrivalTimesByPosition will be an array sorted by starting // positions. It'll likely have dummy slots filled with -1, // but that's no problem for us. A small price to pay for // linear O(target) time and space complexities. // We now loop through arrivalTimesByPosition backwards, i.e. // in order of cars initially closest to the target to those // furthest away let fleetAheadArrivalTime = -1; let numFleets = 0; for (let i = arrivalTimesByPosition.length - 1; i >= 0; i--) { const arrivalTime = arrivalTimesByPosition[i]; if (arrivalTime

[@sajeeree]

Since you are taking sorted pair, you probably will endup time complexity as nlogn, Did I miss anything?

[@metalyx1]

I am wondering why nobody said this before. Any answer about that? If you need to sort them, you'll not getting a O(n). Or did I missed smthing?

[@metalyx1]

Oops, he mentioned it on 10:54

[@hardiksinghal1360]

This problem was asked in my interview and I couldn't solve it and now I'm here just to understand how to do it

[@Chirayu19]

Awesome, great explanation! However, I think this can be done without using the stack as well.

[@edwardteach2]

You will need a float(target-p) / s to get the right answer Debugged the hard way when I was presented with the input target = 10, position = [6,8], speed = [3,2]. Output = 1, expected = 2 class Solution(object): def carFleet(self, target, position, speed): """ :type target: int :type position: List[int] :type speed: List[int] :rtype: int """ pair = [[p,s] for p, s in zip(position, speed)] stack = [] for p,s in sorted(pair)[::-1]: stack.append(float(target - p) / s) if len(stack) >= 2 and stack[-1]

[@haregneshbitsu3442]

class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: Stuple = zip(position,speed) dict1 = dict(Stuple) dict2 = {} srd = sorted(dict1.items(), key= lambda x:x[0]) if len(srd) == 1: return 1 result = [] for i in range(len(srd)-1,-1,-1): result.append((target-srd[i][0])/srd[i][1]) if len(result) > 1 and result[-1]

[@VarunMittal-viralmutant]

Why do u need float() when single '/' already gives float division

[@edwardteach2]

@@VarunMittal-viralmutant yea at first I left it as - (target - p) / s - and later it failed some test cases. Naturally regardless of interview or not, I wouldn’t code in the float() part unless I get different values. Let us know if it worked for u! Thanks!

[@VarunMittal-viralmutant]

@@edwardteach2 Ofcourse it works without float(). Not sure which testcase failed for you

[@nicolasrichard1100]

There is a difference in py2 vs py3 in the way `/` works. `3/2` returns 1 (int) in py2 but 1.5 (foat) in py3.

[@horrorcrave]

No stack is actually needed. Here is another way: class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: cars = sorted(zip(position, speed), reverse=True) fleets = 0 last_t = 0 for (p, s) in cars: t = (target - p) / s if t > last_t: fleets += 1 last_t = t return fleets

[@jideabdqudus]

Wonderfully explained, keep it going neet 💯💯

[@electric336]

Never would have thought of this.

[@anthonygong100]

What's the point of the stack when we're indexing stack[-2]. doesn't really make sense to use a stack in that case, at least to me.

[@Lamya1111]

you are my knight in shining armour! thanks once again!

[@gmhussein]

This one was surprisingly intuitive for me...

[@tejas8211]

I used to solve much harder physics problems when i was preparing for iitjee lol. Now this problem is looking hard to me. How times change

[@philcui9268]

I came out a slightly faster solution, hope that helps: class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: pos_spd_pair = [(pos,spd) for pos, spd in zip(position, speed)] pos_spd_pair.sort(reverse=True) stack = [pos_spd_pair[0]] for pos, spd in pos_spd_pair[1:]: pos_car_ahead, spd_car_ahead = stack[-1] # if time to arrive at the destination is shorter, will merge if (target-pos) / spd

[@sumitsharma6738]

Why stack just sort the array in descending order of position and use two pointer approach

[@poketopa1234]

I also thought of this. I think it works, but I haven't tested it yet.

[@chowdhuryan-noor2673]

Does anyone else think that this problem would be much better if they gave cars in sorted order? The question specifically states that it is a single lane road and cars cannot overtake one another. So when I saw test cases that didn't have car positions in order I got really confused and thought I was misunderstanding the problem somehow.

[@aliemadeldamiry]

No need to use a stack def carFleet(target: int, position: List[int], speed: List[int]) -> int: n = len(position) cars = sorted(zip(position, speed), reverse=True) max_time = 0 fleets = 0 for pos, spd in cars: time = (target - pos) / spd if time > max_time: max_time = time fleets += 1 return fleets

[@TheKikSmile]

yep this is prob the best solution, but can also be implemented as a stack which was more intuitive for me but of course higher space complexity. cars = [(pos, spd) for pos, spd in zip(position, speed)] cars.sort(reverse=True) stack = [] for i in range(len(cars)): time = (target - cars[i][0]) / cars[i][1] if len(stack) > 0 and time > stack[-1]: stack.append(time) if len(stack) == 0: stack.append(time) return len(stack)

[@mahamatoumar1963]

Your explanation is golden

[@gokukakarot6323]

I have a follow up question. what happens if the distance is not given?

[@krishankantray]

not strictly a stack problem, but yeah can be solved using stack.

[@seanleo1285]

It is only linear if the cars are given in sorted order.

[@NeetCode]

Yeah that's correct

[@last-life]

Flavortown - def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: sorted_fleet = sorted(zip(position, speed), reverse=True) fleets = [] for p, s in sorted_fleet: time = (target - p) / s if not fleets or time > fleets[-1]: fleets.append(time) return len(fleets)

[@Acel-01]

The best explanation I've watched on your channel so far. Damn!

[@AmolGautam]

this is a great way to look at this problem.

[@suparnaprasad8187]

Great explanation! But I've got a doubt -> According to the solution, whether a car A catches up to the car B in front of it is determined by the "final" speed of B. But let's say B catches up to the car C in front of it and SPEEDS UP such that now car A can't catch up to fleet BC. We know this by comparing a given car to the speed of the car on top of the stack. But what if A actually can catch up with B before B catches up with C? Are we testing the case in the above solution? I don't see how, because you're only comparing A to the UDPATED SPEED OF B aka after B meets C. Am I missing something? Any help appreciated!

[@ekropotin]

Hi. Amazing explanation, as usual! But with all due respect, a stack is absolutely unnecessary here. Can easily be done with two plain vars instead, therefore with O(1) memory. Overall I think the problem more fit into "Arrays and Hashing" category then in "Stack".

[@Matthias53787]

The singular of "axes" is "axis"

[@mahesh_kok]

we dont need list comprehension rather def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: data = list(zip(position, speed)) fleets = curr_time = 0 for pos, sp in sorted(data)[::-1]: destination_time = (target-pos)/sp if destination_time < curr_time: cur_time = destination_time fleets += 1 return fleets

[@Ynno2]

You can call sorted directly on the zip iterator, you don't need to explicitly convert it to a list

[@AlexzDum-6174]

you really don't need a stack to solve this. Sorting is the key and then go in reverse

[@CharlesMacKay88]

I dont understand why we just delete the element instead of merging the elements together? Why do we not consider when the two cars become a fleet at time X, it does not affect the rest of the problem?

[@bluesteel1]

Why is this stack ? Seems like a regular list question. Stack doesnt allow you to access ith value does it ?

[@habalgarmin]

Your explanation is the best. I tried to ask chatGPT to give me hints. It didn't succeed. My js solution (not the best) var carFleet = function(target, position, speed) { if (position.length === 1) return 1; const sorted = position.map((el,i) =>({p: el, v:speed[i]}) ).sort((a, b) => b.p - a.p); let stack = [sorted[0]]; for (let i = 1; i < sorted.length; i++) { const current = sorted[i]; const last = stack[stack.length-1]; const currentReachTime = (target - current.p) / current.v; const lastReachTime = (target - last.p) / last.v; if (currentReachTime > lastReachTime) { stack.push(current); } } return stack.length; };

[@mohamedbashir8737]

Perfect explanation bro, The java solution in your website didn't work for me, I am not sure why.

[@engineering-maths]

Sir the time complexity of this solution is O(nlogn) not O(n) because we use sorted() function in the solution and it's time complexity is O(nlogn)

[@DankMemes-xq2xm]

he mentions that in the video

[@ClaSiiCs]

Doesn't accessing the second from the top (stack[-2]) go against the whole idea of the stack data structure? Calling this a stack solution seems forced.

[@sebastianilinca1560]

Congratulations! Good explanation!!!

[@olalekanoloba9656]

is the position relative to the starting point or to the destination?

[@tahirraza2590]

the explanation for the problem was really awesome!

[@PIYUSH-lz1zq]

why we are not counting whenever stack[-1]

[@erenjaeger3522]

Never imagined that we had to use the physics formula for time

[@PIYUSH-lz1zq]

why we are not counting whenever stack[-1]

[@jamesmandla1192]

​@@PIYUSH-lz1zq the top of the stack is meant to represent the slowest car fleet at the time, so every time you add to the stack and don't pop you are adding an even slower car fleet which can't collide with the previous slowest. That's why we can return the length of the stack bc it's going to be the car fleets that didn't collide. We pop because when we find a faster car, we take it out and treat it like it's merged with the slowest car fleet at the previous stack top.

[@rakesha9176]

We're sorting it anyways it's going to be o(nlogn) / o(n^2(right) ?

[@Azharuddin-khan]

I was able to solve this problem on my own in a sense that I came up with the idea of sorting, had my own formula of determining collisions and when to append items to stack. The only problem I had was that due to poor wordings of the question I couldn't fully understand which car to keep after collisions, due to which I was failing one of the tests. But after hearing in diagram explanation part that we need to keep front car, I had to make small adjustments in my solution and it worked. Should I tick mark this question to be solved by myself?

[@ibib0086]

No

[@stopfdenpc]

So there is no actual linear time solution to this problem? I initially implemented pretty much like this, not looking at the data in detail and just assuming that the cars would be already in the order of which they appear on the road because why would anyone collect the data in a random order. Then when my solution failed due to lack of sorting, I realized the issue but assumed there must be a more superior solution to sorting it first. Why else would they just randomly offer the cars out of order and then you have to then just sort it yourself.

[@thoniasenna2330]

i LOVE YOU NEETCODE!

[@akshaydusad6642]

This problem would be such a headache to understand in interviews

[@christendombaffler]

Damn, this marks the first time I failed to understand your solution even after multiple watches, so I had to look elsewhere. Turns out this problem is just a pain to implement in C++.

[@elebs_d]

Thank you so much. Very well explained.

[@ayushkr3917]

# Solution in C++ class Solution { public: int carFleet(int target, vector& position, vector& speed) { vector ans; stack st; int n = speed.size(); for(int i=0; i=0; i--){ double time = (target - ans[i].first) / ((double) ans[i].second); if(st.empty() || st.top() < time){ st.push(time); } } return st.size(); } };

[@samwow26]

Isn't sorting an array O(n log n) time? You mention you can solve in O(n) time but use sorting. Am i missing something?