Car Fleet - Leetcode 853 - Python
Vložit
- čas přidán 7. 08. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: neetcode.io/problems/car-fleet
0:00 - Read the problem
2:53 - Drawing Explanation
12:18 - Coding Explanation
leetcode 853
This question was identified as a google interview question from here: github.com/xizhengszhang/Leet...
#google #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
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
It is just a matter of solving a lot of problems.
I love physics more than computer science.
@@saisurisetti6278 are you just as good at both?
@@symbol767 Physics, I am really really good, but computer science…. not sure
@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.
Did anyone else find this problem pretty hard?
This problem sucks honestly
Especially when youre not using python so sorting array of tuples is a pain
@@mk-19memelauncher65 especially while using Java😭😭
finding it hard just to understand what the problem is asking!
No, it was fine. Pretty easy actually if you're not a brainlet.
This medium problem feels like hard one.
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
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?
@@albertd7658 no idea, unfortunately... Perhaps some syntax change?
@@Grawlix99 yea I guess so... But thanks anyway!
@@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!
@@AlexAlex-bb8db thanks a lot for the explanation!
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.
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.
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
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
same, I don't like when solutions use stacks just for the sake of using a stack.
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
I just never get an intuition naturally to use a stack. My only weaknesses are stacks and heaps. Others I could still manage.😢
@@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?
I rarely leave any comment but I could not resist. The explanation was on top! You chewed the problem so well!
I loved the fact that you demonstrated the process and then jumped on the actual solution! Kudos doing a great job!!
this is the best video on this channel, love how you broke it down to the end, top tier content!
the understanding portion of this video is well made!
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.
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 .
yeah just checked it 92 ms diff on average not too big of a deal from better than 89% to better than 99.7%
Sometimes interviewers don't like extra space 😅
We need extra space for pairs array anyways so its not like we are reducing from O(n) to O(1)
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
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
Is it not that the time complexity is O(n*logn) instead of linear time as we sorted the array as well?
Yeah i saw that python sorted() on the entire array is O(nlogn) ...
You make these questions look so easy, great explanation.
Thank you so much!
Love it ! Thanks for keeping post new videos
One of the best explanations from this channel!
why we are not counting whenever stack[-1]
Awesome explanation. Thanks a lot.
Congratulations! Good explanation!!!
Many congratulations on 100K!!! you totally deserve it and more :)
are you talking about his subs or his salary?=)
The best explanation I've watched on your channel so far. Damn!
Awesome explanation!
Really like your explanation!
Very difficult concept but easy and short for codes, amazing.
Your explanation is golden
Explanation is top!
the explanation for the problem was really awesome!
why we are not counting whenever stack[-1]
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
That was really good, thank you!!!
this is a great way to look at this problem.
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.
I did not understand why we have to sort it
@@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.
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.
Thank you so much. Very well explained.
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.
Bingo
you are my knight in shining armour! thanks once again!
Wonderfully explained, keep it going neet 💯💯
Never would have thought of this.
I guess you could call this one fleetcode
heh
lol
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.
Awesome, great explanation! However, I think this can be done without using the stack as well.
This one made me cry in my sleep, no way this is medium
very great solution,mind blown
omgomg finally!! Thank you so much
this solution is so dope
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]
Was a genius solution. very nice
is the position relative to the starting point or to the destination?
you could substract the target from the positions to get the graph start from 0, 0 :>
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.
Wow that linear equation visualization was just 👌👌
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
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
thanks for this.
This one was surprisingly intuitive for me...
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)
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
@@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:
...
@@davidkang833 Very nice, you're hired ✅
Perfect explanation bro, The java solution in your website didn't work for me, I am not sure why.
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
Since you are taking sorted pair, you probably will endup time complexity as nlogn, Did I miss anything?
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?
Oops, he mentioned it on 10:54
Here is a solution without reversing
for p,s in sorted(pair):
arrival = (target-p)/s
while stack:
if stack[-1]
Well explained.
when we sort, does it sort based on the first indices or the second? in pair of list
First, then second. So for example, [0,1] goes before [1,0], but if first indices match, [1,0] goes before [1,1]
They havent mentioned time for float values.We should only check for time if they collide or not in whole values.
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
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).
Awesome!
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?
No
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)
Why is this stack ? Seems like a regular list question. Stack doesnt allow you to access ith value does it ?
thanks man
Awesome 🤘
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.
Thank you!
Now, this is good!
I have a follow up question. what happens if the distance is not given?
We're sorting it anyways it's going to be o(nlogn) / o(n^2(right) ?
just amazing
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)
Won't the reverse order be a tad bit faster because of not having the while loop (for large inputs)?
@@arkamukherjee457 It may impact the number of comparison like >= or
@@VarunMittal-viralmutant but you dont really need a stack
@@minciNashu If you are working from left to right, then you do. From right to left, it is not
Why stack just sort the array in descending order of position and use two pointer approach
I also thought of this. I think it works, but I haven't tested it yet.
So I was trying to implement the solution as NeetCode was doing the explanation and I got to the solution below. I thought I had it and submitted and it worked, I don't pop anything, but I just add values that are smaller than the ones present at the stack, which means I have a monotonic stack. can anyone tell me why this works if not try to give me the explanation why it doesn't?
var s = new Stack();
var a = new (int,int)[position.Length];
for (int i = 0; i < a.Length; i++)
{
a[i] = (position[i], speed[i]);
}
Array.Sort(a);
for (int i = a.Length - 1; i >= 0; i--)
{
var (p, sp) = a[i];
var r =(double)(target - p) / sp;
if(s.Count() == 0)
{
s.Push(r);
}
else if(s.Any() && s.Peek() < r)
{
s.Push(r);
}
}
return s.Count();
I'm not sure how the sorted(pair) function work, does it sort by position or speed? When I'm trying to print the sorted(pair), it seems like it sorts the pair by the position, not the speed. Is that what we want?
It sorts by the first element (in this case position). When there is a tie, it sorts by the second element (in this case speed). We want to sort by position bc/ a car that is initially behind another car will never pass that car; so, if we are moving faster than a car in front of us, we "collide" and slow down to that cars speed (which means we also share their position).
The second element is irrelevant for the purposes of sorting for the leetcode version of this problem, because it guarantees all of the positions are unique. We just need to pair them first because we need the two values together.
tis is awesome
You explained it good. Thanks
This problem would be such a headache to understand in interviews
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
what is the big o, for this solution?, i thought that when you sort the time complexity goes to O(nlogn), why is not in this example?
Sorting in python would actually take o(nlogn) so the time complexity of this solution is indeed O(nlogn).
I think if we'd use radix sort for the sorting the time complexity can be lowered down to O(n) - but I wouldn't implement it for the sake of this solution haha
damn it was a good problem. Good explanation
It is only linear if the cars are given in sorted order.
Yeah that's correct
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
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]
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.
May I ask what's the difference between sorted(pair)[: : -1] and sorted(pair[: : -1])? The outcomes were not the same.
the first one reverses the sorted pair array, while the second one reverses the pair array then sorts that.
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?
Never imagined that we had to use the physics formula for time
why we are not counting whenever stack[-1]
@@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.
its not working for all the test cases in leetcode
not strictly a stack problem, but yeah can be solved using stack.
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.
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".
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
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++.
I don't know why this can run on python3, the latest python compiler on leetcode can't run through test case 11.
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.
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
i love you so much