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
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
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.
@@adityatiwari8930 Tumne misunderstand kar diya comment ko. @lakshyasharma1940 ka matlab hai ki itne ache solution ka rating kaafi kam hai youtube par.
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?????????/
Mam mere last round ke interview me ye question poochha tha (6lpa) Maine iska response dp se diya tha greedy approach dimaag me hit nhi hui interviewer bol rha tha optimal kro but uss time ye approach hit nhi hui but koi nhi i learned now
@@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.
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
To anyone whose leetcode test cases are failing with the code provided in the video here is the corrected code : class Solution { public int jump(int[] nums) { if(nums.length == 1) { return 0; } int current = 0; int jumps = 0; int farthest = 0; for(int i = 0; i < nums.length; i++) { farthest = Math.max(farthest, i + nums[i]); if(i == current && i != nums.length - 1) { current = farthest; ++jumps; } } return jumps; } }
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.
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 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
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??
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
Life would have been easy if greedy had easy proofs: Nice explanation though !!
Got deviated with the hillarious sneaky movement behind 🤣🤣🤣🤣🤣. Great Explanation
was wondering if no one else saw it
@@kolawoleabdulrahman I see 😂😂
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
Honestly the way u explained i subscried your channel😁 took more than 5 video to understand this logic Thanks
Honestly mam appka samghane ka tarika ekdam nique hai thanku mam
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
Thanks for easy and nice explanation 😊
1:21 someone sneaked into your room :P
Concept is Crystal clear, thanks
haha that's my mom trying to not make noise :)
Salute to your dedication🙏🙏
Good explaination
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.
Thanks a lot for such a great explanation!! Keep posting more video on Leetcode daily challenge.
Easiest and best solution among all
very good solution. good explanation
Aunty was so cute, tried her best not be in the frame. Thanks for awsome explanation.
The intuition of problem at 6.20 .. great!!!!
This is is the best solution for me.
Thanks mam, It took me 1 day to solve
Nice Explanation
I understand the solutin after 3 to 4 dry run.
thanks mam,you cleared my doubts ,i was struggling with this question
thanks di your explanation was superb
Thanks - for easy explanation...
we have to break the loop if current reaches the last index , else one extra jump will be added!
literally good explanation
Nice explanation . Thanks👍
Nice explanation, do upload more such videos..
1:20 your mother hiding herself from camera 😁😁
beautiful explanation
crystal clear concept thank u :)
finally a video with good explanation..
Am i the only guy for whom the code is not working?
no, it doesn't pass for me
pretty good explanation
Thanks nicely explained
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.
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
U got my subscribe❤
Really really good ...please increase example numbers ...like if any edge cases are there and some tips
just a correction u have not added condition if i > current: return -1 , which is one of the edge case..
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?????????/
Very nice explanation mam. Thank you
Mam mere last round ke interview me ye question poochha tha (6lpa)
Maine iska response dp se diya tha greedy approach dimaag me hit nhi hui interviewer bol rha tha optimal kro but uss time ye approach hit nhi hui but koi nhi i learned now
Thanks for the explanation. But this is failing on 44th test case in Leetcode: [1,2,3].
really good explained
Nice One
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.
mashallaha mashallah solution Thanks!
really helpful😊
easiest approach 💙💙
thanks a lot for such a great explanation
The one condition is not their that is if(i >= furthest) {return -1 } bz we cannot move forward.
such a great explanation, thanksss!
why size-1?
lol got it we dont want to go anywhere from last index
I==current means????
why do u go till
my thoughts too
why dp is not working here
Well explained!!, :)
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.
IIB respect 🙇♀
Her video should be on the top of the search results. Really great explanation.
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
nice
why do we iterate only until the second last index ?can you explain this?
Yea
To anyone whose leetcode test cases are failing with the code provided in the video here is the corrected code :
class Solution {
public int jump(int[] nums) {
if(nums.length == 1) {
return 0;
}
int current = 0;
int jumps = 0;
int farthest = 0;
for(int i = 0; i < nums.length; i++) {
farthest = Math.max(farthest, i + nums[i]);
if(i == current && i != nums.length - 1) {
current = farthest;
++jumps;
}
}
return jumps;
}
}
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.
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.
just amazing
Thanks
[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
mummy rocks!!!!!!
Eagaely I am waiting for you ❤️❤️
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
1:22 peeche dekho peeche 😂
why did you run the loop until arr.size()-1 instead of arr.size()
please take more example
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.
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
Thanks di
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.
Steps vs Jumps
if possible please teach in Hindi
if the curr becomes >= lastIndex, we can break from the for loop, then there will be fewer number of iterations. a little more optimized.
Kuch samaj nahi aaya
Aunty at 1:21 😂