title

DP 43. Longest Increasing Subsequence | Binary Search | Intuition

description

Lecture Notes/C++/Java Codes: https://takeuforward.org/dynamic-programming/striver-dp-series-dynamic-programming-problems/
Problem Link: https://bit.ly/3rVoIoq
Please watch the video at 1.25x for a better experience.
Pre-req for this Series: https://www.youtube.com/watch?v=yVdKa8dnKiE&list=PLgUwDviBIf0rGlzIn_7rsaR2FQ5e6ZOL9
a
Make sure to join our telegram group for discussions: https://linktr.ee/takeUforward
Full Playlist: https://www.youtube.com/watch?v=FfXoiwwnxFw&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY
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: https://takeuforward.org/interviews/strivers-sde-sheet-top-coding-interview-problems/
You can also get in touch with me at my social handles: https://linktr.ee/takeUforward

detail

{'title': 'DP 43. Longest Increasing Subsequence | Binary Search | Intuition', 'heatmap': [{'end': 880.17, 'start': 832.988, 'weight': 0.721}], 'summary': 'Explains solving the longest increasing subsequence problem using binary search, addressing constraints of n=10^5, achieving time complexity of o(nlogn) and space complexity of o(n). additionally, it delves into understanding the thought process behind finding the lis using binary search, emphasizing the importance of intuition and prerequisites, and discusses optimizing subsequence length in dynamic programming with examples of overwriting elements and utilizing binary search.', 'chapters': [{'end': 51.956, 'segs': [{'end': 51.956, 'src': 'embed', 'start': 0.329, 'weight': 0, 'content': [{'end': 2.19, 'text': 'hey, everyone, welcome back to take you forward.', 'start': 0.329, 'duration': 1.861}, {'end': 8.375, 'text': 'so today we will be solving, uh, the problem longest increasing subsequence using binary search.', 'start': 2.19, 'duration': 6.185}, {'end': 18.001, 'text': 'in the previous two videos we have solved using recursion, memoization, space optimization or tabulation and an algorithmic approach.', 'start': 8.375, 'duration': 9.626}, {'end': 21.804, 'text': 'these approach has been covered in the previous couple of videos.', 'start': 18.001, 'duration': 3.803}, {'end': 36.07, 'text': 'but we did see that the constraint was n equal to 10 to the power 5 and the best we could do was time complexity of b go of n square and a space complexity of b go of n.', 'start': 21.804, 'duration': 14.266}, {'end': 40.451, 'text': 'this was the best that we had done till now.', 'start': 36.07, 'duration': 4.381}, {'end': 49.575, 'text': 'but if n is 10 to the power 5, n square is 10 to the power 5 square is 10 to the power 10 operations, which is definitely giving you a tle.', 'start': 40.451, 'duration': 9.124}, {'end': 51.956, 'text': 'so we we definitely cannot do this right.', 'start': 49.575, 'duration': 2.381}], 'summary': 'Solving longest increasing subsequence using binary search with constraints n=10^5, achieving time complexity o(n^2) and space complexity o(n).', 'duration': 51.627, 'max_score': 0.329, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH4329.jpg'}], 'start': 0.329, 'title': 'Longest increasing subsequence problem', 'summary': 'Covers solving the longest increasing subsequence problem using binary search, addressing constraints of n=10^5, achieving time complexity of o(nlogn) and space complexity of o(n).', 'chapters': [{'end': 51.956, 'start': 0.329, 'title': 'Longest increasing subsequence problem', 'summary': 'Covers solving the longest increasing subsequence problem using binary search, addressing constraints of n=10^5, achieving time complexity of o(nlogn) and space complexity of o(n).', 'duration': 51.627, 'highlights': ['The previous approaches of recursion, memoization, space optimization, and algorithmic approach have been covered in the previous videos.', 'The time complexity achieved till now was O(n^2) and space complexity was O(n), which was not efficient enough for the constraint of n=10^5.', 'Using binary search, the time complexity achieved is O(nlogn) and the space complexity achieved is O(n), which is efficient for the given constraint.']}], 'duration': 51.627, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH4329.jpg', 'highlights': ['Using binary search achieves time complexity of O(nlogn) and space complexity of O(n)', 'Previous approaches had time complexity of O(n^2) and space complexity of O(n)', 'Covered recursion, memoization, space optimization, and algorithmic approach']}, {'end': 343.051, 'segs': [{'end': 119.813, 'src': 'embed', 'start': 51.956, 'weight': 1, 'content': [{'end': 55.398, 'text': "so that's where something like binary search comes in.", 'start': 51.956, 'duration': 3.442}, {'end': 58.02, 'text': 'can we find lis using binary search?', 'start': 55.398, 'duration': 2.622}, {'end': 61.722, 'text': "now you'll find a lot of videos where the intuition is missing.", 'start': 58.02, 'duration': 3.702}, {'end': 64.824, 'text': 'like i, i went through a lot of videos but the intuition was missing.', 'start': 61.722, 'duration': 3.102}, {'end': 72.608, 'text': 'so in this video my main focus will be to give you the thought process, because once you get the thought process, the algorithm is very, very simple.', 'start': 64.824, 'duration': 7.784}, {'end': 81.602, 'text': "so prerequisites are you should be knowing binary search and there is a lower bound and there's an upper bound video in, uh, my channel.", 'start': 72.608, 'duration': 8.994}, {'end': 83.283, 'text': "i'll be putting the link in the description.", 'start': 81.602, 'duration': 1.681}, {'end': 86.987, 'text': 'go back and watch it and after that come back and watch this video again.', 'start': 83.283, 'duration': 3.704}, {'end': 88.108, 'text': "uh, if you know low bound, it's.", 'start': 86.987, 'duration': 1.121}, {'end': 88.749, 'text': 'uh, well and good.', 'start': 88.108, 'duration': 0.641}, {'end': 89.95, 'text': "so let's let's get started.", 'start': 88.749, 'duration': 1.201}, {'end': 92.673, 'text': 'what is, first of all, what is lis?', 'start': 89.95, 'duration': 2.723}, {'end': 96.277, 'text': 'you know what is longest increasing subsequence like.', 'start': 92.673, 'duration': 3.604}, {'end': 99.84, 'text': 'uh, you can call a subsequence like one, eight, four, six.', 'start': 96.277, 'duration': 3.563}, {'end': 102.023, 'text': 'this is a subsequence not increasing.', 'start': 99.84, 'duration': 2.183}, {'end': 107.384, 'text': 'You can call something like 1,, 8, 9 as an increasing subsequence.', 'start': 102.717, 'duration': 4.667}, {'end': 119.813, 'text': 'Increasing Similarly, you can call something like 1, 4, 5, 6, 9 as the longest increasing subsequence of length 5.', 'start': 108.025, 'duration': 11.788}], 'summary': 'Explaining binary search and finding lis in a clear, intuitive manner; emphasizing the importance of understanding the thought process.', 'duration': 67.857, 'max_score': 51.956, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH451956.jpg'}, {'end': 181.413, 'src': 'embed', 'start': 149.036, 'weight': 0, 'content': [{'end': 150.016, 'text': "that's, that's a big.", 'start': 149.036, 'duration': 0.98}, {'end': 152.438, 'text': 'so how do you approach this problem?', 'start': 150.016, 'duration': 2.422}, {'end': 159.443, 'text': "so what I'll see is ok, let's, let's try to go across every element and try to form sub sequences.", 'start': 152.438, 'duration': 7.005}, {'end': 161.665, 'text': "that's that's my thinking.", 'start': 159.443, 'duration': 2.222}, {'end': 167.769, 'text': "so be like ok, initially, when I'm at one, ok, let's form a sub sequence with one.", 'start': 161.665, 'duration': 6.104}, {'end': 168.81, 'text': 'make sense.', 'start': 167.769, 'duration': 1.041}, {'end': 169.851, 'text': "next let's go to seven.", 'start': 168.81, 'duration': 1.041}, {'end': 177.953, 'text': 'i need to form a new sub sequence with sir, or can i just attach over like attach it over here?', 'start': 171.451, 'duration': 6.502}, {'end': 181.413, 'text': "the answer to that is uh, let's try, let's attach it over here.", 'start': 177.953, 'duration': 3.46}], 'summary': 'Approaching problem by forming sub sequences, attaching elements.', 'duration': 32.377, 'max_score': 149.036, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH4149036.jpg'}, {'end': 343.051, 'src': 'embed', 'start': 315.069, 'weight': 4, 'content': [{'end': 322.035, 'text': 'But will you actually go across and generate all these subsequences?', 'start': 315.069, 'duration': 6.966}, {'end': 332.463, 'text': "because it's going to be very hectic and it's going to be taking a lot of time, because If you make new subsequences at every junction,", 'start': 322.035, 'duration': 10.428}, {'end': 333.604, 'text': "it's gonna take up a lot of space.", 'start': 332.463, 'duration': 1.141}, {'end': 340.169, 'text': "Because if you're aiming to make a new subsequence at every step, it's gonna take up a lot of space.", 'start': 334.304, 'duration': 5.865}, {'end': 343.051, 'text': 'So, we will definitely not move this way.', 'start': 340.649, 'duration': 2.402}], 'summary': 'Generating all subsequences would be time-consuming and space-inefficient.', 'duration': 27.982, 'max_score': 315.069, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH4315069.jpg'}], 'start': 51.956, 'title': 'Understanding longest increasing subsequence (lis)', 'summary': 'Delves into understanding the thought process behind finding the longest increasing subsequence (lis) using binary search, emphasizing the importance of intuition and prerequisites. additionally, it discusses the concept of the longest increasing subsequence, demonstrating the approach to solving the problem and highlighting the implications of generating all subsequences.', 'chapters': [{'end': 92.673, 'start': 51.956, 'title': 'Understanding lis using binary search', 'summary': 'Discusses the thought process behind finding the longest increasing subsequence (lis) using binary search, emphasizing the importance of understanding the intuition and prerequisites including knowledge of binary search and lower bound.', 'duration': 40.717, 'highlights': ['The importance of understanding the thought process behind finding LIS using binary search, as it simplifies the algorithm significantly.', 'Emphasizing the necessity of knowing prerequisites such as binary search and lower bound for effectively grasping the concepts discussed in the video.']}, {'end': 343.051, 'start': 92.673, 'title': 'Longest increasing subsequence', 'summary': 'Discusses the concept of the longest increasing subsequence, demonstrating the approach to solving the problem and highlighting the implications of generating all subsequences.', 'duration': 250.378, 'highlights': ['The longest increasing subsequence is demonstrated using the example of a sequence with a length of 5, showing the process of forming the subsequence step by step.', 'The approach to solving the longest increasing subsequence involves considering each element and determining whether to form a new subsequence or attach it to the existing subsequence, illustrating the thought process and decision-making involved.', 'The implications of generating all subsequences at every junction are highlighted, emphasizing the potential space complexity and inefficiency of this approach.']}], 'duration': 291.095, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH451956.jpg', 'highlights': ['The approach to solving LIS involves considering each element and determining whether to form a new subsequence or attach it to the existing subsequence, illustrating the thought process and decision-making involved.', 'The importance of understanding the thought process behind finding LIS using binary search, as it simplifies the algorithm significantly.', 'Emphasizing the necessity of knowing prerequisites such as binary search and lower bound for effectively grasping the concepts discussed in the video.', 'The longest increasing subsequence is demonstrated using the example of a sequence with a length of 5, showing the process of forming the subsequence step by step.', 'The implications of generating all subsequences at every junction are highlighted, emphasizing the potential space complexity and inefficiency of this approach.']}, {'end': 976.778, 'segs': [{'end': 480.29, 'src': 'embed', 'start': 451.947, 'weight': 3, 'content': [{'end': 456.424, 'text': 'So We are sure that before 8, there is something smaller, which is 7.', 'start': 451.947, 'duration': 4.477}, {'end': 460.065, 'text': 'Yeah, we have overwritten it, but we are not concerned about the subsequence.', 'start': 456.424, 'duration': 3.641}, {'end': 465.746, 'text': "That's why what I did is, instead of creating a new, I overwrote the 7.", 'start': 460.525, 'duration': 5.221}, {'end': 472.428, 'text': "I overwrote the 7 to 4 because it's okay to overwrite because we're not concerned about the alias.", 'start': 465.746, 'duration': 6.682}, {'end': 473.388, 'text': "We're concerned about the length.", 'start': 472.468, 'duration': 0.92}, {'end': 476.169, 'text': 'So, I overwrote it at that place itself.', 'start': 473.788, 'duration': 2.381}, {'end': 480.29, 'text': "Perfect Let's move across to the next, which is 5.", 'start': 476.649, 'duration': 3.641}], 'summary': 'Overwrote 7 to 4, focusing on length not alias.', 'duration': 28.343, 'max_score': 451.947, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH4451947.jpg'}, {'end': 560.762, 'src': 'embed', 'start': 531.356, 'weight': 1, 'content': [{'end': 535.29, 'text': 'The length of the final array will be your answer which is 5.', 'start': 531.356, 'duration': 3.934}, {'end': 538.653, 'text': 'Because you replicated by putting those values.', 'start': 535.29, 'duration': 3.363}, {'end': 541.475, 'text': 'You replicated the same space by putting those values.', 'start': 538.993, 'duration': 2.482}, {'end': 544.038, 'text': "That's how you can easily do it.", 'start': 542.096, 'duration': 1.942}, {'end': 548.281, 'text': 'Now, why binary search? Again, very straightforward.', 'start': 544.498, 'duration': 3.783}, {'end': 551.444, 'text': 'If I again just omit this off.', 'start': 548.301, 'duration': 3.143}, {'end': 554.507, 'text': "I'll be just omitting this.", 'start': 553.506, 'duration': 1.001}, {'end': 557.189, 'text': 'Why binary search? Again, a very simple one.', 'start': 555.648, 'duration': 1.541}, {'end': 560.762, 'text': 'Because initially you had 1, then you had 7.', 'start': 557.649, 'duration': 3.113}], 'summary': 'Final array length is 5, replicated values, binary search rationale, starting with 1 and then 7.', 'duration': 29.406, 'max_score': 531.356, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH4531356.jpg'}, {'end': 724.454, 'src': 'embed', 'start': 686.308, 'weight': 0, 'content': [{'end': 689.79, 'text': 'Can you regenerate the subsequence via binary search? The answer is no.', 'start': 686.308, 'duration': 3.482}, {'end': 697.634, 'text': 'Then you have to store a lot more things, but you can easily get the length by accessing the length because you optimize space.', 'start': 690.21, 'duration': 7.424}, {'end': 702.897, 'text': 'Instead of carrying different subsequences, you reuse that space and you created it.', 'start': 698.175, 'duration': 4.722}, {'end': 706.459, 'text': "So it's time to actually now go back and code it.", 'start': 703.458, 'duration': 3.001}, {'end': 724.454, 'text': 'So, in order to find remember this, our main intention of binary search is, if there is an element as array of i, find array of i, like in this case.', 'start': 708.4, 'duration': 16.054}], 'summary': 'Binary search not suitable for regenerating subsequences, focus on reusing space and optimizing length.', 'duration': 38.146, 'max_score': 686.308, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH4686308.jpg'}, {'end': 769.41, 'src': 'embed', 'start': 744.183, 'weight': 2, 'content': [{'end': 750.146, 'text': 'and in c plus plus this can easily be done using a function a lower bound, the lower bound.', 'start': 744.183, 'duration': 5.963}, {'end': 754.908, 'text': 'if you are doing a lower bound on any array, it gives you the first index.', 'start': 750.146, 'duration': 4.762}, {'end': 765.627, 'text': 'it gives you the index of array of i, if exist, or gives you the first index which is greater than array of I.', 'start': 754.908, 'duration': 10.719}, {'end': 769.41, 'text': 'In order to understand it in depth, you can watch the video link in the description.', 'start': 765.627, 'duration': 3.783}], 'summary': 'C++ lower bound function returns first index or greater', 'duration': 25.227, 'max_score': 744.183, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH4744183.jpg'}, {'end': 880.17, 'src': 'heatmap', 'start': 832.988, 'weight': 0.721, 'content': [{'end': 841.572, 'text': 'so int index, you can easily do a binary search like lower bound, and the temporary space is this so just do a begin comma,', 'start': 832.988, 'duration': 8.584}, {'end': 845.093, 'text': "temporary dot end and you're looking for array of i.", 'start': 841.572, 'duration': 3.521}, {'end': 848.474, 'text': "that's what you'll do a binary search and you can just subtract them.", 'start': 845.093, 'duration': 3.381}, {'end': 849.695, 'text': "that's how easy.", 'start': 848.474, 'duration': 1.221}, {'end': 852.896, 'text': 'the binary search will be looking perfect.', 'start': 849.695, 'duration': 3.201}, {'end': 857.597, 'text': "once you've got the index, just go to temporary index and say this is where this guy will replace.", 'start': 852.896, 'duration': 4.701}, {'end': 862.198, 'text': 'once you have done this, you can directly return the temp dot size.', 'start': 857.597, 'duration': 4.601}, {'end': 865.099, 'text': 'perfect, and in this way, if you run this code.', 'start': 862.198, 'duration': 2.901}, {'end': 865.619, 'text': 'it should be.', 'start': 865.099, 'duration': 0.52}, {'end': 867.12, 'text': 'i think it should give you the correct answer.', 'start': 865.619, 'duration': 1.501}, {'end': 869.227, 'text': 'uh, my bad, temp.begin.', 'start': 868.087, 'duration': 1.14}, {'end': 873.168, 'text': 'this will be temp.begin now, it should give you the correct answer.', 'start': 869.227, 'duration': 3.941}, {'end': 874.348, 'text': 'so we did a mistake.', 'start': 873.168, 'duration': 1.18}, {'end': 876.769, 'text': 'this will be array of i and yeah, it should be fine.', 'start': 874.348, 'duration': 2.421}, {'end': 880.17, 'text': 'now, and you see, all the test cases are running absolutely fine.', 'start': 876.769, 'duration': 3.401}], 'summary': 'Binary search and array manipulation for efficient code. test cases successful.', 'duration': 47.182, 'max_score': 832.988, 'thumbnail': ''}], 'start': 343.391, 'title': 'Optimizing subsequence length', 'summary': 'Discusses optimizing subsequence length in dynamic programming, with examples of overwriting elements and utilizing binary search to find the length of an increasing subsequence with a focus on space and time complexity and the lower bound function in c++.', 'chapters': [{'end': 530.595, 'start': 343.391, 'title': 'Overwriting subsequences for length', 'summary': 'Discusses overwriting subsequences in a dynamic programming context to optimize space while focusing on the length of the subsequence, as demonstrated through examples of overwriting elements like 7 with 4 and 8 with 5 to maintain the same length.', 'duration': 187.204, 'highlights': ['The approach involves overwriting elements in the subsequence to optimize space, demonstrated by replacing 7 with 4 and 8 with 5 while maintaining the same length.', 'The emphasis is on preserving the length of the subsequence rather than its specific elements, showcased by the process of overwriting 7 with 4 and 8 with 5 to illustrate this optimization.', 'The focus is on optimizing space and preserving the length of the subsequence, exemplified by the strategy of overwriting specific elements like 7 with 4 and 8 with 5 in the dynamic programming process.']}, {'end': 976.778, 'start': 531.356, 'title': 'Binary search solution', 'summary': 'Explains the concept of binary search in finding the length of an increasing subsequence in an array, utilizing a thought process to optimize space and time complexity, and utilizing the lower bound function in c++.', 'duration': 445.422, 'highlights': ['Binary search is used to find the length of an increasing subsequence in an array, optimizing space by reusing the same space for different values, resulting in a final array length of 5.', 'The thought process behind using binary search to find the length of an increasing subsequence involves replicating the same space by putting values and utilizing the fact that the array is sorted.', 'Utilizing the lower bound function in C++ allows for efficient finding of the first index of an element in the array or the first index greater than the element, optimizing the time complexity of the solution.', 'The solution involves using a temporary array to store the increasing subsequence length, with the intention of not generating the actual subsequence but rather optimizing space and time complexity.', 'The chapter concludes with a call to action for viewers to like, subscribe, and comment on their understanding of the concept, emphasizing engagement and feedback.']}], 'duration': 633.387, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/on2hvxBXJH4/pics/on2hvxBXJH4343391.jpg', 'highlights': ['The solution involves using a temporary array to store the increasing subsequence length, optimizing space and time complexity.', 'Binary search is used to find the length of an increasing subsequence in an array, resulting in a final array length of 5.', 'Utilizing the lower bound function in C++ allows for efficient finding of the first index of an element in the array or the first index greater than the element, optimizing the time complexity of the solution.', 'The approach involves overwriting elements in the subsequence to optimize space, demonstrated by replacing 7 with 4 and 8 with 5 while maintaining the same length.', 'The emphasis is on preserving the length of the subsequence rather than its specific elements, showcased by the process of overwriting 7 with 4 and 8 with 5 to illustrate this optimization.']}], 'highlights': ['Using binary search achieves time complexity of O(nlogn) and space complexity of O(n)', 'The approach to solving LIS involves considering each element and determining whether to form a new subsequence or attach it to the existing subsequence, illustrating the thought process and decision-making involved.', 'The solution involves using a temporary array to store the increasing subsequence length, optimizing space and time complexity.', 'The importance of understanding the thought process behind finding LIS using binary search, as it simplifies the algorithm significantly.', 'Utilizing the lower bound function in C++ allows for efficient finding of the first index of an element in the array or the first index greater than the element, optimizing the time complexity of the solution.', 'Previous approaches had time complexity of O(n^2) and space complexity of O(n)', 'Emphasizing the necessity of knowing prerequisites such as binary search and lower bound for effectively grasping the concepts discussed in the video.', 'The longest increasing subsequence is demonstrated using the example of a sequence with a length of 5, showing the process of forming the subsequence step by step.', 'The implications of generating all subsequences at every junction are highlighted, emphasizing the potential space complexity and inefficiency of this approach.', 'The approach involves overwriting elements in the subsequence to optimize space, demonstrated by replacing 7 with 4 and 8 with 5 while maintaining the same length.']}