DP 43. Longest Increasing Subsequence | Binary Search | Intuition
Vložit
- čas přidán 11. 07. 2024
- Lecture Notes/C++/Java Codes: takeuforward.org/dynamic-prog...
Problem Link: bit.ly/3rVoIoq
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: • Re 1. Introduction to ...
a
Make sure to join our telegram group for discussions: linktr.ee/takeUforward
Full Playlist: • Striver's Dynamic Prog...
In this video, we solve the Longest Increasing Subsequence problem using Dynamic Programming
If you have not yet checked our SDE sheet, you should definitely do it: takeuforward.org/interviews/s...
You can also get in touch with me at my social handles: linktr.ee/takeUforward
let me know in the comments, if this blew your mind or not :P
Great explanation!
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?
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!!
This has been the most succinct explanation that I could find on CZcams. 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! 👍👍
Understood, Thanks for providing every possible intuition for Longest Increasing Subsequence
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
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 concept of lower bound was so amazing...Thank you
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
UNDERSTOOD............Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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
awesome content. the only binary search approach I could find online as well and i understood. great video
MIND BLOWING MAN! LOVED THE EXPLANATION.
This method is so good !! Much better TC and SC with such a short code !
Intution is superb... And Striver choice question is awesome :)
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.
Striver, trust me you have insane explanation skills.
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 this amazing series 🎉
This was really well made !! Kudos!!!
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.
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();
}
Very good series in which we solve a same question by different methods.
Awesome explanation bro, thanks❤
great explanation I love it, thank you sir
Understood, thank you so much.
Great explanation. And also credit to people who invented and came up with this idea 💡. That's tough.
Wow your explanation is super
the most perfect N log N solution out there for LIS.
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 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
Great explanation! Well understood, thanks!!
Thanks for letting me know thre concept of Upper Bound and lower bound
Great explanation ...pls continue like this
thank you Striver:)
Bhaiya tussi great ho!
Understood! Thank U so much as always!!
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?
great intuition striver
understood!!!
Understood, thank you sir, you are god to me , I worship striver Everyday. thanks.
No need to update the temp if the index we got by lower_bound is not n-1,right?
good explanation 👍👍👍
Nice explanation
Dude ur the best
what a great explanation simply loved it
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 ?
Understood, sir. Thank you very much.
that so useful, i have got the hang of its working after watching this video
Is there any proof for binary search replacement method that it will not affect the LIS length?
Understood ❤
Striver, this is just perfect !
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.
Understood!
I was searching for this explanation everywhere
thanks for the easy and awesome explanation sir
Was looking for this approach 😱👍
amazing
no one can teach like you sir
i feel this approach in not at all intuitive but thanks for the explanation bhaiya:)
Understood!!!
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
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.
Osm explanation keep making this kind of videos
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
This is the best intuition I have ever seen for LIS using BS, code and explaination is everywhere but intuition 🔥🔥
Understood bro
Understood.
understood
Hi can anyone tell me if its possible to print LIS in o(nlogn) ? If yes, then how should the code look like?
understood,great series
in java , I make a separate function for the binary search instead of using the inbuild Arrays.binarySearch(). But I am getting TLE . Why so ? Is there anyone who are also getting this issue like me ?
this is mind blowing striver:)
bhaiya java me toh stl n hota toh humko lowerbound and upperbound ka code likhna padega??
understand sir
Thanks Striver. Understood.
Not working for [0, 1, 0, 3, 2, 3], Expected: 4 Actual: 3
really good explanation 😃
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.
This is more like greedy we try to keep minimum values in lis so list can expand
awesome explanation as always
Understood
As always "understood" ❤️
Understood:)
Why temp array is not the lis and why it is only length of longest lis??
Love you bhai..
From Bangladesh..
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
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?
daaamnnn🔥
This algo of finding longest increasing subsequence by BINARY SEARCH is call patience sorting algorithm.
Understooooooooooooooooooooooooooood!!!!!!!!!!!!!!!!
helped a lot :)
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... ;))
Amazing 👌👌
I have been following this series right from the beginning and found it to be the best on youtube . Thank you striver for this awesome playlist.
can someone please give the brute force approach for this problem which he's explaining in the solution
understand