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.
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??
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!
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)
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
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
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
@@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.
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 :)
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!
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.
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!!!
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); }
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.
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..
UNDERSTOOD.........Thank You So Much for this wonderful video......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
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.
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??
clearly understood and was able to code it on my own, thanks a lot bhaiya ❤🔥!
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!
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.
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
I solved it myself , thanbk you so much for building such a strong foundation.
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
"UNDERSTOOD BHAIYA!!"
Love this guy's effort 🤩
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.
striver strives us forward😍😍
Understood ❤ and thanks for explaining runtime error ❤
Asked in my Interview at Nation With Namo
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)
18:50 good issue
understood thank you striver
Thankyou for great solution Striver
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?
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
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]
```
bhaiya please do longest arithmetic subsequence of given difference
Again, Understood! Loving this series.
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
NICE SUPER EXCELLENT MOTIVATED
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
1 Comment Bhaiya You Are Great ☺️
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)
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
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
didn't even have to watch the video...was able to solve it :)
" 10 , come , be my part " :D
Bhai apki videos next level hai
Understood 🙏
You made it look so easy
Thanku bhaiya
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
Thanks Striver. Understood.
Memorization is a technique used in DP
Understood Bhayya
understood thank you so much.
Understood, sir. Thank you very much.
Understood 🎉
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!
10 come be my part , come across and be my part
dont be my part🙄
great content bhai respect for you
Awesome Explanation. Understood!
Understood Sir, Thank you very much
UNDERSTOOD
Thank You Legend for showing us all the possible approaches.
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 :(
Understood 😊
thank you
thanks
UNDERSTOOD ...
understood.
for the algorithm(the youtube one), Understood.
Good one
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);
}
};
*/
18 th Feb
Understood! Thank you so so so much as always!!!
Understood Sir!
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
Understood!
Understood
Great content. Thanks a lot striver.
Understood🌻
UNDERSTOOD
why not take used before ?
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);
}
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.
understood
Understood Sir :)
understood sir🙏🙏
Understood💯💯💯💪💪💪
Understood 😇
understood!
Understood ❤
Understood:)
Understood!!Thank you
understood
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
was able to do it by myself
Understood 😁
As always "understood"❤️
UnderStood💯
understoood
#understood
thanks, test case - [0,1,0,2,3] failing.