Frog Jump
Vložit
- čas přidán 9. 07. 2024
- For business inquiries email partnerships@k2.codes My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi
SOCIAL
----------------------------------------------------------------------------------------------------------------
Support me on Patreon: / kevinnaughtonjr
Follow me on Twitter: / kevinnaughtonjr
Follow me on Instagram: / kevinnaughtonjr
Follow me on GitHub: github.com/kdn251
MUSIC
----------------------------------------------------------------------------------------------------------------
Blushes by Dj Quads
/ blushes
#coding #interviews #softwareengineering Discord: bit.ly/K2-discord - Věda a technologie
Do you guys prefer videos this long or did that get boring?
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.
@@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!
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!
@@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 :)
@@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!
Now this solution results in "Time Limit Exceeded"
That's correct , as this is not an optimal solution.
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.
For real interviewers really care about that part you think???
@@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!
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.
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.
@@stromboli183 leetcode has an evil test case that will TLE, but this check quickly discards the input as invalid.
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;
}
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.
it's not working for this case [0,1,3,5,6,8,12,17]
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
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!
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!
Thanks so much Yo! Super happy that my explanation made sense :)
Can anyone explain me what was the purpose of the first for loop (the one that start with i=3) thanks.
May I ask for complexity? is it O(n^2) from while and for loop in or just O(n)?
It's O(2^n) since we are searching all possible paths
Hi Kevin, Awesome explanation, bdw, where does that math solution came from?
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.
thats why its "hard" and not a medium problem.
@Kevin Naughton Jr
Can you also please add the time and space complexity for this problem
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?
What is the time complexity? Thanks!
This approach is giving time limit exceed error as of march 2022
@Kevin Naughton Jr. What is that for loop for? Any explanation? Why is it there?
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.
@Kevin Naughton Jr.
Can you plese put the Github link to the solution code for this problem?
A very nice and clean solution indeed. Never thought of using stack in such question.
Thanks Pooja!
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.)
Hey, kev
Why'd you use Stacks, instead of variables?
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
You are such a great teacher. Love your explanation
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).
could you also explain the dp solution for this problem? thanks alot!
Well explained. Could you explain the time complexity of your solution.
Why not maintain just 2 array lists or a queue. Why specifically 2 stacks are used here ?
Hi Kevin, could u analysis its time complexity, thx
I think worst case O(N^2)
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
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,............]
Can someone explain the math at the beginning? And also why we start jump distance at 0 instead of 1? That really puzzles me.
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
Which approach is this?
Amazing solution!
Like the rap/hip-hop songs played at the start of some of your videos. Can you share your playlist?
Rohan Manatkar check the description for the songs
What is the complexity of this code?
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.
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 :) )
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.
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?"
Thanks for your videos! It is really really useful!
Anytime! Thanks for watching!
Great build up towards solution ! Thanks for the help !
A diagram would be useful
Why we can't use queue instead of stack?
Hi Kevin, can you make a video of the Jump Game problem? (leetcode-55)
space and time complexity?
You don't have an error checking at line 3. What if the stones.length == 2 or 3
Hi Kevin, Amazing solution! Thank you for your great work. Can you help me with analysing the time complexity of this solution?
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
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
bogchamp
Is the runtime O(3^n) ?
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
If it changes to ' for (int i = jumpDistance+ 1; i >= jumpDistance - 1; i--) '
the result is 'Time Limit Exceeded'.
I am confused.
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.
You are not allowed to jump backwards.
Actually I like someone to explain the Maths. Is that check really necessary?
Why are you so cool
hahahah thanks Liyuan I'm sure you're waaaaay cooler :)
pls uplod rainwater trapping 2
Why recursion approach give TLE??
private boolean helper(int currPosition, int jumpDistance){
for(int i=jumpDistance-1; i
Is it kind of backtracking?
I would say so! Good point :)
Please increase voice
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.
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
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.
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.
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.
simplest solution
thanks!
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.
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
@@KevinNaughtonJr Thanks Kevin, please let me know about your availability this week.
@@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!
@@KevinNaughtonJr Thursday sounds great, can you tell me where should I be signing up?
@@sachinrodge3796 Sure! Follow this link and sign up for the "Phone Screen" tier: www.patreon.com/KevinNaughtonJr
Please explain the math
This is not hard. I have solved it using DFS.
Do you have it's recursive solution?
Didn't understand need to review
Hard to hear your voice. Too low
its not dfs its bfs .
voice is low
worst