73% done …. this is the first time , that i pick a series and consistently practice and learn from it.... u make us doubtless striver.... ur way of explanation is 100x better than any paid courses.... thank god we have striver ....
Able to solve without watching the video. the concepts and basics that you taught so far is now helping me to tackle the problems on my own. Thanks striver!!
Thanks, striver bhaiya !!! Even the DP array of size n*n would work because the f(n,n-1) will never get stored in dp array because the moment index==n the base case would hit
bhaiya you won't believe its been 20 days since i started graph and dp. each day i try to solve alteast 1 question of each topic. i have solved 20 question from each and i haven't reached this question yet but for some placement drive i was just looking for the intuition but as i had already solved the DP on subsequences i was able to build intuition on my within 5 min. in fortunately it is same as yours. thanks a lot for making this A2Z sheet..
instead of taking -1 as prev when there is no previous index, take prev same as index and check with condition (prev == index), this will not give memory exceed error as you will not need the n+1 2d array, just n will be enough.
Thanks, striver for the amazing clarity in explanation. Even though the concept and solution is correct, but it would be helpful to stick to bottom up (memoization) and top down (recursion) approach you had from the very beginning.
The good thing is I was able to crack logic for LIS before this video. Did not know that binary search logic is the optimized approach for LIS! Thanks my intuition for DP problems has become much better than before!
Striver bhaiya you are just our GOD, did till space optimization without watching this video. Cant thank you enough for this brilliant series. Here's the code: class Solution { public: int lengthOfLIS(vector& nums) { int n = nums.size(); // vector dp(n+1,vector(n+1,0)); vector ahead(n+1,0),cur(n+1,0);
for(int ind = n-1;ind>=0;ind--){ for(int prev = ind-1;prev>=-1;prev--){ // int nottake = dp[ind+1][prev+1]; int nottake = ahead[prev+1]; int take =0; if(prev==-1 || nums[ind]>nums[prev]){ // take = 1+dp[ind+1][ind+1]; take = 1+ahead[ind+1]; } // dp[ind][prev+1]=max(nottake,take); cur[prev+1]=max(nottake,take); } ahead=cur; } return ahead[0]; } };
in take case "take = 1+dp[ind+1][ind+1];" why did you write [ind+1][ind+1] in both, acording to the recursive solution isn't it should be dp[ind+1][ind] ?
@@pranavchandrode7127 yes according to recursion it should be that only , but if you carefully observe you'll notice that indexing changes for tabulation and space optimization, striver has even tried to teach us why that change in indexing happens , i don't remember it as of now , did DP 5 months ago , have to revise again
@@anmoljohri9930 Thank you! I think this is because of coordinate shifting , we have shift the coordinate of prev_ind by 1 everytime, so instead of writting dp[i][prev_ind] we have to write dp[i][prev_ind +1]
Hey bro !! could you plz tell why you have taken ( take = 1+dp[ind+1][ind+1]; ) bcz it must be like (// take = 1+dp[ind+1][ind];) could you plz tell the reason??
understood and also thanks for runtime error till know i not sure about "runtime error" ,today i get one ans from you that is occur due to memory execced
We can perform a simple lcs on the given vector and its sorted vector(containing unique elements) and solve this😁 create a new vector push the values in the set and then push the values of set in the new vector (set automatically arranges in increasing order) and then run the lcs code(longest common subsequence)
Can we take prev as element (INT_MIN) instead of index And compare like If( nums[I] > prev) Take = 1 + f(I+1,nums[I]); No take = 0 + f(I+1,prev); Max(take,not); In recursion?
@Dhanesh, see below is the issue u will face according to me if u use prev_value instead of prev_idx @Striver was using f(int idx, int prev_idx) for recursion, when he converted it to memoization array he used dp[idx][prev_idx]. We know that both idx and prev_idx can be till n. So dp array will be of size n*n Your case: Your function becomes f(int idx, int prev_value) for Recursion, when u convert it to memoization array, dp[idx][prev_val]. Now idx can go till n, we cannot guarantee what will be limit for prev_value. If array consists of negative elements then array cannot take negative index, lets say array has 5 very huge elements, then your array will be of 5* huge value instead of 5*5. So using prev_idx is better as we know it will be max array size!
bro map is not right data structure . You should use the unorderd_mpap as the map have insertion,deletion,searching of o(logn) , whereas the unorderd_map have time complexity of o(1) for the operations.
Apart from DP be aware of there exist more optimised solution. nLogN def lengthOfLIS(self, nums: List[int]) -> int: lis = [] for num in nums: pos = bisect.bisect_left(lis,num) if pos == len(lis): lis.append(num) else: lis[pos] = num return len(lis)
vector longestIncreasingSubsequence(std::vector& nums) { std::vector dp; // Longest increasing subsequence for (int i = 0; i < nums.size(); i++) { int x = nums[i]; if (dp.empty() || x > dp.back()) { dp.push_back(x); } else { // Perform a binary search to find the correct position to insert x in dp int left = 0; int right = dp.size() - 1; int index = -1; while (left
@@googlewasmyidea9895 the original array maintains the order of indexes, the second array which has only sorted unique elements make sure it is strictly increasing. the LCS of both these arrays should maintain the indexes and at the same time strictly increasing.
Thanks Striver for the clear explanation of the approach. Can you please help me understand why is the time complexity n*n? We are traversing through the elements only once considering along with the memoization.
No need to create 2D matrix. just 1D def lis(nums): if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return max(dp
your previous is the last index and in the recursion you are increasing the indexes, the logic must be reversed and yeah it is still giving a runtime error :)
look at this base case then you will understand! 1 2 2 if you start from 0th index then the ans is 2 and if you start from the last index the ans is 1.
@@piyushacharya7696 not true thats why we are using pick and not pick we wont pick 2 at last index rather 2 of second last index and then 1 so ans will be 2. You start from start or last doesnt matter anyways.
One more approach that can be used is monotonic stack private static int findLongestIncreasingSequence(int[] arr) { Stack st = new Stack(); for(int i = 0; i < arr.length; i++) { while(!st.isEmpty() && st.peek() < arr[i]){ st.pop(); } st.push(arr[i]); } return st.size(); } Let me know your thoughts/corrections
it is throwing compilation errors, please run your code before posting it somewhere, it wastes our time to understand your approach and figure out what the hell you wanted this code to do
UnderStood. It's Kind of funny that the comments and views get lower as you reach the end of the series. But the comments are always super positive and praising striver!!!
in gfg at test case 111/116 i am getting an error "Abort signal from abort(3) (SIGABRT)" in both memoization and tabulation. can anyone help me with this here's the code int recursion(int i,int prev_ind,int arr[],int n,vector& dp) { if(i == n) { return 0; }
if(dp[i][prev_ind+1] != -1) return dp[i][prev_ind+1]; int pick = 0; if(prev_ind == -1 || arr[i] > arr[prev_ind]) { pick = 1 + recursion(i+1,i,arr,n,dp); } int not_pick = 0 + recursion(i+1,prev_ind,arr,n,dp); return dp[i][prev_ind+1] = max(pick,not_pick); } Tabulation code :- vectordp(n+1,vector(n+1,0)); // since in base case we have to assign 0 therefore we can omit it // and can be taken care during the for loops for(int i = n-1;i>=0;i--) { for(int prev_ind = n-1;prev_ind>=-1;prev_ind--) { int pick = 0; if(prev_ind == -1 || a[i] > a[prev_ind]) { pick = 1 + dp[i+1][i+1]; } int not_pick = 0 + dp[i+1][prev_ind+1]; dp[i][prev_ind+1] = max(pick,not_pick); } } return dp[0][0]; }
you can do that , using binary search concept int ceilIdx(int tail[], int l, int r, int key) { while (r > l) { int m = l + (r - l) / 2; if (tail[m] >= key) r = m; else l = m+1; } return r; } int longestIncreasingSubsequence(int nums[], int n) { int tail[n]; int len =1; tail[0] = nums[0]; for (int i = 1; i < n; i++) { if(nums[i] > tail[len - 1]) { tail[len] = nums[i]; len++; } else { int c = ceilIdx(tail, 0, len - 1, nums[i]); tail[c] =nums[i]; } } return len; }
Other way if you don't want to shift:- #include int f(int i, int prev, int n, int arr[], vector &dp){ // base case if(i==n) return 0; if(prev!=-1 && dp[i][prev] != -1) return dp[i][prev]; int pick = INT_MIN; if(prev==-1 || arr[i]>arr[prev]){ pick = 1 + f(i+1, i, n, arr, dp); }
int notpick = f(i+1, prev, n, arr, dp);
if(prev==-1) return max(pick, notpick); else return dp[i][prev] = max(pick, notpick); } int longestIncreasingSubsequence(int arr[], int n){ vector dp(n, vector(n, -1)); return f(0, -1, n, arr, dp); }
Can anyone help? My intuition to solve this with recursion is lisEndingAtI(idx, next) instead of lisStartingAtI(idx, prev). It works out for 2d array memoization. However i am having problem to create the tabulation formula based on this and hence not able to optimize for space through tabulation. Can someone help me to understand the recurrence from lisEndingAtI with next element selement selected?
Bhaiya what to do in case if nums[I] values range from 10^-4 to 10^4 . if I am declaring dp of n x 10^8 , It is showing memory limit exceeded on leetcode
Can someone explain why this wont work? int lmax(vector &nums,int n,int index,int prev){ if(index==n) return 0; int take; if(prev==-1 || nums[index]>nums[prev]){ take=1+lmax(nums,n,index+1,index); } int nottake=0+lmax(nums,n,index+1,prev); return max(take,nottake); } What is the difference?
I could nt do with a slight variation... What if we are alllowed to swap two of the numbers in the subsequence and then find the longest increasing subseuence? Please suggest.
bhaiya why the base cant be if(ind == n - 1) return 1 but in the coin change problem you take base case at n - 1. I am confused when base will be n - 1 or when it will be n
say the array elements are [2,7,4,5,6] in the take case when you take 2 and 7 ,we will missout the 2,4,5,6 sequence right? can someone help me to get this doubt cleared?
let's say you start with 2 and in one case you took 7 (take 7) then sequence will be 2,7 and if we not take 7 (don't take 7) then sequence will be 2 4 5 6 so we're taking both possibility of including and excluding 7 and returning wether by including 7 we get max length or by excluding it
I used the following approach( but it is giving wrong answer for some test cases) for finding LIS : First I sorted the given array and then i found the Longest common subsequence between the original array and the sorted array. What is wrong with this approach, it is giving wrong answer for some test cases ?
From index=n to index=0 : Accepted on LC : Memo : int f(int i,int next_idx,int n,vector&nums,vector&dp) { if(i==0) return 0; if(dp[i][next_idx]!=-1) return dp[i][next_idx]; int np=f(i-1,next_idx,n,nums,dp); int p=0; if(next_idx==n+1 || nums[i-1]
How can I optimize memory in this: Leetcode problem 334: public boolean increasingTriplet(int[] nums) { Boolean[][][] dp= new Boolean[nums.length+1][nums.length+1][4]; return sub(0,-1,nums,nums.length,dp,3); } public boolean sub(int ind, int prev, int[] nums, int n, Boolean[][][]dp, int count) { if(count==0) return true; if(ind==n) return false; if(dp[ind][prev+1][count]!=null) return dp[ind][prev+1][count]; boolean len1=sub(ind+1, prev,nums,n,dp, count);// nottake case boolean len2=false; if(prev==-1 || nums[ind] > nums[prev]) { // System.out.println(nums[ind]); // System.out.println(count); len2 = sub(ind+1,ind,nums,n,dp,count-1);// take case } return dp[ind][prev+1][count] = len1||len2; }
73% done …. this is the first time , that i pick a series and consistently practice and learn from it.... u make us doubtless striver.... ur way of explanation is 100x better than any paid courses.... thank god we have striver ....
Thank striver, we have God
@@parthsalat what???
@@parthsalat Bhai tunne alag level ka recursion seekh liya hai😂
@@atanunayak6637 😂😂😂😂
@@atanunayak6637 😂😂😂
Able to solve without watching the video. the concepts and basics that you taught so far is now helping me to tackle the problems on my own. Thanks striver!!
The moment you said prev concept trust me striver bhaiya, i somehow was able to understand how to solve this. Thank you man you are a great teacher.
Thanks, striver bhaiya !!!
Even the DP array of size n*n would work because the f(n,n-1) will never get stored in dp array because the moment index==n the base case would hit
Bahut Badhiya sir ji sab samajh aa rha h . Bahut sara pyar is series ke liye
bhaiya you won't believe its been 20 days since i started graph and dp. each day i try to solve alteast 1 question of each topic. i have solved 20 question from each and i haven't reached this question yet but for some placement drive i was just looking for the intuition but as i had already solved the DP on subsequences i was able to build intuition on my within 5 min. in fortunately it is same as yours.
thanks a lot for making this A2Z sheet..
instead of taking -1 as prev when there is no previous index, take prev same as index and check with condition (prev == index), this will not give memory exceed error as you will not need the n+1 2d array, just n will be enough.
Smaller modifications I will leave it on you 😛
@@takeUforward Absolutely Sir, thanks for everything 🙂
@Vinayak Gandhi can u please share the code of your approach, I am not able to implement it. Thank You!
class Solution {
public int lengthOfLIS(int[] nums) {
int[][] dp = new int[nums.length][nums.length];
for (int i = 0; i < nums.length; i++) {
Arrays.fill(dp[i], -1);
}
int[] max = new int[] { 0 };
sol(0, 0, nums, dp, max);
return max[0];
}
private int sol(int ind, int prev, int[] nums, int[][] dp, int[] max) {
if (ind == nums.length) {
return 0;
}
if (dp[ind][prev] != -1) {
return dp[ind][prev];
}
int w = -1;
int wo = -1;
if (ind == prev) {
w = 1 + sol(ind + 1, ind, nums, dp, max);
wo = sol(ind + 1, ind + 1, nums, dp, max);
} else {
if (nums[ind] > nums[prev]) {
w = 1 + sol(ind + 1, ind, nums, dp, max);
}
wo = sol(ind + 1, prev, nums, dp, max);
}
dp[ind][prev] = Math.max(w, wo);
max[0] = Math.max(max[0], dp[ind][prev]);
return dp[ind][prev];
}
}
Actually, we cannot do this in some cases(ex: gfg lis question), because they mention it has to be strictly increasing
UNDERSTOOD.........Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Thanks, striver for the amazing clarity in explanation. Even though the concept and solution is correct, but it would be helpful to stick to bottom up (memoization) and top down (recursion) approach you had from the very beginning.
The good thing is I was able to crack logic for LIS before this video. Did not know that binary search logic is the optimized approach for LIS!
Thanks my intuition for DP problems has become much better than before!
clearly understood and was able to code it on my own, thanks a lot bhaiya ❤🔥!
Striver bhaiya you are just our GOD, did till space optimization without watching this video. Cant thank you enough for this brilliant series.
Here's the code:
class Solution {
public:
int lengthOfLIS(vector& nums) {
int n = nums.size();
// vector dp(n+1,vector(n+1,0));
vector ahead(n+1,0),cur(n+1,0);
for(int ind = n-1;ind>=0;ind--){
for(int prev = ind-1;prev>=-1;prev--){
// int nottake = dp[ind+1][prev+1];
int nottake = ahead[prev+1];
int take =0;
if(prev==-1 || nums[ind]>nums[prev]){
// take = 1+dp[ind+1][ind+1];
take = 1+ahead[ind+1];
}
// dp[ind][prev+1]=max(nottake,take);
cur[prev+1]=max(nottake,take);
}
ahead=cur;
}
return ahead[0];
}
};
in take case "take = 1+dp[ind+1][ind+1];" why did you write [ind+1][ind+1] in both, acording to the recursive solution isn't it should be dp[ind+1][ind] ?
@@pranavchandrode7127 yes according to recursion it should be that only , but if you carefully observe you'll notice that indexing changes for tabulation and space optimization, striver has even tried to teach us why that change in indexing happens , i don't remember it as of now , did DP 5 months ago , have to revise again
@@anmoljohri9930 Thank you!
I think this is because of coordinate shifting , we have shift the coordinate of prev_ind by 1 everytime, so instead of writting dp[i][prev_ind] we have to write dp[i][prev_ind +1]
@@pranavchandrode7127 yes this was it as far as I remember
Hey bro !! could you plz tell why you have taken ( take = 1+dp[ind+1][ind+1]; ) bcz it must be like (// take = 1+dp[ind+1][ind];)
could you plz tell the reason??
understood and also thanks for runtime error till know i not sure about "runtime error" ,today i get one ans from you that is occur due to memory execced
I solved it myself , thanbk you so much for building such a strong foundation.
People who want top-down approach
int fun(int ind,int last,vector &arr){
if(ind==0) return 0;
int len=fun(ind-1,last,arr);
if(last==-1 || arr[ind]
that would be ind < 0.
"UNDERSTOOD BHAIYA!!"
Understood ❤ and thanks for explaining runtime error ❤
We can perform a simple lcs on the given vector and its sorted vector(containing unique elements) and solve this😁
create a new vector push the values in the set and then push the values of set in the new vector (set automatically arranges in increasing order) and then run the lcs code(longest common subsequence)
that seems like a valid approach
Great
@@janardhan2jordan won't work when we have input like 55555 or 22222, output should be 1 but instead it will give length of string
@@Ashutoshc777
public int lengthOfLIS(int[] nums) {
HashSet hs=new HashSet();
for(int i:nums){
hs.add(i);
}
int arr[]=new int[hs.size()];
int idx=0;
for(int i:hs){
arr[idx++]=i;
}
Arrays.sort(arr);
int dp[][]=new int[arr.length+1][nums.length+1];
for(int i=1;i
@@Ashutoshc777 just take remove duplicates and sort it and then apply LCS . It will work
Love this guy's effort 🤩
striver strives us forward😍😍
Thankyou for great solution Striver
Again, Understood! Loving this series.
Asked in my Interview at Nation With Namo
tip : instead of swapping everyone by one just swap -1 with n. like use n inspite of -1 as default idx.
10 come be my part , come across and be my part
dont be my part🙄
Can we take prev as element (INT_MIN) instead of index
And compare like
If( nums[I] > prev)
Take = 1 + f(I+1,nums[I]);
No take = 0 + f(I+1,prev);
Max(take,not);
In recursion?
Initially take as 0
@Dhanesh, see below is the issue u will face according to me if u use prev_value instead of prev_idx
@Striver was using f(int idx, int prev_idx) for recursion, when he converted it to memoization array he used dp[idx][prev_idx]. We know that both idx and prev_idx can be till n. So dp array will be of size n*n
Your case:
Your function becomes f(int idx, int prev_value) for Recursion, when u convert it to memoization array, dp[idx][prev_val]. Now idx can go till n, we cannot guarantee what will be limit for prev_value. If array consists of negative elements then array cannot take negative index, lets say array has 5 very huge elements, then your array will be of 5* huge value instead of 5*5.
So using prev_idx is better as we know it will be max array size!
All approachs Memoization,Tabulation,Space optimization in C++
class Solution {
public:
//simple memoization with prevind shift of 1
// int solve(int ind,vectorarr,int n,int prevind,vector&dp){
// if(ind==n) return 0;
// if(dp[ind][prevind+1]!=-1) return dp[ind][prevind+1];
// int nottake=solve(ind+1,arr,n,prevind,dp);
// int take=INT_MIN;
// if(prevind==-1 or arr[ind]>arr[prevind]){
// take=1+solve(ind+1,arr,n,ind,dp);
// }
// return dp[ind][prevind+1]=max(nottake,take);
// }
// int lengthOfLIS(vector& nums) {
// int n=nums.size();
// vectordp(n,vector(n+1,-1));
// return solve(0,nums,n,-1,dp);
// }
//simple tabulation with prevind shift of 1
// int lengthOfLIS(vector& arr) {
// int n=arr.size();
// vectordp(n+1,vector(n+1,0));
// for(int ind=n-1;ind>=0;ind--){
// for(int prevind=ind-1;prevind>=-1;prevind--){
// int nottake=dp[ind+1][prevind+1];
// int take=0;
// if(prevind==-1 or arr[ind]>arr[prevind]){
// take=1+dp[ind+1][ind+1];
// }
// dp[ind][prevind+1]=max(take,nottake);
// }
// }
// return dp[0][0];
// }
//simple space optimization with prevind shift of 1 and ahead and curr arrays
int lengthOfLIS(vector& arr) {
int n=arr.size();
vectorahead(n+1,0);
for(int ind=n-1;ind>=0;ind--){
vectorcurr(n+1,0);
for(int prevind=ind-1;prevind>=-1;prevind--){
int nottake=ahead[prevind+1];
int take=0;
if(prevind==-1 or arr[ind]>arr[prevind]){
take=1+ahead[ind+1];
}
curr[prevind+1]=max(take,nottake);
}
ahead=curr;
}
return ahead[0];
}
};
its giving tle for map dp ( map mp )
bro map is not right data structure . You should use the unorderd_mpap as the map have insertion,deletion,searching of o(logn) , whereas the unorderd_map have time complexity of o(1) for the operations.
Apart from DP be aware of there exist more optimised solution. nLogN
def lengthOfLIS(self, nums: List[int]) -> int:
lis = []
for num in nums:
pos = bisect.bisect_left(lis,num)
if pos == len(lis):
lis.append(num)
else:
lis[pos] = num
return len(lis)
vector longestIncreasingSubsequence(std::vector& nums) {
std::vector dp; // Longest increasing subsequence
for (int i = 0; i < nums.size(); i++) {
int x = nums[i];
if (dp.empty() || x > dp.back()) {
dp.push_back(x);
} else {
// Perform a binary search to find the correct position to insert x in dp
int left = 0;
int right = dp.size() - 1;
int index = -1;
while (left
we can do this sum in other way sort the given elements and apply lcs with given array and sorted array
good way, but it increases the time complexity for this though so maybe useful for tougher variations
@@your_name96 ig it will not increase the tc
bruh, in subsequence we have to maintain order of indexes. if youll sort it then how could it be a subsequence
@@googlewasmyidea9895 the original array maintains the order of indexes, the second array which has only sorted unique elements make sure it is strictly increasing. the LCS of both these arrays should maintain the indexes and at the same time strictly increasing.
won't work when we have input like 55555 or 22222, output should be 1 but instead it will give length of string
bhaiya please do longest arithmetic subsequence of given difference
18:50 good issue
understood thank you striver
1 Comment Bhaiya You Are Great ☺️
Memorization is a technique used in DP
Understood :)
Was pretty confused why I am getting runtime error, when I was solving it before completing the chapter.
Aug'1, 2023 10:38 pm
didn't even have to watch the video...was able to solve it :)
DP size would be dp[n+1][n+1]; (Just pointing out a small error, Otherwise your content is TOP TIER! BEST CONTENT AVAILABLE OUT THERE)
Why?
I think I have more simpler solution
```
vector lis(n, 1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[j] < nums[i]) {
lis[i] = max(lis[i], lis[j] + 1);
}
}
}
return lis[n-1]
```
Thanks Striver for the clear explanation of the approach. Can you please help me understand why is the time complexity n*n? We are traversing through the elements only once considering along with the memoization.
Same doubt :(
No need to create 2D matrix. just 1D
def lis(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp
NICE SUPER EXCELLENT MOTIVATED
Memoization Solution without taking n+1 .... ie only making dp[n][n].
// Leetcode : Accepted
class Solution {
public:
int f(int ind, int prev_index, vector &dp, vector &arr, int &n)
{
if (ind == n)
return 0;
if (dp[ind][prev_index] != -1)
return dp[ind][prev_index];
int len = f(ind + 1, prev_index, dp, arr, n); // not take
if (prev_index == n-1 || arr[ind] > arr[prev_index])
len = max(len, 1 + f(ind + 1, ind, dp, arr, n)); // take condition
return dp[ind][prev_index] = len;
}
int lengthOfLIS(vector& arr) {
int n = arr.size();
vector dp(n, vector(n , -1));
return f(0, n-1, dp, arr, n);
}
};
your previous is the last index and in the recursion you are increasing the indexes, the logic must be reversed and yeah it is still giving a runtime error :)
@@rahulsaha332 It is not giving me error in leetcode. Copy paste the code in leetcode and please check again
@@rahulsaha332 actually it is giving TLE errror coz of memoization
why we are not using concept that we did earlier, that is starting from back?
i am getting lot of confusions
look at this base case then you will understand!
1 2 2
if you start from 0th index then the ans is 2 and if you start from the last index the ans is 1.
@@piyushacharya7696 not true thats why we are using pick and not pick we wont pick 2 at last index rather 2 of second last index and then 1 so ans will be 2. You start from start or last doesnt matter anyways.
Was able to solve it by myself
at 4:23 , can you share on which videos you have taught it ?
Awesome Explanation. Understood!
Understood, sir. Thank you very much.
One more approach that can be used is monotonic stack
private static int findLongestIncreasingSequence(int[] arr) {
Stack st = new Stack();
for(int i = 0; i < arr.length; i++) {
while(!st.isEmpty() && st.peek() < arr[i]){
st.pop();
}
st.push(arr[i]);
}
return st.size();
}
Let me know your thoughts/corrections
it is throwing compilation errors, please run your code before posting it somewhere, it wastes our time to understand your approach and figure out what the hell you wanted this code to do
Love you striver
Understood! Thank you so so so much as always!!!
Thank You Legend for showing us all the possible approaches.
here first we run not take till if(ind==n) then we run take?
why not take used before ?
Understood Sir, Thank you very much
UnderStood. It's Kind of funny that the comments and views get lower as you reach the end of the series. But the comments are always super positive and praising striver!!!
Mostly because Many folks don't have Recursion grasp , So they won't be able to understand as the series goes forward.
bcz they are able to do it without watching tutorial
You made it look so easy
in gfg at test case 111/116 i am getting an error "Abort signal from abort(3) (SIGABRT)" in both memoization and tabulation.
can anyone help me with this
here's the code
int recursion(int i,int prev_ind,int arr[],int n,vector& dp)
{
if(i == n)
{
return 0;
}
if(dp[i][prev_ind+1] != -1) return dp[i][prev_ind+1];
int pick = 0;
if(prev_ind == -1 || arr[i] > arr[prev_ind])
{
pick = 1 + recursion(i+1,i,arr,n,dp);
}
int not_pick = 0 + recursion(i+1,prev_ind,arr,n,dp);
return dp[i][prev_ind+1] = max(pick,not_pick);
}
Tabulation code :-
vectordp(n+1,vector(n+1,0));
// since in base case we have to assign 0 therefore we can omit it
// and can be taken care during the for loops
for(int i = n-1;i>=0;i--)
{
for(int prev_ind = n-1;prev_ind>=-1;prev_ind--)
{
int pick = 0;
if(prev_ind == -1 || a[i] > a[prev_ind])
{
pick = 1 + dp[i+1][i+1];
}
int not_pick = 0 + dp[i+1][prev_ind+1];
dp[i][prev_ind+1] = max(pick,not_pick);
}
}
return dp[0][0];
}
You are not sending right index i+1, i here i is i+1 not i use another variable
Striver bhai, why you haven't started picking elements from the end of the array?
bro did u got the tabulation solution if we start picking elements from the end
great content bhai respect for you
def lis(array):
def dfs(curr, prev):
if curr == n:
return 0
if (curr, prev) not in memoize:
length = dfs(curr+1, prev)
if prev == None or array[curr] > array[prev]:
length = max(length, 1+dfs(curr+1, curr))
memoize[(curr, prev)] = length
return memoize[(curr, prev)]
n = len(array)
memoize = {}
return dfs(0, None)
Is a 2D dp array necessary? Can't we do it in 1D?
Start from the back and and for any i, dp[i] = LIS from inex 0...i ??
nope beacuse we need the previous index also along with curent index beacuse result changes based on previous element also
you can do that , using binary search concept
int ceilIdx(int tail[], int l, int r, int key)
{
while (r > l)
{
int m = l + (r - l) / 2;
if (tail[m] >= key)
r = m;
else
l = m+1;
}
return r;
}
int longestIncreasingSubsequence(int nums[], int n)
{
int tail[n];
int len =1;
tail[0] = nums[0];
for (int i = 1; i < n; i++)
{
if(nums[i] > tail[len - 1])
{
tail[len] = nums[i];
len++;
}
else
{
int c = ceilIdx(tail, 0, len - 1, nums[i]);
tail[c] =nums[i];
}
}
return len;
}
for the algorithm(the youtube one), Understood.
why we always take the first elemnt there might be a case where without it we get a longer inc subsequence ?
Other way if you don't want to shift:-
#include
int f(int i, int prev, int n, int arr[], vector &dp){
// base case
if(i==n) return 0;
if(prev!=-1 && dp[i][prev] != -1) return dp[i][prev];
int pick = INT_MIN;
if(prev==-1 || arr[i]>arr[prev]){
pick = 1 + f(i+1, i, n, arr, dp);
}
int notpick = f(i+1, prev, n, arr, dp);
if(prev==-1) return max(pick, notpick);
else return dp[i][prev] = max(pick, notpick);
}
int longestIncreasingSubsequence(int arr[], int n){
vector dp(n, vector(n, -1));
return f(0, -1, n, arr, dp);
}
understood thank you so much.
Bhai apki videos next level hai
Hey Striver
A solution of TC(nlogn) and SC O(n) is available at leetcode explore section. Would be great if you can cover that approach as well.
Can anyone help? My intuition to solve this with recursion is lisEndingAtI(idx, next) instead of lisStartingAtI(idx, prev). It works out for 2d array memoization. However i am having problem to create the tabulation formula based on this and hence not able to optimize for space through tabulation. Can someone help me to understand the recurrence from lisEndingAtI with next element selement selected?
Bhaiya what to do in case if nums[I] values range from 10^-4 to 10^4 .
if I am declaring dp of n x 10^8 , It is showing memory limit exceeded on leetcode
For that bs approach in next video
Thanks Striver. Understood.
Why (prev-ind) tho instead of prev only? Cause the previous element should be prev if we don't take right??
Can someone explain why this wont work?
int lmax(vector &nums,int n,int index,int prev){
if(index==n) return 0;
int take;
if(prev==-1 || nums[index]>nums[prev]){
take=1+lmax(nums,n,index+1,index);
}
int nottake=0+lmax(nums,n,index+1,prev);
return max(take,nottake);
}
What is the difference?
u need to initialize take with 0. if( the conditions prev==-1 || nums[index]>nums[prev] are not satisfied it will take a garbage value.
" 10 , come , be my part " :D
Memoization working code:
/*
class Solution {
public:
int Solve(int ind, int prevIndex, vector& nums,
vector& memo) {
if (ind == nums.size())
return 0;
if (memo[ind][prevIndex + 1] != -1)
return memo[ind][prevIndex + 1];
int dontTake = Solve(ind + 1, prevIndex, nums, memo);
int take = 0;
if (prevIndex == -1 || nums[ind] > nums[prevIndex])
take = 1 + Solve(ind + 1, ind, nums, memo);
return memo[ind][prevIndex + 1] = max(take, dontTake);
}
int lengthOfLIS(vector& nums) {
int n = nums.size();
vector memo(n, vector(n + 1, -1));
return Solve(0, -1, nums, memo);
}
};
*/
Guys can someone explain why the time complexity for the memoized soln is O(n^2)?
I could nt do with a slight variation... What if we are alllowed to swap two of the numbers in the subsequence and then find the longest increasing subseuence? Please suggest.
what if values of array are from -10^4 to 10^4 then coordinate shift by 1 wont work how to do that
bhaiya is lecture ke notes site pe available nahi hai
Hey striver
In interview how we decide that the problem is memoized Or not?
By drawing recursion tree...
what is wrong in this code someone explain please :
int f(int n , vector& nums){
if(n == 0){
if(nums[n] < nums[n+1])
return 1;
else
return 0;
}
int notTake = f(n-1 , nums);
int take = -1;
if(n-1 >= 0){
if(nums[n] > nums[n-1])
1 + f(n-1 , nums);
}
return max(take , notTake);
}
bhaiya why the base cant be if(ind == n - 1) return 1 but in the coin change problem you take base case at n - 1. I am confused when base will be n - 1 or when it will be n
In this code the tabulation and space optimization solution is not mentioned...
Maja aa gaya bhaiya explanation is awesome😀😍
Understood 😊
As always "understood"❤️
say the array elements are [2,7,4,5,6]
in the take case
when you take 2 and 7 ,we will missout the 2,4,5,6 sequence right?
can someone help me to get this doubt cleared?
let's say you start with 2 and in one case you took 7 (take 7) then sequence will be 2,7 and if we not take 7 (don't take 7) then sequence will be 2 4 5 6 so we're taking both possibility of including and excluding 7 and returning wether by including 7 we get max length or by excluding it
I used the following approach( but it is giving wrong answer for some test cases) for finding LIS : First I sorted the given array and then i found the Longest common subsequence between the original array and the sorted array. What is wrong with this approach, it is giving wrong answer for some test cases ?
Bcz it will change order in input
Ex. 2 3 1
Lcs=2
If we sort input 1 2 3
Lcs = 3 ehich is wrong
@@chiragmehta2955no your explanation is wrong . The LCS after sorting for your example will still be 2 not 3 .
Understood💯💯💯💪💪💪
From index=n to index=0 :
Accepted on LC :
Memo :
int f(int i,int next_idx,int n,vector&nums,vector&dp)
{
if(i==0)
return 0;
if(dp[i][next_idx]!=-1)
return dp[i][next_idx];
int np=f(i-1,next_idx,n,nums,dp);
int p=0;
if(next_idx==n+1 || nums[i-1]
in memoization why we need to pass i starting values as n and not n-1 and similarly nextIdx as n + 1 instead of n?
@@riyakumari8377 I am assuming index starts with 1 instead of 0 for a string.
For index=1,n-1 becomes n:
For index=0 ,we pass n-1
I hope it helps.
Understood 🙏
Understood 🎉
Understood!!Thank you
Understood Bhayya
How can I optimize memory in this:
Leetcode problem 334:
public boolean increasingTriplet(int[] nums) {
Boolean[][][] dp= new Boolean[nums.length+1][nums.length+1][4];
return sub(0,-1,nums,nums.length,dp,3);
}
public boolean sub(int ind, int prev, int[] nums, int n, Boolean[][][]dp, int count)
{
if(count==0) return true;
if(ind==n) return false;
if(dp[ind][prev+1][count]!=null) return dp[ind][prev+1][count];
boolean len1=sub(ind+1, prev,nums,n,dp, count);// nottake case
boolean len2=false;
if(prev==-1 || nums[ind] > nums[prev])
{
// System.out.println(nums[ind]);
// System.out.println(count);
len2 = sub(ind+1,ind,nums,n,dp,count-1);// take case
}
return dp[ind][prev+1][count] = len1||len2;
}
Great content. Thanks a lot striver.
understood sir🙏🙏
Can we tabulise it, I am not able to tabulise it