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 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!
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.
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
@@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?
@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.
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 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
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!
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.
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.
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 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.
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 you might fail on floating point operations. Its better to compare times multiplied by distance: ... if curr_distance * prev_speed > prev_distance * curr_speed: ...
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.
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.
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
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 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.
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
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)
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.
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
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)
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 😅
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
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.
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).
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)
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
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
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
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
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]
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 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!
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
@@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.
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
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
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".
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
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]
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!
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.
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];
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
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)
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.
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.
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!
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.
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.
I rarely leave any comment but I could not resist. The explanation was on top! You chewed the problem so well!
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 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.
@@ssuriset 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.
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 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
the understanding portion of this video is well made!
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!
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
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 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.
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();
}
};
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.
this is the best video on this channel, love how you broke it down to the end, top tier content!
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 ✅
I loved the fact that you demonstrated the process and then jumped on the actual solution! Kudos doing a great job!!
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
One of the best explanations from this channel!
why we are not counting whenever stack[-1]
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.
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.
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
I guess you could call this one fleetcode
heh
lol
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 will be a loyal neetcode user for the rest of my swe career. Thank you, Sir!
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.
This one made me cry in my sleep, no way this is medium
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
Wow that linear equation visualization was just 👌👌
Never would have thought of this.
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
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) ...
11:00
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 ❤
Wonderfully explained, keep it going neet 💯💯
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.
you could substract the target from the positions to get the graph start from 0, 0 :>
Here is a solution without reversing
for p,s in sorted(pair):
arrival = (target-p)/s
while stack:
if stack[-1]
you are my knight in shining armour! thanks once again!
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]
yes, this was clear after solving daily temperatures problem
You make these questions look so easy, great explanation.
Thank you so much!
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)
Very difficult concept but easy and short for codes, amazing.
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 😅
The best explanation I've watched on your channel so far. Damn!
Your explanation is golden
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
Many congratulations on 100K!!! you totally deserve it and more :)
are you talking about his subs or his salary?=)
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!
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).
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)
Congratulations! Good explanation!!!
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
this is a great way to look at this problem.
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
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
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
Love it ! Thanks for keeping post new videos
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
Is it still a stack if we're accessing the top element and the element after that?
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]
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]
Why do u need float() when single '/' already gives float division
@@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!
@@edwardteach2 Ofcourse it works without float(). Not sure which testcase failed for you
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.
This one was surprisingly intuitive for me...
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
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.
Awesome, great explanation! However, I think this can be done without using the stack as well.
They havent mentioned time for float values.We should only check for time if they collide or not in whole values.
the explanation for the problem was really awesome!
why we are not counting whenever stack[-1]
Awesome explanation. Thanks a lot.
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
Thank you so much. Very well explained.
i LOVE YOU NEETCODE!
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
Really like your explanation!
man thanks alot, this was really understandable
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".
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
very great solution,mind blown
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]
you really don't need a stack to solve this. Sorting is the key and then go in reverse
That was really good, thank you!!!
It is only linear if the cars are given in sorted order.
Yeah that's correct
Was a genius solution. very nice
Explanation is top!
Awesome explanation!
That orange must get a speeding ticket. Jokes aside, thank you for the video man.
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.
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!
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)
not strictly a stack problem, but yeah can be solved using stack.
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.
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.
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;
};
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
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)
The singular of "axes" is "axis"
omgomg finally!! Thank you so much
this solution is so dope
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.
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.
Perfect explanation bro, The java solution in your website didn't work for me, I am not sure why.