Sir in amazon online interview, is it like leetcode where we have to complete a given function only, or we have to do all the input/output, construct trees/graphs etc. also ?
in java it returns the index of the search key, if it is contained in the array. otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key. int pos=Collections.binarySearch(temp,arr[i]); if(pos
thank you ! the intuition was very helpful. for anyone looking to generate the actual sequence you can't do it using binary search. You would need a segment tree !
You know what , I just paused at this timestamp and came into the comment section to find whether i was the only one who spotted the mistake and found your comment.
I struggled badly when I was doing it myself and worried why I am able to apply dp. But I when I started watching his video, I realised the problem is indeed difficult. Hats off to Striver for the way he explains the approach!
the explanation is soooooooooooo goood, im really enjoying your dp series. i understand everything easily and enjoy it a lot. u make learning these concepts so easy to remember. thanks a lot
i don't know why ppl leave videos like this wdout giving a like. there are currently 8k+ views and only around 400 likes. btw awesome content !!!!!!!!!thanks
Java Solution: static int longestSubsequence(int size, int arr[]) { // using binary search ArrayList ans = new ArrayList(); ans.add(arr[0]); int len = 1; for (int i = 1; i < size; i++) { if (arr[i] > ans.get(ans.size() - 1)) { ans.add(arr[i]); len++; } else { int indx = binarySearch(ans, arr[i]); ans.set(indx, arr[i]); } } return len; } static int binarySearch(ArrayList ans, int key) { int low = 0; int high = ans.size() - 1; while (low
For all the java peeps out there Use this function instead of lower bound static int ceil(int key, List lst){ int low = 0 , lst = lst.size() - 1; int ans = -1; while(low
Awesome video by Striver as always!!! Java also has ceiling methods for TreeSet, TreeMap. Because we are inserting in such a way sequence is kept increasing even after deletion and reinsertion, below will get accepted as well: public static int longestIncreasingSubsequence(int arr[]) { //Your code goes here TreeSet myset = new TreeSet(); myset.add( arr[0] ); for( int i = 0; i < arr.length; i++ ){ if( arr[i] > myset.last() ){ myset.add( arr[i] ); } else { //Map.Entry entry = myset.ceilingEntry( arr[i] ); Integer ceilValue = myset.ceiling( arr[i] ); if( ceilValue != arr[i] ){ myset.remove( ceilValue ); myset.add( arr[i] ); } } } return myset.size(); }
so sorry for my words but this optimization is so fucking good. Seriously, so many approches for a single question damm. honestly sir if u want u can just give the best approch and finish it but u r taking us step by step and make us undersatnd the actuall concepts. i m following ur playlist from the starting but after this question not able to stop myself from getting jump into the cmnt box. Really thank u sir for such a best ever playlist.
another O(nlogn) approach, kind of intuitive: Note: first do the space optimization using only one array (only *dp* and not *dp* with *cur* ) and analyze how the table is getting filled. make a duplicate array of pair {nums[i],i} and sort them. Lets name this array arr2. Now, the dp table is filled with "i" going n -> 0 as dp(prev) = max( dp(prev), 1+dp(i)) which essentially means that any number less than number at current index "i" will take its max i.e. { arr[i] > arr[prev] } and { i > prev } are the two conditions and then we can do dp[prev] = max(dp[prev], 1+dp[i]). thus we find the lower_bound of the current element arr[i] in arr2 and since arr2 is sorted, we go to all elements to left side of the lower_bound of arr[i]. as arr2 has size n and we are finding each arr[i] using binary search, this makes the complexity O(nlogn). Sorting also takes O(nlogn) so overall it works in O(nlogn).
The intuition behind the binary search lies in the fact that we replace considerably bigger elements with smaller ones with the possibility that there are high chances that smaller elements will be smaller than upcoming bigger elements thereby forming LIS as compared to relatively existing bigger elements having possibility of being smaller than upcoming new elements meanwhile also maintaining max LIS list length up to some index i.
@@gauravtiwary1839 i've been programming for 4 years and i didn't knew that the size function has 0(1) TC. can you please share the algo for size function. I can understand what if a vector is already initialised for ex: vectorvec={1,2,3,4,5,6,7,8,9}; is vec.size(); 0(1)tc here also?
The concept of array could also be understood in this manner: Basically the ith element of temp array means that the longest increasing subsequence whose greatest element is temp[i] has a length of i+1. In the Algorithm what we are basically doing is that we are replacing the current element with it's best place in temp vector. By best place I mean that the place at which current element is the greatest element in the longest increasing subsequence. Let the index of that best place be ind(0 based indexing). Then ind+1 is the length of the longest increasing subsequence whose greatest element is the current element.
Just a small correction: lower_bound() gives index of first element which is greater than or equal to the target element. For getting index of 1st element, strictly greater than target element, we need upper_bound(). Anyway, great video as ever 🔥
DP Revision : Uff bhai, how can I even forget this solution ;-; Had to watch the previous two videos too, to get to the O(N) solution ;-; Nov'20, 2023 03:30 pm (Happy Birthday to me... ;))
Firstly a lots of thanks for delivering such an amazing content in an understandable way.... But one doubt...how does such intuition strikes to anyone while solving such questions...coz if this intuition strikes to anyone then it means that he is as equal as...a researcher/expert who has already developed such an algorithm for this question....
DOUBT If for arr={1,7,8,4,5,6,-1,9} say we are at i = 4, arr[i] = 5 and our temp is {1,4,8}..Now for comparing 5 in temp when we use lower_bound the range is [first, last) last not included..So isn't the comparison from temp.begin() to temp.end()-1? Since last is not included in the range.
thanks for your video. But have a doubt @11:06...If we are replacing items , what will be the output for 1,4,4,5,5,6,6,7]? Based on algorithm which you explained it will be 5 [1,4,5,6,7].. But i think actual output will be 8 ..
At first I thought that the number will be added to the result directly if(arr[i] > arr[i - 1]), but later understood that it will only add the number directly to the result if(result.get(result.size() - 1) < arr[i]). List res = new ArrayList(); for (int n : nums) { if (res.isEmpty() || res.get(res.size() - 1) < n) { res.add(n); } else { int index = binarySearch(res, n); res.set(index, n); } } return res.size();
What if the question was modified a bit and asking for non decreasing sub sequence instead of strictly increasing sub sequence, then in that case we cannot simply replace elements in the list right? So do we just insert these elements into the list? Or create a list of pair and if we have a duplicate we just increment count?
If I want to print the subsequence then how I can do this, the subsequence is changing and we are inserting the new element into a vector which is actually not a subsequence. I got the approach for finding but if i have to print it then ?
You can save in the same array as well. Java code : import java.util.*; public class Solution { public static int longestIncreasingSubsequence(int arr[]) { //Your code goes here int ptr = 0; int idx = 1; int n = arr.length; while(idx < n) { if( arr[idx] > arr[ptr] ) { arr[++ptr] = arr[idx]; } else { arr[bs(arr, arr[idx], ptr)] = arr[idx]; } idx++; } return ptr+1; } public static int bs(int[] arr, int tar, int idx) { int left = 0; int right = idx; int mid = 0; while( left < right ) { mid = left + (right-left)/2; if( arr[mid] == tar ) { return mid; } else if( arr[mid] >tar ){ right = mid; } else { left = mid+1; } } return left; } }
int lengthOfLIS(vector& nums) { // Using Binery Search with the help of lower_bound int n=nums.size(); int len=1; for(int i=1;inums[len-1]){
len++; swap(nums[len-1],nums[i]); }else{ int ind=lower_bound(nums.begin(),nums.begin()+len,nums[i])-nums.begin(); nums[ind]=nums[i]; } } return len; } //I tried to solve using only given nums
int lengthOfLIS(vector& nums) { int n = nums.size(); vector temp; int lenn=1; temp.push_back((nums[0]); for(int i =1;itemp.back()){ temp.push_back(nums[i]); lenn++; }else{ int ind = lower_bound(temp.begin(),temp.end(),nums[i])-temp.begin(); temp[ind]=nums[i]; } } return lenn; }
It's good that he has mentioned that this method is useful for finding only the length of the longest increasing subsequence, instead of the subsequence itself. For finding the longest increasing subsequence , you can refer to lecture 42 (hash method)).
let me know in the comments, if this blew your mind or not :P
Sir in amazon online interview, is it like leetcode where we have to complete a given function only, or we have to do all the input/output, construct trees/graphs etc. also ?
Mind blowing bhaiya
My mind flew away and now I am chasing it 😌🥴
lower_bound returns an iterator. How your code compiled by returning an index?
@@KapilKumar-ig6df he has subtracted the starting pt of the vector that will give you the index.
Dude you were the only one who could explain why this worked!! loved it!!
in java it returns the index of the search key, if it is contained in the array. otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key.
int pos=Collections.binarySearch(temp,arr[i]);
if(pos
This has been the most succinct explanation that I could find on UA-cam. Thank you so much for your dedication.
thanks for giving the intutution behind, really makes the solution more meaningful, rather than feeling like we just gotta cram it
Perfect explanation of the intuition behind this solution.
Nice work! 👍👍
thank you ! the intuition was very helpful. for anyone looking to generate the actual sequence you can't do it using binary search. You would need a segment tree !
At 11:15 the 2 will come after 1,even though nothing will change,just reminding.
You know what , I just paused at this timestamp and came into the comment section to find whether i was the only one who spotted the mistake and found your comment.
@@aeroabrar_31 +1 mate
i think 4 after that 1 has to be changed
I struggled badly when I was doing it myself and worried why I am able to apply dp. But I when I started watching his video, I realised the problem is indeed difficult.
Hats off to Striver for the way he explains the approach!
i feel this approach in not at all intuitive but thanks for the explanation bhaiya:)
UNDERSTOOD............Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
the explanation is soooooooooooo goood, im really enjoying your dp series. i understand everything easily and enjoy it a lot. u make learning these concepts so easy to remember. thanks a lot
Striver, trust me you have insane explanation skills.
code:
int lengthOfLIS(vector& nums) {
vector temp;
temp.push_back(nums[0]);
for(int i(0);i temp.back()){
temp.push_back(nums[i]);
}else{
int ind = lower_bound(temp.begin(),temp.end(),nums[i]) - temp.begin();
temp[ind] = nums[i];
}
}
return temp.size();
}
Thank You so much Bro
i don't know why ppl leave videos like this wdout giving a like. there are currently 8k+ views and only around 400 likes. btw awesome content !!!!!!!!!thanks
Some men just want to watch the world burn 🔥
and now its 172K views and 6.4k likes loml
Java Solution:
static int longestSubsequence(int size, int arr[])
{
// using binary search
ArrayList ans = new ArrayList();
ans.add(arr[0]);
int len = 1;
for (int i = 1; i < size; i++) {
if (arr[i] > ans.get(ans.size() - 1)) {
ans.add(arr[i]);
len++;
} else {
int indx = binarySearch(ans, arr[i]);
ans.set(indx, arr[i]);
}
}
return len;
}
static int binarySearch(ArrayList ans, int key) {
int low = 0;
int high = ans.size() - 1;
while (low
Very well explained. Watched multiple videos and it didn't click.
Understood!!!
Thanks for this amazing series 🎉
For all the java peeps out there
Use this function instead of lower bound
static int ceil(int key, List lst){
int low = 0 , lst = lst.size() - 1;
int ans = -1;
while(low
int l = 0 , h = li.size() - 1;
while(lnums.get(mid)) l=mid+1;
else h=mid-1;
}
return l
Wow, the only place where I need to come back since no other place helps me with the intuition.
For those who are wondering how is 'ind' calculated :-
ind = lower_bound(temp.begin(),temp.end(),arr[i]) - temp.begin();
thanks bro u saved my time
you can also use
auto ind = lower_bound(temp.begin(),temp.end(),arr[i]);
*ind = nums[i];
can you please explain this line of code ?
@@mrigankshigupta9859 basically you used auto to declare i, so it returns an iterator. *i is to approach the value where i points at.
can u just explain me why at 11:09 we overwrite 1 with 2...that wont become a subsequence then right?
Understood, Thanks for providing every possible intuition for Longest Increasing Subsequence
the most perfect N log N solution out there for LIS.
The concept of lower bound was so amazing...Thank you
This method is so good !! Much better TC and SC with such a short code !
Intution is superb... And Striver choice question is awesome :)
Great explanation, finally understood how it works!
This was really well made !! Kudos!!!
awesome content. the only binary search approach I could find online as well and i understood. great video
Awesome video by Striver as always!!! Java also has ceiling methods for TreeSet, TreeMap. Because we are inserting in such a way sequence is kept increasing even after deletion and reinsertion, below will get accepted as well:
public static int longestIncreasingSubsequence(int arr[]) {
//Your code goes here
TreeSet myset = new TreeSet();
myset.add( arr[0] );
for( int i = 0; i < arr.length; i++ ){
if( arr[i] > myset.last() ){
myset.add( arr[i] );
} else {
//Map.Entry entry = myset.ceilingEntry( arr[i] );
Integer ceilValue = myset.ceiling( arr[i] );
if( ceilValue != arr[i] ){
myset.remove( ceilValue );
myset.add( arr[i] );
}
}
}
return myset.size();
}
so sorry for my words but this optimization is so fucking good. Seriously, so many approches for a single question damm. honestly sir if u want u can just give the best approch and finish it but u r taking us step by step and make us undersatnd the actuall concepts. i m following ur playlist from the starting but after this question not able to stop myself from getting jump into the cmnt box. Really thank u sir for such a best ever playlist.
another O(nlogn) approach, kind of intuitive:
Note: first do the space optimization using only one array (only *dp* and not *dp* with *cur* ) and analyze how the table is getting filled.
make a duplicate array of pair {nums[i],i} and sort them. Lets name this array arr2. Now, the dp table is filled with "i" going n -> 0 as dp(prev) = max( dp(prev), 1+dp(i)) which essentially means that any number less than number at current index "i" will take its max i.e. { arr[i] > arr[prev] } and { i > prev } are the two conditions and then we can do dp[prev] = max(dp[prev], 1+dp[i]). thus we find the lower_bound of the current element arr[i] in arr2 and since arr2 is sorted, we go to all elements to left side of the lower_bound of arr[i]. as arr2 has size n and we are finding each arr[i] using binary search, this makes the complexity O(nlogn). Sorting also takes O(nlogn) so overall it works in O(nlogn).
But making the DP table required N^2 complexity right?
Great explanation. And also credit to people who invented and came up with this idea 💡. That's tough.
The intuition behind the binary search lies in the fact that we replace considerably bigger elements with smaller ones with the possibility that there are high chances that smaller elements will be smaller than upcoming bigger elements thereby forming LIS as compared to relatively existing bigger elements having possibility of being smaller than upcoming new elements meanwhile also maintaining max LIS list length up to some index i.
That makes sense. I was trying to find some logical idea to relate. We are always replacing element in array with smaller element.
Java guys can use TreeSet from the Collection framework.
// Code
public int lengthOfLIS(int[] nums) {
TreeSet ts = new TreeSet();
ts.add(nums[0]);
for(int i=1; i
Time complexity?
@@nikhilsanaye7494 n log n
thanks
at 14:57, I think The size() function does not recalculate or iterate over the elements each time it is called, so it has a constant time complexity.
Yes, the size() function for a std::vector in C++ has a time complexity of O(1).
@@gauravtiwary1839 i've been programming for 4 years and i didn't knew that the size function has 0(1) TC. can you please share the algo for size function.
I can understand what if a vector is already initialised
for ex:
vectorvec={1,2,3,4,5,6,7,8,9};
is vec.size(); 0(1)tc here also?
"UNDERSTOOD BHAIYA!!"
Very good series in which we solve a same question by different methods.
Thanks for letting me know thre concept of Upper Bound and lower bound
Isn't the elements in the final vector the LIS we require?
MIND BLOWING MAN! LOVED THE EXPLANATION.
I think we have to use an iterator for "ind" here because lower_bound will not return the index as int here. Can anyone clarify this?
We can subtract first iterator to get index
The concept of array could also be understood in this manner:
Basically the ith element of temp array means that the longest increasing subsequence whose greatest element is temp[i] has a length of i+1.
In the Algorithm what we are basically doing is that we are replacing the current element with it's best place in temp vector.
By best place I mean that the place at which current element is the greatest element in the longest increasing subsequence.
Let the index of that best place be ind(0 based indexing).
Then ind+1 is the length of the longest increasing subsequence whose greatest element is the current element.
Awesome explanation bro, thanks❤
Understood ❤
This is more like greedy we try to keep minimum values in lis so list can expand
awesome explanation as always
Wow your explanation is super
great explanation I love it, thank you sir
Just a small correction: lower_bound() gives index of first element which is greater than or equal to the target element. For getting index of 1st element, strictly greater than target element, we need upper_bound(). Anyway, great video as ever 🔥
No bro, lower bound hi hoga
Haan to lower bound is we all required if the element is present then we have to replace with the same elements if not then find first greater one
Understood, thank you sir, you are god to me , I worship striver Everyday. thanks.
I was searching for this explanation everywhere
Bhaiya tussi great ho!
good explanation 👍👍👍
that so useful, i have got the hang of its working after watching this video
This is the best intuition I have ever seen for LIS using BS, code and explaination is everywhere but intuition 🔥🔥
This algo of finding longest increasing subsequence by BINARY SEARCH is call patience sorting algorithm.
No need to update the temp if the index we got by lower_bound is not n-1,right?
thanks for another great video
If array is [ 5 4 6] the output 3
Since we counting the number of indes shorter than ith index
no that will not happen 5 will be overwritten by 4 and the array will be {4,6 } of length 2 and answer will be 2 not 3.
Not working for [0, 1, 0, 3, 2, 3], Expected: 4 Actual: 3
Understood ! Thank you.
really good explanation 😃
Is there any proof for binary search replacement method that it will not affect the LIS length?
Thanks somebody asked this question.
Where is the intution???
If interview ask this why you are replacing it, I don't know but this works 🤣🤣🤣🤣🤣🤣🤣
Was looking for this approach 😱👍
Understood!
heyy when you start this playlist ??? and in which year you are ?
@@Mohit_Q it's been 2 months since I started but I'm going slowly, btw I'm in my final year
DP Revision :
Uff bhai, how can I even forget this solution ;-;
Had to watch the previous two videos too, to get to the O(N) solution ;-;
Nov'20, 2023 03:30 pm
(Happy Birthday to me... ;))
Firstly a lots of thanks for delivering such an amazing content in an understandable way....
But one doubt...how does such intuition strikes to anyone while solving such questions...coz if this intuition strikes to anyone then it means that he is as equal as...a researcher/expert who has already developed such an algorithm for this question....
You can't form this solution in a 40min interview, if you've not seen it earlier
DOUBT If for arr={1,7,8,4,5,6,-1,9} say we are at i = 4, arr[i] = 5 and our temp is {1,4,8}..Now for comparing 5 in temp when we use lower_bound the range is [first, last) last not included..So isn't the comparison from temp.begin() to temp.end()-1? Since last is not included in the range.
Why temp array is not the lis and why it is only length of longest lis??
superb method
Understood, thank you so much.
thanks for your video. But have a doubt @11:06...If we are replacing items , what will be the output for 1,4,4,5,5,6,6,7]? Based on algorithm which you explained it will be 5 [1,4,5,6,7].. But i think actual output will be 8 ..
nahi bhai read the problem acha se they say greater than , not greater than equal to so therefore 5 is the correct answer
great intuition striver
int ind = lower_bound(temp.begin(),temp.end(),nums[i])-temp.begin();
At first I thought that the number will be added to the result directly if(arr[i] > arr[i - 1]), but later understood that it will only add the number directly to the result if(result.get(result.size() - 1) < arr[i]).
List res = new ArrayList();
for (int n : nums) {
if (res.isEmpty() || res.get(res.size() - 1) < n) {
res.add(n);
} else {
int index = binarySearch(res, n);
res.set(index, n);
}
}
return res.size();
no one can teach like you sir
What if the question was modified a bit and asking for non decreasing sub sequence instead of strictly increasing sub sequence, then in that case we cannot simply replace elements in the list right? So do we just insert these elements into the list? Or create a list of pair and if we have a duplicate we just increment count?
reverse the list and apply the same logic and reverse the final array to be returned
space complexity should be length of the lis??
Great explanation! Well understood, thanks!!
Great explanation ...pls continue like this
If I want to print the subsequence then how I can do this, the subsequence is changing and we are inserting the new element into a vector which is actually not a subsequence. I got the approach for finding but if i have to print it then ?
us guru us !!
I have a doubt.. isn't this going to be an upper_bound instead of lower_bound as we are finding the element which is >= current element?
Nice explanation
You can save in the same array as well.
Java code :
import java.util.*;
public class Solution {
public static int longestIncreasingSubsequence(int arr[]) {
//Your code goes here
int ptr = 0;
int idx = 1;
int n = arr.length;
while(idx < n) {
if( arr[idx] > arr[ptr] ) {
arr[++ptr] = arr[idx];
} else {
arr[bs(arr, arr[idx], ptr)] = arr[idx];
}
idx++;
}
return ptr+1;
}
public static int bs(int[] arr, int tar, int idx) {
int left = 0;
int right = idx;
int mid = 0;
while( left < right ) {
mid = left + (right-left)/2;
if( arr[mid] == tar ) {
return mid;
} else if( arr[mid] >tar ){
right = mid;
} else {
left = mid+1;
}
}
return left;
}
}
isn't this upper bound? element which is just greater than target?
for binary search dont we need sorted array
Mind blowing
thank you Striver:)
Understood, sir. Thank you very much.
absolute treat
hey striver .....kha se late ho aap itne approaches ........how can we improve our thinking like this
int lengthOfLIS(vector& nums) {
// Using Binery Search with the help of lower_bound
int n=nums.size();
int len=1;
for(int i=1;inums[len-1]){
len++;
swap(nums[len-1],nums[i]);
}else{
int ind=lower_bound(nums.begin(),nums.begin()+len,nums[i])-nums.begin();
nums[ind]=nums[i];
}
}
return len;
}
//I tried to solve using only given nums
int lengthOfLIS(vector& nums) {
int n = nums.size();
vector temp;
int lenn=1;
temp.push_back((nums[0]);
for(int i =1;itemp.back()){
temp.push_back(nums[i]);
lenn++;
}else{
int ind = lower_bound(temp.begin(),temp.end(),nums[i])-temp.begin();
temp[ind]=nums[i];
}
}
return lenn;
}
Alias -> LIS.
Dude ur the best
That was sooooooo smooth
Completely blown away😶🌫😶🌫
UNDERSTOOD!!!!🔥🔥🔥🔥
It's good that he has mentioned that this method is useful for finding only the length of the longest increasing subsequence, instead of the subsequence itself. For finding the longest increasing subsequence , you can refer to lecture 42 (hash method)).