#Leetcode
Vložit
- čas přidán 20. 08. 2024
- Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.
Example 1:
Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4]
Output: 2
Got deviated with the hillarious sneaky movement behind 🤣🤣🤣🤣🤣. Great Explanation
was wondering if no one else saw it
@@kolawoleabdulrahman I see 😂😂
Life would have been easy if greedy had easy proofs: Nice explanation though !!
I was struggling to understand this question from last 2 days. i've watched ur video 3-4 times and now its clear to me. thanks for such a good explanation
1:21 someone sneaked into your room :P
Concept is Crystal clear, thanks
haha that's my mom trying to not make noise :)
Thanks for easy and nice explanation 😊
Honestly the way u explained i subscried your channel😁 took more than 5 video to understand this logic Thanks
Thank you Alisha !! This problem had become a nightmare for me. I couldn't find it's right solution. Finally your solution helped. This is such a simple solution
Her video should be on the top of the search results. Really great explanation.
Honestly mam appka samghane ka tarika ekdam nique hai thanku mam
let me add a trick i.e, add the arrowed line on the given place. this will prevent unnecessary iteration once the current and further has reached the last array element. and the previous jump is considered the optimal jump state.
for(int i = 0; i < n-1; i++){
--> if(curr==far && far>=nums.length-1) break;
far = Math.max(far, (i + nums[i]));
This condition is only going to be true when loop counter (i) reach the end of an array. Hence, I don't think to add this condition for reducing the iteration or further calculations in loop.
This is such an underrated solution to this problem throughout the youtube 🙏🙏
better u ignore. at least she is trying to help and Alisha plz ignore such bull shits....
@@adityatiwari8930 kya hua bhai underrated matlab kuch glt nai hai
@@adityatiwari8930 Tumne misunderstand kar diya comment ko. @lakshyasharma1940 ka matlab hai ki itne ache solution ka rating kaafi kam hai youtube par.
Salute to your dedication🙏🙏
I had solved this question using graph.
void BFS(vector adj[],vector &visited,vector &dist,int start){
queue q;
q.push(start);
dist[start]=0;
while(!q.empty()){
int node=q.front();
q.pop();
visited[node]=1;
for(auto i:adj[node]){
if(!visited[i]){
visited[i]=1;
q.push(i);
dist[i]=dist[node]+1;
}
}
}
}
int jump(vector& nums) {
int n=nums.size();
if(n
Aunty was so cute, tried her best not be in the frame. Thanks for awsome explanation.
Thanks a lot for such a great explanation!! Keep posting more video on Leetcode daily challenge.
The intuition of problem at 6.20 .. great!!!!
Easiest and best solution among all
This is is the best solution for me.
Good explaination
we have to break the loop if current reaches the last index , else one extra jump will be added!
Thanks mam, It took me 1 day to solve
The one condition is not their that is if(i >= furthest) {return -1 } bz we cannot move forward.
finally a video with good explanation..
I understand the solutin after 3 to 4 dry run.
if the jump is not possible then we can have a check . see below.
class Solution:
def minJumps(self, array, n):
if n == 0 or array[0] == 0:
return -1
jumps= current = farthest = 0
for i in range(n-1):
farthest = max(farthest, array[i] + i)
if i >= farthest:
return -1
if i == current:
current = farthest
jumps += 1
return jumps
Am i the only guy for whom the code is not working?
very good solution. good explanation
crystal clear concept thank u :)
thanks mam,you cleared my doubts ,i was struggling with this question
why did you run the loop until arr.size()-1 instead of arr.size()
have got this ??
@@PIYUSH-lz1zq bcuz if u go through the last element, the condition if(i==curr) will satisfy and jump++ will execute so you get an extra jump than required. Do a dry run to understand better.
literally good explanation
Nice Explanation
When you are not able to reach the last index, return -1, slight changes in code as shown below
int farthest = 0, jumps = 0, curr = 0;
//edge case
if(arr[0] == 0)
return -1;
for(int i=0; i
In the question it's written that we will reach the last index anyhow. so this piece of code is not needed.
Thanks - for easy explanation...
thanks di your explanation was superb
why do we iterate only until the second last index ?can you explain this?
just a correction u have not added condition if i > current: return -1 , which is one of the edge case..
Thanks for the explanation. But this is failing on 44th test case in Leetcode: [1,2,3].
Nice explanation . Thanks👍
IIB respect 🙇♀
easiest approach 💙💙
Thanks nicely explained
beautiful explanation
i think the intuition u gave that "current" will point to the last made optimal jump is not correct as because
for test case [4,1,1,3,1,1,1] the current will be pointing to indexes 0,4,6 which are not the correct positions to take a jump on...although the answer of jumps will be still 2 luckily and hence it passed that test case, so could u please explain the above test case?????????/
pretty good explanation
Very nice explanation mam. Thank you
U got my subscribe❤
Nice explanation, do upload more such videos..
thanks a lot for such a great explanation
such a great explanation, thanksss!
Really really good ...please increase example numbers ...like if any edge cases are there and some tips
Nice One
mashallaha mashallah solution Thanks!
really good explained
really helpful😊
why dp is not working here
Well explained!!, :)
I==current means????
Can you please explain what does i==current means ??? When I and curr is becoming same ??
after going through all the possible cases if we have reached the last case, then we need to update maxReach and jump as well.
mummy rocks!!!!!!
why size-1?
lol got it we dont want to go anywhere from last index
just amazing
Thanks
nice
Eagaely I am waiting for you ❤️❤️
why do u go till
my thoughts too
Why i < nums.size() - 1 but not < nums.size(), why it stops two indexes before?
Thank you Jim, for asking this
In this question, it's given you can always reach the last index
Consider the example [2,1,1,1]
The number of jumps you need to take is only 2 here
First jump at 0
Second jump at 2
So two times you go in the case (i==current) & increment jumps
If you take i< nums.size()
You will consider the jumps starting from the last index also
(when i==3) you will enter in the case (i==current)and again increase jumps and make it to 3 which is wrong
why num.sum()-1,and when we have to return true or false then only it is num.size()?????
bcuz if u go through the last element, the condition if(i==curr) will satisfy and jump++ will execute so you get an extra jump than required. Do a dry run to understand better.
[0 , 1, 1, 1, 1] output of this is 1. But and is -1.can u help me to solve this issue.
if u get 0 jumps at initial then there is no chance to jump to next step so u can write this edge case if(nums[0]==0)return 0
can anyone explain me that why we're traversing given array till the n-2 idx?
i checked with chatgpt, it said:
I changed the loop condition from for (int i = 0; i < nums.length; i++) to for (int i = 0; i < n - 1; i++) to iterate until the second-to-last element, as you only need to consider reaching the last element as a destination.
in other words, our aim is to reach the last element, therefore we only need to iterate till the second last element.
bcuz if u go through the last element, the condition if(i==curr) will satisfy and jump++ will execute so you get an extra jump than required. Do a dry run to understand better.
if the curr becomes >= lastIndex, we can break from the for loop, then there will be fewer number of iterations. a little more optimized.
1:22 peeche dekho peeche 😂
why did you run the loop until arr.size()-1 instead of arr.size()
Explaination is superb but if the array elements is like
arr = [2 1 0 3]
then this code is not work.
why did you run the loop until arr.size()-1 instead of arr.size()
The question say the test cases will be such that we will reach the end.
please take more example
Steps vs Jumps
Aunty at 1:21 😂
Thanks di
Thanku ❤️❤️
Thanks for the Explanation .
4
2 1 0 3
for this i/p , output is -1 but code is giving 2
i think code will give wrong o/p if for any (a[i]+i) is giving largest index but the value of that index is 0 so our output will be -1
how can we tackle this??
You can assume that you can always reach the last index. ->REad ques carefuly
int farthest=0;
int current=0;
int jumps=0;
for(int i=0;i=n-1) break;
if(current==i){
current=farthest;
jumps++;
}
}
if (n==1) return 0;
//cout
In that case in loop give another if statement that if at any point your farthest is less than i then return -1 .. i.e
If(farthest
we have to run our loop for (
which means
Because n-1 is last element,, we need not to check for that
if possible please teach in Hindi
Kuch samaj nahi aaya