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
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.
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
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 !
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 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!
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).
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
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
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(); }
@@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 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.
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.
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.
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 🔥
Instead of lower bound , Upper bound looks more intuitive beacuse at each else case we are finding the ceil of arr[i] class Solution { private int upperBound(ArrayList arr, int k){ int low=0; int high=arr.size()-1; while(low=k){ high= mid-1; } else{ low= mid+1; } } return low; } public int lengthOfLIS(int[] nums) { int n=nums.length; ArrayList al=new ArrayList(); al.add(nums[0]); for(int i=1;ial.get(al.size()-1)){ al.add(nums[i]); } else{ int idx= upperBound(al, nums[i]); al.set(idx, nums[i]); } }
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 ..
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.
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....
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?
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... ;))
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)).
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; }
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 ?
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
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.
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
Dude you were the only one who could explain why this worked!! loved it!!
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
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
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! 👍👍
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
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 !
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
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?
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!
Striver, trust me you have insane explanation skills.
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?
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
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 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
Understood!!!
Thanks for this amazing series 🎉
Understood, Thanks for providing every possible intuition for Longest Increasing Subsequence
Very well explained. Watched multiple videos and it didn't click.
The concept of lower bound was so amazing...Thank you
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();
}
Intution is superb... And Striver choice question is awesome :)
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?
Wow, the only place where I need to come back since no other place helps me with the intuition.
This method is so good !! Much better TC and SC with such a short code !
the most perfect N log N solution out there for LIS.
Great explanation, finally understood how it works!
i feel this approach in not at all intuitive but thanks for the explanation bhaiya:)
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.
This was really well made !! Kudos!!!
Great explanation. And also credit to people who invented and came up with this idea 💡. That's tough.
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 content. the only binary search approach I could find online as well and i understood. great video
"UNDERSTOOD BHAIYA!!"
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.
Thanks for letting me know thre concept of Upper Bound and lower bound
MIND BLOWING MAN! LOVED THE EXPLANATION.
Very good series in which we solve a same question by different methods.
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
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
Awesome explanation bro, thanks❤
Understood ❤
No need to update the temp if the index we got by lower_bound is not n-1,right?
Instead of lower bound , Upper bound looks more intuitive beacuse at each else case we are finding the ceil of arr[i]
class Solution {
private int upperBound(ArrayList arr, int k){
int low=0;
int high=arr.size()-1;
while(low=k){
high= mid-1;
}
else{
low= mid+1;
}
}
return low;
}
public int lengthOfLIS(int[] nums) {
int n=nums.length;
ArrayList al=new ArrayList();
al.add(nums[0]);
for(int i=1;ial.get(al.size()-1)){
al.add(nums[i]);
}
else{
int idx= upperBound(al, nums[i]);
al.set(idx, nums[i]);
}
}
return al.size();
}
}
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
Understood, thank you sir, you are god to me , I worship striver Everyday. thanks.
Isn't the elements in the final vector the LIS we require?
Understood ! Thank you.
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.
great explanation I love it, thank you sir
Wow your explanation is super
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
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
Great explanation! Well understood, thanks!!
This algo of finding longest increasing subsequence by BINARY SEARCH is call patience sorting algorithm.
Bhaiya tussi great ho!
Understood, thank you so much.
I was searching for this explanation everywhere
really good explanation 😃
that so useful, i have got the hang of its working after watching this video
Was looking for this approach 😱👍
Understood, sir. Thank you very much.
thanks for another great video
good explanation 👍👍👍
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.
thank you Striver:)
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... ;))
This is the best intuition I have ever seen for LIS using BS, code and explaination is everywhere but intuition 🔥🔥
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 🤣🤣🤣🤣🤣🤣🤣
int ind = lower_bound(temp.begin(),temp.end(),nums[i])-temp.begin();
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?
space complexity should be length of the lis??
great intuition striver
Great explanation ...pls continue like this
no one can teach like you sir
superb method
This is more like greedy we try to keep minimum values in lis so list can expand
awesome explanation as always
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)).
absolute treat
bhaiya java me toh stl n hota toh humko lowerbound and upperbound ka code likhna padega??
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;
}
Dude ur the best
Why temp array is not the lis and why it is only length of longest lis??
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 ?
thanks for the easy and awesome explanation sir
Not working for [0, 1, 0, 3, 2, 3], Expected: 4 Actual: 3
Mind blowing
Nice explanation
what a great explanation simply loved it
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
Understood! Thank U so much as always!!
crazy 🧨🧨
Love you bhai..
From Bangladesh..
for binary search dont we need sorted array
Thanks Striver. Understood.
Completely blown away😶🌫😶🌫
Hi can anyone tell me if its possible to print LIS in o(nlogn) ? If yes, then how should the code look like?