RACE CAR | LEETCODE # 818 | PYTHON BFS SOLUTION

Рет қаралды 11,860

Күн бұрын

Пікірлер: 66

@RishinderRana 2 жыл бұрын

This was the only video that explained the concept clearly. Nothing more than needed and perfect for interview prep. Thanks for making this.

@majidshaikh5913 2 жыл бұрын

Yes indeed, Couple of video but this was crisp and making algorithms easy!

@rackfocus8299 2 жыл бұрын

Your solution made the most sense of all of the BFS and DP solutions that I have seen. Thank you.

@crackfaang 2 жыл бұрын

Thanks! I was hoping to write something that would give people an alternative to the DP nonsense with this question

@ksaigon 2 жыл бұрын

Hey, great video. I was wondering why do we check postion + speed > target and not simply postion > target? From the explanation (i.e we would go backwards once we've overshot), why don't we overshoot first before going backwards, rather than preemptively going backwards. Thanks and keep up the great work!

@manojmarneni-k5i 2 жыл бұрын

Since it is BFS, all neighbors of (pos, speed) should be together next in queue. So the neighbours (pos+1, speed *2) and (pos, 1/-1) should be together next in queue. I think this is just easier to write, otherwise you need to take care of the order in which (pos, 1/-1) and (pos+1, speed *2) is added, and manipulate moves accordingly.

@jubiliudu 6 ай бұрын

I spent my entire morning thinking about that, basically, if you just use the postion > target, you'll not cover the case where you need to reverse before overshooting, which might be the best solution in some cases, take for example target = 4. So, if you want to use this approach, which only considers the reverse after an overshoot, you need to also have another if to cover the reverse before the overshoot case: if ((pos > target && vel > 0) || (pos < target && vel < 0)) // Cover reverse after overshoot { q.push({moves + 1, pos, (vel > 0) ? -1 : 1}); } else if ((pos + vel > target && vel > 0) || (pos + vel < target && vel < 0)) // Cover reverse before overshoot { q.push({moves + 1, pos, (vel > 0) ? -1 : 1}); } However, it's definitely not necessary, it's tricky to see, I could only understand when I did a manual test, but just having the second condition is already enough to cover both situations: the reverse before and after the troubleshooting, just try to run manually a simple sample using target 6 that you'll see it.

@giannizamora7247 Жыл бұрын

I found neetcodes channel a while back and knew the style of explaining and keeping it short was awesome which you are also doing. Keep it up on this channel and it will blow up soon. Thanks

@samyakjain7422 2 жыл бұрын

thanks man i usually watch indian tutorials as they are native to me and easy to understand but giving ur video a chance was totally worth it....

@breadream 2 жыл бұрын

DP hater also here, thank you for making this vid! clear and helpful

@luusant 2 жыл бұрын

Thanks and congrats for the great work. I also hate DP and whenever I can model a problem using a graph, I do so :) Your videos have been helping me a lot!

@crackfaang 2 жыл бұрын

Haha yea man I detest DP. It’s such a terrible question type and doesn’t test your knowledge of algorithms at all

@leon10982 2 жыл бұрын

Best video for 818 !

@crackfaang 2 жыл бұрын

Thanks for the kind words

@alextecca 2 жыл бұрын

I love your commentary on DP it's so funny

@ashwanisharma8903 Жыл бұрын

wow! That was great question selection and amazing explanation. Thanks a ton.

@yunaf4609 2 жыл бұрын

This was an awesome explanation. Thanks for making this, looking forward to more videos :)

@AlfranAli 2 жыл бұрын

All positions between [-target,target] will be visited in worst case, the complexity in the video only tells of a specific position so overall time and space complexity would be O(t*logt)).

@crackfaang 2 жыл бұрын

This is not true. Here is the explanation for why it is log(T) from one of the staff at Leetcode: "The reason is that everything within the while loop can be done in O(1) time so the time complexity will be O(1) times however many times we perform the while loop. If we only consider the car moving forward to reach or pass t, then it will always take log2(t) steps. So O(1)·O(log2(t)) gives us O(log(t)). Since we only consider reversing the car when we are near t, the effect of step 3 on the time complexity is independent of t and can be thought of as O(1). As for the space complexity, during each cycle we add one or two items to the deque and remove 1. So in the best case, our space complexity will be O(1) (deque is always one item long) and in the worst case it could be O(log(t)) (always add 2 items and remove only 1)."

@baboon_baboon_baboon 2 жыл бұрын

@@crackfaang Are you sure about this? Leetcode website even has this as O(T*log(T)). For each node, you are honing towards target. There are T nodes and each hone in worse case is log(T) steps.

@Pl15604 2 жыл бұрын

@@baboon_baboon_baboon Yes! I am quite certain the gentleman is correct in claiming it is O(log(t)). This approach is a Divide & Conquer approach, "integrated" in a BFS pattern. Binary Search of a Tree is also a D&C approach, and it is also BFS (i.e., you only look at the children of a given root at any given moment). In Binary Search, the "pruning" consists of only visiting relevant nodes. In this approach, the acceleration (i.e., 2*speed), and the mere fact that he is not visiting any other nodes linked to one that was already visited along with some property (i.e., speed), together would consolidate a sufficiently strong pruning tactic to reach, if not a O(log(T)), a very close approximate to O(log(T)). Important: This algorithm is also different than any of those in the solutions available for this problem on LeetCode: the BFS solution from LeetCode comes with an inner for-loop: "for k in range(K+1)", which essentially adds to the complexity. Even more, if you run the algorithm he presented, you can get to 44-113ms but more below 100ms; Whereas if you run the BFS solution from LeetCode, you will get 2000-4000ms :D (The DP one from there is quicker at 500-700ms, whereas the quickest ever recorded was a DP at 25ms - for which I could only get 41ms the lowest after running it multiple times: hence, taking into account readability, code cleanliness, the overall complexity to understand the solution, this one would be your best bet to go with in an interview!) Hope this clarifies.

@slambam4592 2 жыл бұрын

@@Pl15604 This is incorrect for anyone reading this. Run this code for input 10000 and you'll see the counter run 4641 times... obviously not log(target). log(10000) = 13. Seems way off seen = set() queue = deque([(0, 0, 1)]) counter = 0 while queue: counter += 1 seq, pos, speed = queue.popleft() if pos == target: print(counter) return seq if (pos, speed) not in seen: seen.add((pos, speed)) queue.append((seq + 1, pos + speed, speed * 2)) if speed > 0 and pos + speed > target or speed < 0 and target > pos + speed: queue.append((seq + 1, pos, 1 if speed < 0 else -1)) return -1

@Pl15604 2 жыл бұрын

@@slambam4592 But it is not n*log2(target), as LC claims, is it? If target=10,000... It would be more like 130,000. Yours is 4,641. Seems way off, too ...

@bz9031 2 жыл бұрын

Hi in line 22, could you show why we change speed when position + speed > target? Why it isn't position > target?

@ivanlee1 2 жыл бұрын

I think it has to do with overshooting when having a big speed. Notice that on line 17, it is exploring the option of taking the big speed and then reverse. The code after line 19 is exploring the other option of slowly approaching the target. When it is close to the target, it will take a reverse command and then on the next move, it will go forward again starting from speed 1.

@amritanshu83 Жыл бұрын

What is the time complexity of the solution. it can be log(T) as we wont always reach target in log(T) steps. We might overshoot or move in opposite direction and have to reverse right? Also is it guaranteed we would always reach target eventually. iS there a case where we never reach target?

@samruddhisiddhamshettiwar3018 Жыл бұрын

Great solution. Thanks for creating this video.

@subahugu Жыл бұрын

Great solution and awesome explanation!

@mustafarocks98 2 жыл бұрын

You're a rockstar bro. Please don't stop making these videos. Could you do #1937 from google's top tagged?

@JaydenMomos 2 жыл бұрын

good solution. Lmao the last rant

@Ninjabdul Жыл бұрын

love this explantation bro

@RavinderPayal 2 жыл бұрын

hi interesting solution, however, are you sure about the solution having logN time complexity? A simple counter which was increment after every execution while loop yielded numbers bigger than target most of the time(tried target less than 100). Did you mean to say it's log N for very large numbers? For target = 10000, it takes 3472 iterations, which is clearly not log2(10000) . If we only count how many times items were queued, value is 3301

@Yurppppppppp 2 жыл бұрын

This was such a concise and clear explanation. Thank you!

@crackfaang 2 жыл бұрын

Glad you are enjoying the content!

@rayanfadhlaoui Жыл бұрын

Wow excellent explanation, thanks a lot !

@manojamrutharaj9071 2 жыл бұрын

Wonderful explanation, thanks

@Shubhaw 2 жыл бұрын

@Cracking FAANG can you or someone else explain the Time & Space complexity for this in detail? Thanks!

@MinhNguyen-lz1pg 2 жыл бұрын

just read the LC discussion man

@yixinchen344 2 жыл бұрын

for the given example, with target as 6, why isn't AARA as the shortest path to get to 6?

@yetian1968 2 жыл бұрын

Nice video and good explanation! There is one thing that bothers me. How do you prove that reverse early is a bad idea? Referring to your conditions for reversing.

@rmp251 Жыл бұрын

You can argue that reversing early is equivalent to overshooting and then reversing, except it uses an extra reverse (R) step (because we are initially facing forward).

@harmanjeetsingh7160 2 жыл бұрын

suppose we are at point 4 with speed 10, and point 2 with speed 4, we have to reach target 6 . we can reach sooner from point 2 as we don't have to come back. So sometimes going further back to increase speed should work? instead of immediately turning when we cross the target. please help what am I missing here?

@TheTaruna1 2 жыл бұрын

Hi, A question - Wonderful explanation! I am a newbie and do have a question. What is the need for a visited set in this problem? The solution is accepted even without using the visited set. Thanks for answering my question.

@crackfaang 2 жыл бұрын

The visited set is to prevent you from visiting points you have already touched. Perhaps the test cases aren’t big enough for it to exceed the time limit but if the path to the solution was very complex you could end up revisiting points multiple times which is not efficient

@georgema9252 2 жыл бұрын

Thanks, this was very helpful!

@crackfaang 2 жыл бұрын

Thank you for the kind words. Make sure to subscribe so you don’t miss future videos

@MrMattyHot Жыл бұрын

Thank you for your explanation. But there isn't any proofs why this type of pruning strategy is optimal for this issue. For my point of view this explanation is very important to say during real interview and can confuse interviewee.

@crackfaang Жыл бұрын

Proving this question’s solution is so far beyond the scope of the problem and let’s be honest 99% of candidates and interviewers don’t know the proof. It’s never really necessary to prove mathematically why your solution is optimal. Maybe in academia but if you’re interviewer is asking for a proof then they probably want you to fail 😂