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
"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!"
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
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?
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 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; }
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)
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; }
the dp solution is 1d why use 2d:class Solution { public: int solve(vector& nums,int id,vector& dp){ if(id>=nums.size()-1)return 0; if(dp[id]!=-1)return dp[id]; int reach=id+nums[id]; int n=nums.size(); int mini=1e9; for(int k=id+1;k
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
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.
please bring string series as soon as possible
Please bring strings series ASAP bhaiya ❤ lots of love and thanks for your content ❤️🙏🏻
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
"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?
Hope you are doing extremely well.
Thank you so much💯.....please bring stacks and queue playlist
Please bring the string series as soon as possible.
Thankyou
Please bring a playlist on strings
Thank u so much for this playlist
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
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?
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.
awesome content... please make string playlist soon
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❤❤
Never thought, there would be a linear solution for this question!
love your tutorials till now can you pls add string series also
Thanks Great Content!
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;
}
Would also recommend solving Minimum Jumps problem in gfg. Same as above but with a little caveat. Amazing solution btw
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) ....)
you are best❤
Sir please do playlist in strings
Really it is needed 🙏
Can we expect Stack and Queue playlist by end of this month or next month ?
Understood 💯
Wow ! what a solution
thankyou sir
Bhaiya please make a series on strings badly need it it's a humble request
love it
awesome
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)
Hey raj, can you bring the string series soon???
Bhaiyya, please start heap series after this one
Striver brilliant solution man , I had done this problem using dp only , No wonder u r in GOOGLE
Best!
ty sir
Understood
Bhaiya pattern wise recursion prr bhi daal do
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;
}
String please
please bring the string video first .A humble request from us
Why code studio is gone
Isn't that i+arr[i] inside the for loop? Why striver has written i+arr[ind]? Won't that be different?
Bhaiya please start sde sheet challange 2024
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
Waiting for strings playlist
HOW IS IT 2 JUMPS FOR ALL INDEXES FROM F(1,1) IN TREE @3:09 ?
it's wrong computation.
was the greedy solution intuitive or not ?coz i dont find it intuitive!!!!
yehi too chahiye tha 😭
US
Striver, there is no need for 2D DP here. It can be solved using 1D DP.
the dp solution is 1d why use 2d:class Solution {
public:
int solve(vector& nums,int id,vector& dp){
if(id>=nums.size()-1)return 0;
if(dp[id]!=-1)return dp[id];
int reach=id+nums[id];
int n=nums.size();
int mini=1e9;
for(int k=id+1;k
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
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
Data Structures & Algorithm ❌
Data STRIVERS & Algorithm ✅
bro, why is your voice very low in this greedy series, can't here u properly
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.