Do you guys prefer videos this long or did that get boring?
@loveyagrawal8873
5 жыл бұрын
Hi Kevin, I recently started going through your videos and honestly the videos are really helpful. Your videos are short and to the point and "not at all boring".. Thanks.
@KevinNaughtonJr
5 жыл бұрын
@@loveyagrawal8873 Hey Lovey I'm so happy to hear that that means so so much to me thank you! Please let me know if there's anything I can do to make the videos better and thank you so much for your support!
@jlecampana
5 жыл бұрын
The shorter the better of course, but some Dynamic Programming Questions just can't have short explanation. In fact I would have preferred that you explained that bit of "math" you did at the beginning. Thank you for the video, good work!
@KevinNaughtonJr
5 жыл бұрын
@@jlecampana The only reason I don't like getting into math is because it's missing the point of the problem (in my opinion). The real meat of this problem is the DFS / backtracking that is being done after the initial "math" check. It's worth noting too that this problem isn't using dynamic programming :)
@jlecampana
5 жыл бұрын
@@KevinNaughtonJr Yeah, I believe your solution is closer to a "Naive" approach? Incidentally, what would happen if during an Interview I go straight to solving the problem using DP? (Bottom-up in this case), In general and since my interview is soon I would like to know if interviewers expect a less than optimal solution *First* before you go in fancy and solve it using something like tabular/bottom-up DP for example. Sometimes I'm not sure if going for an Optimal solution right away is a good idea since the interviewer could suspect the problem's solution has been memorized by the candidate. Please let me know your thoughts, Thanks in advance!
@alexeydeynega7603
3 жыл бұрын
Now this solution results in "Time Limit Exceeded"
@ADORABLE-KRISHIKA
2 жыл бұрын
That's correct , as this is not an optimal solution.
@manishkumarpandey5224
4 жыл бұрын
Explanation of optimisation // optimisation for(int i = 3; i < N; i++) { // 0->1->3->6->10->15->21->28 max position possible with k+1 jumps each time starting at 0 // 0 1 2 3 4 5 6 7 if(stones[i] > stones[i-1] * 2) return false; // too big a gap } // Another optimisation but same thing as above essentially, use one or the other for(int i = 1; i < N; i++) { // 0->1->3->6->10->15->21->28 max position possible with k+1 jumps each time starting at 0 // 0 1 2 3 4 5 6 7 if(stones[i] - stones[i-1] > i) return false; }
@dongshuowu3454
5 жыл бұрын
It took me a short while to understand why it's very necessary to do a check that any stone should not be greater than twice of its previous. Trust me, interviewers cares a lot why this step should be like that. And actually the distance between any stone and its previous should not be greater than its index. Because, if the stones are perfected aligned at pos 0,1,3,6,10,..., i-2, i-1, i, we can see that each step we jump one unit more than the previous, therefore, we jump i-1 units to reach (i-1)th stone. In this case, our next jump should be no further than i units. If the ith stones if further away than i units, then we can't make it.
@KevinNaughtonJr
5 жыл бұрын
For real interviewers really care about that part you think???
@dongshuowu3454
5 жыл бұрын
@@KevinNaughtonJr You'll get a TLE without that check. Then how you set the exact distance limit between each stone becomes one important part of the solution. Nevertheless, I was really amazed at your solution, it's really helpful! Thank you!
@salonigupta1175
5 жыл бұрын
Can you please explain why we require that check than any stone should not be greater than twice its previous? I do not seem to get it.
@stromboli183
4 жыл бұрын
Why is that check necessary at all. The algorithm will fail automatically if at some point the next stone cannot be reached. I’d say it’s just an optimization, not a necessity.
@svofski
4 жыл бұрын
@@stromboli183 leetcode has an evil test case that will TLE, but this check quickly discards the input as invalid.
@agamarora7906
3 жыл бұрын
Amazing Solution Kevin. Regarding the Time Limit exceeded, I used (memoization) a Set visited to avoid revisiting the seen stones. This is what i did. class Solution { public boolean canCross(int[] stones) { for(int i = 3; i < stones.length; i++) { if(stones[i] > stones[i - 1] * 2) { return false; } } Set stoneSet = new HashSet(); Set visited = new HashSet(); for(int stone: stones) { stoneSet.add(stone); } int lastPosition = stones[stones.length - 1]; Stack positions = new Stack(); Stack jumps = new Stack(); positions.add(0); jumps.add(0); while(!positions.isEmpty()) { int pos = positions.pop(); int dis = jumps.pop(); for(int i = dis - 1; i
@annawilson3824
3 жыл бұрын
For everyone wondering about the MATH, it start from stone #4 (3rd for 0-based) since only after that the math starts to work out. Imagine max possible few jumps: 1, 2, 3, 4, that would cover the maximum range for stones located at 0, 1, 3, 6.... as you can see 1> 0*2, as well as 3 > 1*2, so only after that it works out. Now, why it is the case? Because, the distance cannot simply increase by a factor of 2, since jump is a slowly growing sequence where we increment by 1. Just compare functions X*2 and X+1. So, sanity check that removes bad test cases and thus helps to avoid TIME exceed is stone > prev_stone *2, which will always work starting with the 4th stone. One of the test cases that I saw included ...998, 99999999......, which would be removed early on and not even go through our algorithm logic! HTH.
@DeGoya
2 жыл бұрын
it's not working for this case [0,1,3,5,6,8,12,17]
@MarcinKrzyzanowski
4 жыл бұрын
Nicely done. thank you! The math part you put at the beginning is very important in the acceptance of this code. Without it, it exceeds the time limit, and this is because this trick rejects some nasty test cases that are expensive to iterate over. Maybe you'd like to extend the video (somehow) with an actual explanation of that part.
@amynguy
3 жыл бұрын
thats why its "hard" and not a medium problem.
@sivakumarg98
2 жыл бұрын
This approach is giving time limit exceed error as of march 2022
@tusharkarkera8615
5 жыл бұрын
Hey Kevin, great video, very clear explanation!! If you can do a time and space complexity analysis for your solution as well that would be helpful. Thanks!
@wakita
5 жыл бұрын
Thanks for posting this video! I think you do a great job of explaining your thought processes as you go through the problem and as someone who doesn't code in Java, I was still was very easily able to follow along. Awesome work!
@KevinNaughtonJr
5 жыл бұрын
Thanks so much Yo! Super happy that my explanation made sense :)
@handshadowfun5976
3 жыл бұрын
Thanks for the awesome video. Now this solution results in "Time Limit Exceeded" maybe because of new test cases. I added a new Set `visited([Int])` to remove duplicated visits for [nextPosition, jumpDistance], it ends up getting a good solution even without the initial math part. (Runtime: 116 ms, faster than 100.00% of Swift online submissions for Frog Jump.)
@jain007neeraj
5 жыл бұрын
Hi Kevin, Awesome explanation, bdw, where does that math solution came from?
@shubhamnaik9246
3 жыл бұрын
Can anyone explain me what was the purpose of the first for loop (the one that start with i=3) thanks.
@ashutoshkhare5798
3 жыл бұрын
Now it needs a "visited" set to work, otherwise, it throws TLE. class Solution { public boolean canCross(int[] stones) { for(int i=3; i stones[i-1] * 2){ return false; } } Deque positions = new ArrayDeque(); Deque jumps = new ArrayDeque(); positions.add(0); jumps.add(0); Set stonePositions = new HashSet(); for(int stone : stones){ stonePositions.add(stone); } Set visited = new HashSet(); visited.add("0-0"); int lastStone = stones[stones.length-1]; while(!positions.isEmpty()){ int currentPosition = positions.removeLast(); int currentJump = jumps.removeLast(); for(int nextJump = currentJump-1; nextJump
@saunaknandi1814
2 жыл бұрын
Which approach is this?
@davidgaster
4 жыл бұрын
If you decide to visit positions in the order [jumpDistance+1, jumpDistance, jumpDistance-1] this solution gets TLE. For very large input: [1,2,3,4,5,6,7,8,9,10,............]
@SamhitaPavan27788
3 жыл бұрын
Why not maintain just 2 array lists or a queue. Why specifically 2 stacks are used here ?
@urksome
3 жыл бұрын
I understand not wanting to spend a lot of video time on the math, but maybe in the future you could add like a little note explaining it that we can pause and read if we want
@poojakandoi8113
4 жыл бұрын
A very nice and clean solution indeed. Never thought of using stack in such question.
@KevinNaughtonJr
4 жыл бұрын
Thanks Pooja!
@natsworldUS
4 жыл бұрын
May I ask for complexity? is it O(n^2) from while and for loop in or just O(n)?
@adeebh.s1915
3 жыл бұрын
It's O(2^n) since we are searching all possible paths
@amitmagar1675
4 жыл бұрын
Well explained. Could you explain the time complexity of your solution.
@jaguarbailey5652
5 жыл бұрын
Thanks for posting this video Kevin! Is it possible to use memoization for this question, so that we don't have to recalculate in some scenarios. Let's say for a suitable array of stones we reach 4th stone with a jump from stone 2 and also there's a possibility to reach the 4th stone from stone 3. In this scenario we'll end up calculating for jump{1,2,} from the 4th stone. Is it possible to optimise such cases?
@shrimpo6416
3 жыл бұрын
Can someone explain the math at the beginning? And also why we start jump distance at 0 instead of 1? That really puzzles me.
@AbhishekKumar-ld5vm
3 жыл бұрын
if you come at let x u must have take step in between [1,x) so next maximum step u can take is x if y>2*x then y-x>x but u said ur step cant exceed x so u cant reach y means I y>2*x u cant reach to y from x
@g_455
4 жыл бұрын
@Kevin Naughton Jr Can you also please add the time and space complexity for this problem
@anssha2643
4 жыл бұрын
You are such a great teacher. Love your explanation
@nickelfang5116
4 жыл бұрын
If it changes to ' for (int i = jumpDistance+ 1; i >= jumpDistance - 1; i--) ' the result is 'Time Limit Exceeded'. I am confused.
@gustavoy23
4 жыл бұрын
I got the same result using this logic. Probably the test cases work better when it starts k-1. Depending on the test case, the path maybe be longer until it achieves the last stone if it starts k+1.
@harishrajora6453
4 жыл бұрын
You are not allowed to jump backwards.
@Tlacoyo59a
4 жыл бұрын
A diagram would be useful
@theantonlulz
2 жыл бұрын
Exceeds the time limit on Python. I knew it was too simple to just be a DFS or BFS. Edit: apparently it is a simple DFS. Idk what makes the difference in the video but in Python you have to add the decorator @functools.lru_cache to cache the function calls and save time (or otherwise memoize the calls somehow).
@phillipyang5899
3 жыл бұрын
What is the time complexity? Thanks!
@qiangzhu7634
5 жыл бұрын
Hi Kevin, could u analysis its time complexity, thx
@leomonz
4 жыл бұрын
I think worst case O(N^2)
@chetanpatteparapu7600
4 жыл бұрын
You don't have an error checking at line 3. What if the stones.length == 2 or 3
@RohanManatkar
4 жыл бұрын
Like the rap/hip-hop songs played at the start of some of your videos. Can you share your playlist?
@KevinNaughtonJr
4 жыл бұрын
Rohan Manatkar check the description for the songs
@DaveLeCompte
5 жыл бұрын
You mention that this is depth first search (DFS), but it could easily be implemented as breadth first search (BFS) as well. If I was interviewing you for a Google job, I'd ask you to describe the difference between the two, and when one might be better than the other, and if there are other traversals that might be worth considering.
@leomonz
4 жыл бұрын
I just start doing leetcode. If the question was asked, I probably simply say "The problem just required find if there is a path to jump thru, so DFS may save more space?"
@saulgoodman980
4 жыл бұрын
Is the runtime O(3^n) ?
@sunwoodad
4 жыл бұрын
Why we can't use queue instead of stack?
@cchaptini
4 жыл бұрын
space and time complexity?
@cuongme626
4 жыл бұрын
Actually I like someone to explain the Maths. Is that check really necessary?
@utkarshthakur3174
4 жыл бұрын
What is the complexity of this code?
@hari10599
5 жыл бұрын
Hey, kev Why'd you use Stacks, instead of variables?
@KevinNaughtonJr
5 жыл бұрын
Hey Hari, I just a stack because we don't know how many valid positions we'll have so we don't want to have to declare a ton of variables
@cw86129
5 жыл бұрын
could you also explain the dp solution for this problem? thanks alot!
@algorithmimplementer415
5 жыл бұрын
@Kevin Naughton Jr. What is that for loop for? Any explanation? Why is it there?
@doruwyl
5 жыл бұрын
The for loop is there to make sure you are not reaching TLE. For this testcase leetcode.com/submissions/detail/275263239/testcase/ without that for loop you will reach TLE.
@unmeshjoshi5948
4 жыл бұрын
Hey Kevin, That's a great explanation. I really like all your videos and learn a lot from them. It would be really great if you could include the time and space complexity too in your videos and how it is calculated for that problem. This will really help us to answer question on complexity too. Thank you.
@KevinNaughtonJr
4 жыл бұрын
Thank you and sometimes I forget to mention time/space complexity sorry about that, if you like my explanations and need help with interview questions like this check out the interviewing service I created thedailybyte.dev/?ref=kevin I'd recommend joining the annual tier if you can! (there's time/space complexity mentioned in each of the solutions :) )
@keertibhogaraju4495
4 жыл бұрын
Hi Kevin, Amazing solution! Thank you for your great work. Can you help me with analysing the time complexity of this solution?
@williamalexander5371
4 жыл бұрын
So we have a couple key steps. First, when we run through nearly the whole stone array, we perform about n operations to do the 2x distance check. Next, we have a hashset. Creation of a hashset can be said to take up n time as well, just like populating an array. Now in the while loop (which can also be a recursive implementation), we see that our complexity will be based on how many times we push and pop from the stack until the function terminates. When do we push? If the stone within jumping distance k, k-1 or k+1 exists. What’s the worst case? That all 3 stones exist. This means in the worst case, we are pushing roughly 3n elements to the stacks, which we need to later pop and process, which can simplify to n. The next part is a little more insidious. What is the range of possible k values? In other words, How many ways can we get to a particular stone? If I’m on a stone that is at position 20, maybe I arrived by hopping by 1 unit 20 times. Or maybe I just made a leap of 10 units. So k could take on up to m/2 different values, which could get very large (recursion often has bad complexity). We see the constraints tell us that each stone is limited to a 32 bit positive integer. We also see that the worst case is 1100 stones. This tells us a lot actually. Ordinarily, we are looking at roughly 1100*(2^30) calculations. But, in a list of only 1100 stones, we can pre-calculate the highest stone value. It is nowhere near 2^30. It is 1+2+3+ ... 1099, or about 1100^2 / 2, which is about 550,000. So worst case, the bulkiest part of our code is doing about 5 billion operations, or even less if you take into consideration that only the highest stone value has 550,000 possible k values. This is a completely manageable number. If we were not given such nice constraints, this solution could be said to be bounded by S*(m/2) + m + m or roughly S*m where S is the number of stones in the list and m is the maximum integer value that a stone could be. If we wanted to be even more particular, we could say that m is bounded by S, such that m
@aayushgoyal46
5 жыл бұрын
Hi Kevin, can you make a video of the Jump Game problem? (leetcode-55)
@wolborg1798
4 жыл бұрын
Great build up towards solution ! Thanks for the help !
@g_455
4 жыл бұрын
@Kevin Naughton Jr. Can you plese put the Github link to the solution code for this problem?
@durgesh2493
3 жыл бұрын
Please increase voice
@-Corvo_Attano
Жыл бұрын
JAVA CODE USING HASHMAP (9/11/2022) class Solution { public boolean canCross(int[] a) { if(a[1] != 1) return false; if(a.length == 2) return true; int last_stone = a[a.length-1]; int length = a.length; Map map = new HashMap(); for(int i=0;i
@prithazz
4 жыл бұрын
Yes agree, nobody likes math :) I was having trouble with this question, thanks for explaining the question. I think it would help if you drew some sample outputs in the comments of the code ex. {'0':'1'} corresponding to the line to help visualize the steps.
@MohitSinha4
4 жыл бұрын
Amazing solution!
@michaellk2254
4 жыл бұрын
bogchamp
@lifehacks9450
4 жыл бұрын
pls uplod rainwater trapping 2
@AtulKumarVermaOnline
5 жыл бұрын
Either you are very pro at solving these type of questions or you have prepared and solved the question already before starting the video. The solution passed in very first attempt, without even checking the sample test cases. Watching you solve the question in just 11 mins gives false picture that this question indeed can be solved in this much time.
@IranForeverFree
5 жыл бұрын
He is just explaining a solution he prepared or got from somewhere else, most likely on leetcode, he usually doesn't explain how one arrives to such solutions. in this particular one DFS, recursive or stack method will get TLE (even with HashSet trick) unless that math trick is checked on top. In a real interview the progression would be DFS, maybe stack over recursive calls, observing HashSet opt, then maybe some other observation that gets you to the math trick with some hints.
Hi Kevin, I have my interview scheduled on March 25th with Facebook. I am trying to get new job for front end developer. Would appreciate if you can help me with a mock interview.
@KevinNaughtonJr
5 жыл бұрын
Hey Puneet congrats that's amazing! I'd be happy to help you prepare by doing a mock interview. If you sign up on my Patreon under the "Phone Screen" tier we can get something scheduled right away! Is your interview a phone screen or onsite interview? Let me know! www.patreon.com/KevinNaughtonJr
@ChocolateMilkCultLeader
4 жыл бұрын
Please explain the math
@AbhishekKumar210607
4 жыл бұрын
This is not hard. I have solved it using DFS.
@swetavkamal
4 жыл бұрын
Do you have it's recursive solution?
@vk1618
4 жыл бұрын
Didn't understand need to review
@raiyanrazi1144
4 жыл бұрын
Why recursion approach give TLE?? private boolean helper(int currPosition, int jumpDistance){ for(int i=jumpDistance-1; i
@Raghavik1
5 жыл бұрын
Thanks for your videos! It is really really useful!
@KevinNaughtonJr
5 жыл бұрын
Anytime! Thanks for watching!
@chaoschao9432
5 жыл бұрын
Is it kind of backtracking?
@KevinNaughtonJr
5 жыл бұрын
I would say so! Good point :)
@ganapathinaik6899
5 жыл бұрын
Hard to hear your voice. Too low
@sachinrodge3796
5 жыл бұрын
Hi Kevin, I have my final interviews with Amazon on 14th March, I was hoping if you could help me with a mock interview, like you did previously for others. Thank you so much for your videos.
@KevinNaughtonJr
5 жыл бұрын
Hey Sachin, anytime! I hope you're finding the videos to be helpful. Congrats that's amazing I'm so happy to hear you have a final round with Amazon! I'd be happy to do a mock interview with you if you sign up for the "Phone Screen" tier on my Patreon we can schedule a session before the 14th here's the link to join: www.patreon.com/KevinNaughtonJr
@sachinrodge3796
5 жыл бұрын
@@KevinNaughtonJr Thanks Kevin, please let me know about your availability this week.
@KevinNaughtonJr
5 жыл бұрын
@@sachinrodge3796 Anytime! I can probably do Thursday. Once you sign up I can invite you to the Discord server and we can finalize everything there. I'm looking forward to it!
@sachinrodge3796
5 жыл бұрын
@@KevinNaughtonJr Thursday sounds great, can you tell me where should I be signing up?
@KevinNaughtonJr
5 жыл бұрын
@@sachinrodge3796 Sure! Follow this link and sign up for the "Phone Screen" tier: www.patreon.com/KevinNaughtonJr
Пікірлер: 127