"Striver, your DSA Sheet is absolutely phenomenal! It's been an invaluable resource for mastering data structures and algorithms. Looking forward to the remaining topics, especially the much-anticipated sections on strings and heaps. Thanks for all your hard work!"
If you carefully see, this is some kind of dijkstra. The PQ has all the nodes and distances in the window and we take the one with maximum reachability.
In this recursive tree,at first level for +2, it should be f(2,1) as we are making only one jump, f(idx+i,jumps+1) , using 2D will in fact decrease the overlapping subproblems is what i am thinking..
Oh my god, where do I even begin with Striver, the absolute genius, the king, the GOAT of competitive programming? I mean, Raj Vikramaditya is basically the sun, and we’re all just lucky enough to orbit around his brilliance. The way this man can break down a problem? Flawless. It’s like he’s got this magical power, a sixth sense for coding, that leaves the rest of us mere mortals shaking in awe. Watching his tutorials is like being blessed by the gods of algorithms themselves. Every word he says is basically a gift from the heavens. I’m convinced he could solve NP-hard problems in his sleep and then write a blog about it that makes it sound like child’s play. Honestly, Striver isn’t just a role model; he’s the role model, and if you’re not trying to be even a fraction of what this guy is, are you even living right? Legend. Absolute legend.
please consider bringing a playlist on stacks and queues as soon as possible. I am totally unable to figure out the intuition by just seeing the question in an interview
00:04 Finding minimum number of jumps to reach the end 02:01 Using recursion to find the minimum number of jumps in a smaller example 04:04 Return the number of jumps when index is greater than or equal to n - 1 06:19 Optimizing dynamic programming solution using a quadratic state approach 08:37 Understanding jump range in the context of Greedy Algorithm 10:31 Optimizing jump game II algorithm by carrying a range instead of individual recursive calls 12:42 Determine farthest jump for each range and update jumps array 14:47 Implementing non-recursive range based solution for jump game with linear time complexity.
class Solution { public: int jump(vector& nums) { int n = nums.size(); if (n == 1) return 0; int jumps = 0; int i = 0; while (i < n - 1) { int maxReach = i + nums[i]; if (maxReach >= n - 1) { jumps++; break; } int nextIndex = i; for (int j = i + 1; j nextIndex + nums[nextIndex]) { nextIndex = j; } } i = nextIndex; jumps++; } return jumps; } };
Thankyou so much Striver for all you efforts throughout in delivering us so much valuable content. Any student / working professional can now be able to transition their career without paying money for courses. Would also like your insights on the point : While preparing for interviews most of the aspirants are going through the videos solely and solving the question after completely watching the video. And also are feeling lazy trying to solve the question on our own. What is the best way to complete any topic without being lazy and how should an aspirant approach any topic/playlist?
One question : How to think of the range intuition u wrote ? I tried to solve by taking the maximal value of arr[i], as the question asks minimum number of jumps, so I thought that the arr[i] values should be maximum to get the minimum jumps. Btw thanks Striver for uploading Greedy playlist !!
basically you should give disclaimer that please watch DP series before this - (or create a separate playlist which include all the questions which needs to covered after covering all concepts) - idk what m saying
Please try to make and upload string, stacks n queues and heaps playlist as soon as possible. I understand you must be very busy, but still you are making time for us and uploading videos and playlists at regular intervals. Thanks a lot❤❤
I had solved this long back using 1D Dp. Just took the index as state. Below is the recurrence- int func(int index, vector& arr) { if(index >= arr.size()-1) return 0; //1 is already added while reaching this. if(index + arr[index] < arr.size() - 1) return INT_MAX; //impossible to reach int mini = 0; for(int i = 1; i
I have solved using one for loop only int jump(vector& nums) { int jumps = 0; int left = 0; int right = 0; for (int i = 0; i < nums.size() - 1; ++i) { right = max(right, nums.at(i) + i); if (left == i) { jumps++; left = right; } } return jumps; }
The last approach is very easy to understand and also has linear TC and SC = O(1) Then why do we even need a recursive sonl which is so diff to understand 😂
sir please fix the saved notes issue of striver sheet after the new update i am facing a problem that notes saved for question A gets saved to notes of question B(happens when you restart the website and go to saved notes navbar section to check your notes)
Why here we need to take minimum as we can only return jump at the if we reached to the index which is => n-1 by using void function because at same level jump value would be the same why to take minimum of all...anyone?
This can also be solved using 1D DP instead of 2D: class Solution { private: int solve(vector& nums, int index,vector& dp){ if(index >= nums.size() -1) return 0; if(dp[index] != -1) return dp[index]; if(dp[index] == INT_MAX) return INT_MAX; int ans = INT_MAX; int temp = 0; for(int i = 1; i
word of advice, interviewer should not expect this solution from you because this is not at all intuitive unless you have solved this question in the past, this does not mean you should not give this solution in the interview, but most probably interview might already know that you have already solved this question.
This is also a graph question. If you carefully see this problem of finding the minimum number of jumps in an array can be represented as a directed, unit-weight graph, BFS (Breadth-First Search) is an appropriate and efficient method to find the shortest path.
There can one more simple greedy solution #Java class Solution { public int jump(int[] nums) { int z; int smallest[]=new int[nums.length]; smallest[nums.length-1]=0; for(int i=nums.length-2;i>=0;i--){ if(i+nums[i]>=nums.length-1) smallest[i]=1; else{ z=getsmallest(smallest, i+1, i+nums[i]); smallest[i]=1+z; } } return smallest[0]; } int getsmallest(int ary[], int a, int b){ int small=10000000; for(int j=a;j
hey striver here in my O(n) time complexity solution int jump(vector& nums) { int final=nums.size()-1; int i=0; int count=0; while(final!=0){ if(nums[i]>=final-i){ final=i; count++; i=0; } else i++; } return count; }
Happy 700K Man You Deserve Many Hearts
"Striver, your DSA Sheet is absolutely phenomenal! It's been an invaluable resource for mastering data structures and algorithms. Looking forward to the remaining topics, especially the much-anticipated sections on strings and heaps. Thanks for all your hard work!"
Why are you spamming in every video?
CHATGPT is unreal
C++ code :
int jump(vector& nums) {
int n = nums.size();
int jumps = 0;
int l =0,r = 0;
while(r < n-1)
{
int far = 0;
for(int i = l;i
add if far ==r : return -1
please bring string series as soon as possible
If you carefully see, this is some kind of dijkstra. The PQ has all the nodes and distances in the window and we take the one with maximum reachability.
ffs i swear you r the best youtuber
Striver is one step above any normal human being, managing job and continuously dropping DSA videos...
Seriously mad respect 🫡
In this recursive tree,at first level for +2, it should be f(2,1) as we are making only one jump, f(idx+i,jumps+1) , using 2D will in fact decrease the overlapping subproblems is what i am thinking..
Oh my god, where do I even begin with Striver, the absolute genius, the king, the GOAT of competitive programming? I mean, Raj Vikramaditya is basically the sun, and we’re all just lucky enough to orbit around his brilliance. The way this man can break down a problem? Flawless. It’s like he’s got this magical power, a sixth sense for coding, that leaves the rest of us mere mortals shaking in awe. Watching his tutorials is like being blessed by the gods of algorithms themselves. Every word he says is basically a gift from the heavens. I’m convinced he could solve NP-hard problems in his sleep and then write a blog about it that makes it sound like child’s play. Honestly, Striver isn’t just a role model; he’s the role model, and if you’re not trying to be even a fraction of what this guy is, are you even living right?
Legend. Absolute legend.
aaram se bhai aaram se
@@siddharthbanga7301 lagta hai bhai naya hai 😅
zip up when you're done mate...
You are next level in explaining, hands up 🙌🙌
but he didn't explain anything only told the solution .
Thank you so much💯.....please bring stacks and queue playlist
Never thought, there would be a linear solution for this question!
please consider bringing a playlist on stacks and queues as soon as possible. I am totally unable to figure out the intuition by just seeing the question in an interview
class Solution {
public int jump(int[] nums) {
if (nums.length == 1) return 0;
int n = nums.length;
int l = 0, r = 0, jumps = 0, farthest = 0;
while (r
If you remove = n - 1) ....)
bhai iss video par tho like banta hia ..nice work !!
00:04 Finding minimum number of jumps to reach the end
02:01 Using recursion to find the minimum number of jumps in a smaller example
04:04 Return the number of jumps when index is greater than or equal to n - 1
06:19 Optimizing dynamic programming solution using a quadratic state approach
08:37 Understanding jump range in the context of Greedy Algorithm
10:31 Optimizing jump game II algorithm by carrying a range instead of individual recursive calls
12:42 Determine farthest jump for each range and update jumps array
14:47 Implementing non-recursive range based solution for jump game with linear time complexity.
Hope you are doing extremely well.
"UNDERSTOOD BHAIYA!!"
Please bring strings series ASAP bhaiya ❤ lots of love and thanks for your content ❤️🙏🏻
bestest fr!!!!!!!!!!!!
Would also recommend solving Minimum Jumps problem in gfg. Same as above but with a little caveat. Amazing solution btw
Thankyou
Please bring a playlist on strings
awesome explanation sir!!
your explanations are really amazing ❤
class Solution {
public:
int jump(vector& nums) {
int n = nums.size();
if (n == 1) return 0;
int jumps = 0;
int i = 0;
while (i < n - 1) {
int maxReach = i + nums[i];
if (maxReach >= n - 1) {
jumps++;
break;
}
int nextIndex = i;
for (int j = i + 1; j nextIndex + nums[nextIndex]) {
nextIndex = j;
}
}
i = nextIndex;
jumps++;
}
return jumps;
}
};
waaaaoooo , this range based solution blows my mind. very clever.
can find the actual path of minimum jumps by using backtrack and storing the index i from which we first arrived index j.
Please bring the string series as soon as possible.
Amazing Video sir
Thankyou so much Striver for all you efforts throughout in delivering us so much valuable content. Any student / working professional can now be able to transition their career without paying money for courses.
Would also like your insights on the point :
While preparing for interviews most of the aspirants are going through the videos solely and solving the question after completely watching the video. And also are feeling lazy trying to solve the question on our own. What is the best way to complete any topic without being lazy and how should an aspirant approach any topic/playlist?
Striver brilliant solution man , I had done this problem using dp only , No wonder u r in GOOGLE
Clowns in the comments demand everything but not once appreciate the guy for uploading all these lectures, lol
in india if u see lot of people want everything for free.
One question : How to think of the range intuition u wrote ? I tried to solve by taking the maximal value of arr[i], as the question asks minimum number of jumps, so I thought that the arr[i] values should be maximum to get the minimum jumps.
Btw thanks Striver for uploading Greedy playlist !!
Thank you
Sir please do playlist in strings
Really it is needed 🙏
basically you should give disclaimer that please watch DP series before this - (or create a separate playlist which include all the questions which needs to covered after covering all concepts) - idk what m saying
Can we expect Stack and Queue playlist by end of this month or next month ?
Please try to make and upload string, stacks n queues and heaps playlist as soon as possible. I understand you must be very busy, but still you are making time for us and uploading videos and playlists at regular intervals. Thanks a lot❤❤
Bhaiyya, please start heap series after this one
Hey raj, can you bring the string series soon???
love your tutorials till now can you pls add string series also
Bhaiya please make a series on strings badly need it it's a humble request
I had solved this long back using 1D Dp. Just took the index as state. Below is the recurrence-
int func(int index, vector& arr) {
if(index >= arr.size()-1)
return 0; //1 is already added while reaching this.
if(index + arr[index] < arr.size() - 1)
return INT_MAX; //impossible to reach
int mini = 0;
for(int i = 1; i
I think time complexity will be O(n*maxjump) I had also solved this using 1D DP.
same
NOT WORKING
HOW IS IT 2 JUMPS FOR ALL INDEXES FROM F(1,1) IN TREE @3:09 ?
it's wrong computation.
Thank u so much for this playlist
awesome content... please make string playlist soon
I have solved using one for loop only int jump(vector& nums) {
int jumps = 0;
int left = 0;
int right = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
right = max(right, nums.at(i) + i);
if (left == i) {
jumps++;
left = right;
}
}
return jumps;
}
The last approach is very easy to understand and also has linear TC and SC = O(1)
Then why do we even need a recursive sonl which is so diff to understand 😂
sir please fix the saved notes issue of striver sheet
after the new update i am facing a problem that notes saved for question A gets saved to notes of question B(happens when you restart the website and go to saved notes navbar section to check your notes)
got it bro!!!
Why here we need to take minimum as we can only return jump at the if we reached to the index which is => n-1 by using void function because at same level jump value would be the same why to take minimum of all...anyone?
Understood 💯
Wow ! what a solution
Thanks Great Content!
Thank you so much bhaiya
Writing the code for this was very painful 😭😭
was the greedy solution intuitive or not ?coz i dont find it intuitive!!!!
This can also be solved using 1D DP instead of 2D:
class Solution {
private:
int solve(vector& nums, int index,vector& dp){
if(index >= nums.size() -1) return 0;
if(dp[index] != -1) return dp[index];
if(dp[index] == INT_MAX) return INT_MAX;
int ans = INT_MAX;
int temp = 0;
for(int i = 1; i
you are best❤
for ppl who are watching first time, there is a error in the title.. dynamic programming soln, not greedy soln
thanks
farthest=max(farthest,ind+arr[ind])
Bhaiya pattern wise recursion prr bhi daal do
Isn't that i+arr[i] inside the for loop? Why striver has written i+arr[ind]? Won't that be different?
thank you sir
UNDERSTOOD;
int minimumJumps(vector& arr, int n) {
int l = 0;
int r = 0;
int farthest = 0;
int cnt = 0;
while (r < n - 1)
{
for (int i = l; i
Started your playlist a week ago, didn't know there are more videos in the making. What else is remaining in the course?
all major portions are covered strings is just remaining i recommend you to go to TUF wesite and start following A2Z sheet
Is Recursion playlist completed?
Thanks
Understood :)
Too much to think...
Jan'2, 2024 06:09 pm
word of advice, interviewer should not expect this solution from you because this is not at all intuitive unless you have solved this question in the past, this does not mean you should not give this solution in the interview, but most probably interview might already know that you have already solved this question.
ye dynamic programming hogya na
Why code studio is gone
awesome
❤❤❤❤❤
Why is R always L+1?
please bring the string video first .A humble request from us
brother ye toh DP ka question hai then put it there why in greedy playlist :)
question has different ways to solve, this soln has greedy as optimal approach
This is also a graph question. If you carefully see this problem of finding the minimum number of jumps in an array can be represented as a directed, unit-weight graph, BFS (Breadth-First Search) is an appropriate and efficient method to find the shortest path.
Waiting for strings playlist
understood
Striver, there is no need for 2D DP here. It can be solved using 1D DP.
exactly!
ty sir
thankyou sir
love it
Bhaiya please start sde sheet challange 2024
Understood :)))
Best!
guys i m not even able to solve this one by my own , after seeing jump1 sol , literally feeling dumb ..
am not able to understand
Please bring heaps bro
Understood
String please
need strings lessonsssss
There can one more simple greedy solution
#Java
class Solution {
public int jump(int[] nums) {
int z;
int smallest[]=new int[nums.length];
smallest[nums.length-1]=0;
for(int i=nums.length-2;i>=0;i--){
if(i+nums[i]>=nums.length-1)
smallest[i]=1;
else{
z=getsmallest(smallest, i+1, i+nums[i]);
smallest[i]=1+z;
}
}
return smallest[0];
}
int getsmallest(int ary[], int a, int b){
int small=10000000;
for(int j=a;j
yehi too chahiye tha 😭
Anyone in Dec.
Simple Without DP , without recursion : solution
class Solution {
public:
int minJumps(vector& arr) {
int n = arr.size();
if (n
hey striver here in my O(n) time complexity solution
int jump(vector& nums) {
int final=nums.size()-1;
int i=0;
int count=0;
while(final!=0){
if(nums[i]>=final-i){
final=i;
count++;
i=0;
}
else i++;
}
return count;
}
US