DP 43. Longest Increasing Subsequence | Binary Search | Intuition

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

[@takeUforward]

let me know in the comments, if this blew your mind or not :P

[@prathamchoudhary6244]

Great explanation!

[@jaideepsingh7955]

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 ?

[@Superheroic_Anime]

Mind blowing bhaiya

[@ShivaniSinghYadav-sm3ee]

My mind flew away and now I am chasing it 😌🥴

[@KapilKumar-ig6df]

lower_bound returns an iterator. How your code compiled by returning an index?

[@Joselson14]

This has been the most succinct explanation that I could find on KZbin. Thank you so much for your dedication.

[@gaurishukla9177]

Dude you were the only one who could explain why this worked!! loved it!!

[@rishika6525]

thanks for giving the intutution behind, really makes the solution more meaningful, rather than feeling like we just gotta cram it

[@-harshayadav]

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

[@dhanashreegodase4445]

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

[@parthsalat]

Some men just want to watch the world burn 🔥

[@parvathipillaiii]

and now its 172K views and 6.4k likes loml

[@CostaKazistov]

Perfect explanation of the intuition behind this solution. Nice work! 👍👍

[@AnkitJosh]

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 !

[@rishabhthakur7494]

At 11:15 the 2 will come after 1,even though nothing will change,just reminding.

[@aeroabrar_31]

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.

[@samratgupta731]

@@aeroabrar_31 +1 mate

[@vivekvardhankaranam2027]

i think 4 after that 1 has to be changed

[@sameersahu4569]

The concept of lower bound was so amazing...Thank you

[@Abhishek-yy3xg]

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

[@yogeshvishwakarma596]

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(); }

[@sharcodes]

Thank You so much Bro

[@NARUTOUZUMAKI-bk4nx]

Understood, Thanks for providing every possible intuition for Longest Increasing Subsequence

[@kartikey3695]

For those who are wondering how is 'ind' calculated :- ind = lower_bound(temp.begin(),temp.end(),arr[i]) - temp.begin();

[@harshkushwaha5052]

thanks bro u saved my time

[@arunabhgupta9082]

you can also use auto ind = lower_bound(temp.begin(),temp.end(),arr[i]); *ind = nums[i];

[@mrigankshigupta9859]

can you please explain this line of code ?

[@user-fz9ye6yk9y]

@@mrigankshigupta9859 basically you used auto to declare i, so it returns an iterator. *i is to approach the value where i points at.

[@meetabhashiniparida9417]

can u just explain me why at 11:09 we overwrite 1 with 2...that wont become a subsequence then right?

[@anshverma2921]

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.

[@stith_pragya]

UNDERSTOOD............Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@kolawoleabdulrahman]

awesome content. the only binary search approach I could find online as well and i understood. great video

[@sagarmittal8627]

This method is so good !! Much better TC and SC with such a short code !

[@vikashkumar7762]

Intution is superb... And Striver choice question is awesome :)

[@vishalvishwakarma1760]

MIND BLOWING MAN! LOVED THE EXPLANATION.

[@piyushsaxena7399]

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

[@sarthakjohnsonprasad3909]

Striver, trust me you have insane explanation skills.

[@DivyaKumari179]

Understood!!! Thanks for this amazing series 🎉

[@Zasyg]

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

[@satyamgupta1446]

int l = 0 , h = li.size() - 1; while(lnums.get(mid)) l=mid+1; else h=mid-1; } return l

[@ananyagupta1409]

This was really well made !! Kudos!!!

[@anshulagarwal6682]

Very good series in which we solve a same question by different methods.

[@soumyakantigiri]

Wow, the only place where I need to come back since no other place helps me with the intuition.

[@d_0364]

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).

[@muditkhanna8164]

the most perfect N log N solution out there for LIS.

[@deepakbhoria4172]

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(); }

[@ronakslibrary8635]

Thanks for letting me know thre concept of Upper Bound and lower bound

[@varunsharma1889]

Great explanation. And also credit to people who invented and came up with this idea 💡. That's tough.

[@Tunbumbum]

great explanation I love it, thank you sir

[@user-yc2lm3mr3m]

Awesome explanation bro, thanks❤

[@mohammadyahya78]

Wow your explanation is super

[@DevashishJose]

Understood, thank you so much.

[@SurajVT]

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

[@nikhilsanaye7494]

Time complexity?

[@coding8000]

Understood, thank you sir, you are god to me , I worship striver Everyday. thanks.

[@codingp110]

Bhaiya tussi great ho!

[@andreasleonidou3620]

Great explanation! Well understood, thanks!!

[@pranoymukherjee3319]

This is the best intuition I have ever seen for LIS using BS, code and explaination is everywhere but intuition 🔥🔥

[@rishav144]

Great explanation ...pls continue like this

[@kamleshsinghbisht5569]

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.

[@gagankainthola8454]

i feel this approach in not at all intuitive but thanks for the explanation bhaiya:)

[@utkarshkhairnar371]

No need to update the temp if the index we got by lower_bound is not n-1,right?

[@sayandey1131]

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 🔥

[@satvrii]

No bro, lower bound hi hoga

[@ujjawalraj6096]

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

[@theresilientpianist7114]

absolute treat

[@prashantmishra-yw4xu]

great intuition striver

[@cinime]

Understood! Thank U so much as always!!

[@gamengoaituyen4432]

that so useful, i have got the hang of its working after watching this video

[@singleslit2024ICPCgrind]

thank you Striver:)

[@the.stupid07]

good explanation 👍👍👍

[@prashanjeetkumar1999]

understood!!

[@ratinderpalsingh5909]

Understood, sir. Thank you very much.

[@Tejaswita872]

Nice explanation

[@AnkitVerma-yn3ku]

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.

[@prabhakaran5542]

Understood ❤

[@daumtto]

Dude ur the best

[@ITACHIUCHIHA-dr8sz]

Code to print LIS : www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/

[@tarunsahu2365]

what a great explanation simply loved it

[@prathamchoudhary6244]

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.

[@UECAshutoshKumar]

Understood!!!

[@no---on]

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 ?

[@3darpan]

Striver, this is just perfect !

[@lakeshkumar1252]

thanks for the easy and awesome explanation sir

[@rushikeshdeshpande8809]

I was searching for this explanation everywhere

[@roughero1353]

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?

[@dheerajshukla7008]

understand sir

[@shivisingh9975]

Understood!

[@rimpiranibaruah7922]

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.

[@verma_jay]

understood

[@jatinbhatoya8420]

JAVA SOLUTION - leetcode.com/problems/longest-increasing-subsequence/discuss/2172720/JAVA-oror-BINARY-SEARCH-oror-4-LINER

[@meenakshiyadav7471]

no one can teach like you sir

[@RohitKumar-dy2gc]

amazing

[@hiteshmehra361]

Is there any proof for binary search replacement method that it will not affect the LIS length?

[@dhruvalkushwaha5132]

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?

[@takeUforward]

We can subtract first iterator to get index

[@tvwanderer7729]

Understood.

[@l047vedanglokhande3]

Was looking for this approach 😱👍

[@varunaggarwal7126]

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.

[@gauravtiwary1839]

Yes, the size() function for a std::vector in C++ has a time complexity of O(1).

[@muditkhanna8164]

@@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?

[@immortal6978]

Understood bro

[@JAY-rm8pj]

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....

[@rajeshsingh-mv7zn]

You can't form this solution in a 40min interview, if you've not seen it earlier

[@shivasai7707]

This is more like greedy we try to keep minimum values in lis so list can expand awesome explanation as always

[@anukulgaurav3043]

this is mind blowing striver:)

[@rishabhgupta9846]

understood,great series

[@premduvvapu476]

Understood

[@yashchawla3729]

Osm explanation keep making this kind of videos

[@saiyamsachdeva3354]

bhaiya java me toh stl n hota toh humko lowerbound and upperbound ka code likhna padega??

[@utkarshchandra9787]

If array is [ 5 4 6] the output 3 Since we counting the number of indes shorter than ith index

[@muditkhanna8164]

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.

[@lakshaygupta5911]

really good explanation 😃

[@ganeshkamath89]

Thanks Striver. Understood.

[@SuyashSoni248]

Not working for [0, 1, 0, 3, 2, 3], Expected: 4 Actual: 3

[@dreamyme543]

Understood:)

[@googleit2490]

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... ;))

[@soubhikghosh6564]

Hi can anyone tell me if its possible to print LIS in o(nlogn) ? If yes, then how should the code look like?

[@m-bk4um]

understand

[@YeaOhYeahh]

daaamnnn🔥

[@ujjalsaha428]

As always "understood" ❤️

[@danb9047]

for binary search dont we need sorted array

[@halchal41]

This algo of finding longest increasing subsequence by BINARY SEARCH is call patience sorting algorithm.

[@rabiprakashshanitwarangal527]

space complexity should be length of the lis??