title
DP 41. Longest Increasing Subsequence | Memoization

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 LIS problem with DP. In the next video we have learnt about the next method using tabulation. 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 41. Longest Increasing Subsequence | Memoization', 'heatmap': [{'end': 606.699, 'start': 556.107, 'weight': 0.775}, {'end': 1245.063, 'start': 1179.791, 'weight': 0.717}], 'summary': 'Covers the longest increasing subsequence (lis) pattern, explaining the concept, emphasizing order requirements, discussing generating the lis using brute force, recursion, and dynamic programming, and optimizing the recursive solution using memoization to achieve o(n^2) time and space complexity.', 'chapters': [{'end': 182.834, 'segs': [{'end': 52.967, 'src': 'embed', 'start': 0.049, 'weight': 0, 'content': [{'end': 1.85, 'text': 'hey, everyone, welcome back to take you forward.', 'start': 0.049, 'duration': 1.801}, {'end': 10.916, 'text': 'today we will be starting with another pattern of dp, which is the lis pattern, or the longest increasing subsequence pattern.', 'start': 1.85, 'duration': 9.066}, {'end': 13.258, 'text': 'now we have done some problems on subsequence.', 'start': 10.916, 'duration': 2.342}, {'end': 22.004, 'text': 'if you remember well enough, the dp 13 to dp 22 was based on dp on subsequences, but this is slightly different than that.', 'start': 13.258, 'duration': 8.746}, {'end': 24.886, 'text': 'okay, now, longest common subsequence.', 'start': 22.004, 'duration': 2.882}, {'end': 33.031, 'text': 'all of you know what is the definition of subsequence like, if i give you an array of n numbers, any contiguous or non-contiguous like,', 'start': 24.886, 'duration': 8.145}, {'end': 39.977, 'text': 'you can pick up 10, you can pick up 2, then you can pick up 5, then you can pick up 7, then you can pick up 101.', 'start': 33.031, 'duration': 6.946}, {'end': 43.6, 'text': 'so if i write this, this is a subsequence.', 'start': 39.977, 'duration': 3.623}, {'end': 48.504, 'text': 'okay, but if you write something like this, this is not a subsequence.', 'start': 43.6, 'duration': 4.904}, {'end': 52.967, 'text': 'why 5 and 2 have swapped places.', 'start': 48.504, 'duration': 4.463}], 'summary': 'Introducing the lis pattern for dp, different from previous subsequence patterns.', 'duration': 52.918, 'max_score': 0.049, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc49.jpg'}, {'end': 108.08, 'src': 'embed', 'start': 75.524, 'weight': 1, 'content': [{'end': 80.409, 'text': 'as the question name is suggesting, figure me out the longest increasing sub sequence.', 'start': 75.524, 'duration': 4.885}, {'end': 89.273, 'text': 'so among this, if i try to figure out different types of subsequences, i can say one of them is 10, 101.', 'start': 81.11, 'duration': 8.163}, {'end': 92.434, 'text': 'this is a subsequence of length 2.', 'start': 89.273, 'duration': 3.161}, {'end': 100.037, 'text': "and if i say i can figure 10 and, sorry, 901, that's again another subsequence of length 2.", 'start': 92.434, 'duration': 7.603}, {'end': 101.417, 'text': 'i can similarly say 5, 701, 5, 701.', 'start': 100.037, 'duration': 1.38}, {'end': 108.08, 'text': 'the length is 2.', 'start': 101.417, 'duration': 6.663}], 'summary': 'Identify longest increasing subsequence, e.g. 10, 101, length 2.', 'duration': 32.556, 'max_score': 75.524, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc75524.jpg'}], 'start': 0.049, 'title': 'Longest increasing subsequence pattern', 'summary': 'Introduces the lis pattern, emphasizes the order requirement, explains finding the longest increasing subsequence, and provides examples of subsequences of length 2 and 4, alluding to future content on printing the subsequence.', 'chapters': [{'end': 75.524, 'start': 0.049, 'title': 'Introduction to longest increasing subsequence pattern', 'summary': 'Covers the introduction to the lis pattern and explains the concept of a subsequence, emphasizing the requirement of following the order while picking elements.', 'duration': 75.475, 'highlights': ['The chapter covers the introduction to the LIS pattern and explains the concept of a subsequence, emphasizing the requirement of following the order while picking elements.', 'The DP 13 to DP 22 problems were based on DP on subsequences.', 'A subsequence is defined as picking elements that follow the order from an array of n numbers, whether contiguous or non-contiguous.']}, {'end': 182.834, 'start': 75.524, 'title': 'Longest increasing subsequence', 'summary': 'Explains the concept of finding the longest increasing subsequence and emphasizes the need to determine the length of the subsequence, with examples of subsequences of length 2 and 4, while also alluding to future content on printing the subsequence.', 'duration': 107.31, 'highlights': ['The longest increasing subsequence is determined by finding the sequence with the highest length, such as a sequence like 2, 3, 7, 101, resulting in a length of 4.', 'The concept of subsequences of length 2 is illustrated with examples like 10, 101 and 5, 701, emphasizing the need to identify the length of the subsequence.', 'The speaker alludes to the future content on printing the longest increasing subsequence, indicating additional information to be covered in subsequent videos.', "The pattern of 'pick or not pick' is highlighted as the approach to be followed in solving subsequence problems, emphasizing the decision-making process involved in selecting elements for the subsequence."]}], 'duration': 182.785, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc49.jpg', 'highlights': ['The DP 13 to DP 22 problems were based on DP on subsequences.', 'The longest increasing subsequence is determined by finding the sequence with the highest length, such as a sequence like 2, 3, 7, 101, resulting in a length of 4.', 'The chapter covers the introduction to the LIS pattern and explains the concept of a subsequence, emphasizing the requirement of following the order while picking elements.', 'The concept of subsequences of length 2 is illustrated with examples like 10, 101 and 5, 701, emphasizing the need to identify the length of the subsequence.', 'A subsequence is defined as picking elements that follow the order from an array of n numbers, whether contiguous or non-contiguous.']}, {'end': 416.819, 'segs': [{'end': 207.522, 'src': 'embed', 'start': 183.174, 'weight': 2, 'content': [{'end': 193.943, 'text': 'Now, going forward, if I ask you what is the longest common subsequence of this particular array, the answer to that will be Listen, the length is 1.', 'start': 183.174, 'duration': 10.769}, {'end': 199.651, 'text': 'Why? Because it clearly states, understand this particular word, it clearly states increasing.', 'start': 193.943, 'duration': 5.708}, {'end': 201.614, 'text': 'You cannot have equal elements.', 'start': 200.052, 'duration': 1.562}, {'end': 207.522, 'text': 'It has to be increasing like you see 2 is, you see the increasing pattern, it has to be increasing.', 'start': 201.994, 'duration': 5.528}], 'summary': 'The longest common subsequence of the array is 1, as it must be increasing.', 'duration': 24.348, 'max_score': 183.174, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc183174.jpg'}, {'end': 317.807, 'src': 'embed', 'start': 277.389, 'weight': 0, 'content': [{'end': 278.49, 'text': 'generate all the subsequence.', 'start': 277.389, 'duration': 1.101}, {'end': 279.27, 'text': 'check for increase.', 'start': 278.49, 'duration': 0.78}, {'end': 285.147, 'text': 'store the longest among them, store the longest.', 'start': 280.293, 'duration': 4.854}, {'end': 287.293, 'text': "so that's going to be the brute force, like.", 'start': 285.147, 'duration': 2.146}, {'end': 294.443, 'text': 'I will not be diving deep into it, because you can just go across and watch power set or recursion.', 'start': 288.422, 'duration': 6.021}, {'end': 295.723, 'text': 'generate all subsequences.', 'start': 294.443, 'duration': 1.28}, {'end': 302.344, 'text': 'Once the subsequence is generated, you just at the end of the day, see if that subsequence is increasing or not.', 'start': 295.923, 'duration': 6.421}, {'end': 305.185, 'text': 'And if it is, then you check for the longest portion.', 'start': 302.504, 'duration': 2.681}, {'end': 306.665, 'text': "So that's the brute force.", 'start': 305.825, 'duration': 0.84}, {'end': 313.626, 'text': 'And you know, in order to generate all the subsequences, you end up taking 2 to the power n time, because if you are generating all the subsequence,', 'start': 306.805, 'duration': 6.821}, {'end': 317.807, 'text': 'the number of subsequence for a length n is nothing but 2 to the power n.', 'start': 313.626, 'duration': 4.181}], 'summary': 'Brute force method to generate and check increasing subsequences with 2^n time complexity.', 'duration': 40.418, 'max_score': 277.389, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc277389.jpg'}, {'end': 426.802, 'src': 'embed', 'start': 397.069, 'weight': 1, 'content': [{'end': 399.13, 'text': "That's the generic way to write the recurrence.", 'start': 397.069, 'duration': 2.061}, {'end': 402.552, 'text': 'So we know that we have to express everything in terms of index.', 'start': 399.55, 'duration': 3.002}, {'end': 406.774, 'text': 'Because over here, we are definitely sure we are given an array.', 'start': 403.332, 'duration': 3.442}, {'end': 412.517, 'text': 'So an index will always be there which we can start from here, which is the 0th index.', 'start': 407.294, 'duration': 5.223}, {'end': 416.819, 'text': 'We definitely know there is going to be an index, right, which can start from 0th.', 'start': 413.197, 'duration': 3.622}, {'end': 424.192, 'text': 'zero. now i need to understand if this portion can be a part of my subsequence or not.', 'start': 417.725, 'duration': 6.467}, {'end': 426.802, 'text': 'Can this be a part of my subsequence?', 'start': 425.1, 'duration': 1.702}], 'summary': 'Express recurrence in terms of index for array representation.', 'duration': 29.733, 'max_score': 397.069, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc397069.jpg'}], 'start': 183.174, 'title': 'Longest increasing subsequence and its generation', 'summary': 'Explains the concept of finding the longest increasing subsequence in an array, emphasizing the requirement for strictly increasing elements. it also discusses generating the longest increasing subsequence using brute force technique, recursion, and writing recurrence, highlighting the exponential time complexity of brute force and the rule to write recurrences.', 'chapters': [{'end': 231.334, 'start': 183.174, 'title': 'Longest increasing subsequence', 'summary': 'Explains the concept of finding the longest increasing subsequence in an array, with an example demonstrating the length of the longest increasing subsequence and emphasizing the requirement for strictly increasing elements.', 'duration': 48.16, 'highlights': ['The length of the longest increasing subsequence is 1, as it requires strictly increasing elements, demonstrated by the example in the transcript.', 'The concept emphasizes the requirement for strictly increasing elements in the subsequence, with a clear demonstration using the given array and the pattern of increasing elements.']}, {'end': 416.819, 'start': 232.055, 'title': 'Generating longest increasing subsequence', 'summary': 'Discusses generating the longest increasing subsequence using brute force technique, recursion, and writing recurrence, highlighting the exponential time complexity of brute force and the rule to write recurrences.', 'duration': 184.764, 'highlights': ['The brute force technique of generating all subsequences has an exponential time complexity of 2 to the power n, making it inefficient and likely to result in TLE.', 'The rule to write recurrences involves expressing everything in terms of index and exploring all possibilities in subsequences, either picking or not picking, and determining the maximum length of both.', 'The chapter discusses using recursion and writing recurrences as alternative approaches to generating the longest increasing subsequence, providing insights into the rule for writing recurrences and expressing everything in terms of index.']}], 'duration': 233.645, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc183174.jpg', 'highlights': ['The brute force technique has an exponential time complexity of 2 to the power n, making it inefficient and likely to result in TLE.', 'The rule to write recurrences involves expressing everything in terms of index and exploring all possibilities in subsequences, either picking or not picking, and determining the maximum length of both.', 'The concept emphasizes the requirement for strictly increasing elements in the subsequence, with a clear demonstration using the given array and the pattern of increasing elements.', 'The length of the longest increasing subsequence is 1, as it requires strictly increasing elements, demonstrated by the example in the transcript.', 'The chapter discusses using recursion and writing recurrences as alternative approaches to generating the longest increasing subsequence, providing insights into the rule for writing recurrences and expressing everything in terms of index.']}, {'end': 667.142, 'segs': [{'end': 509.398, 'src': 'embed', 'start': 484.978, 'weight': 1, 'content': [{'end': 493.445, 'text': "you have to keep a store of the previous, because if you're deciding whether you take nine or not, you have to understand what you take,", 'start': 484.978, 'duration': 8.467}, {'end': 495.126, 'text': 'what you took previously.', 'start': 493.445, 'duration': 1.681}, {'end': 499.67, 'text': 'so someone has to tell you that you took previously the zeroth index, which is 10..', 'start': 495.126, 'duration': 4.544}, {'end': 501.211, 'text': 'someone has to tell this.', 'start': 499.67, 'duration': 1.541}, {'end': 508.177, 'text': 'so apparently what i can say is i can express the recurrence in terms of index and previous.', 'start': 501.211, 'duration': 6.966}, {'end': 509.398, 'text': 'why previous?', 'start': 508.177, 'duration': 1.221}], 'summary': 'Express recurrence in terms of index and previous to make informed decisions', 'duration': 24.42, 'max_score': 484.978, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc484978.jpg'}, {'end': 646.371, 'src': 'heatmap', 'start': 556.107, 'weight': 0, 'content': [{'end': 577.069, 'text': 'if i write f of three comma zero, this means length of elias starting from third index, whose previous index is zero.', 'start': 556.107, 'duration': 20.962}, {'end': 585.587, 'text': "let's understand this length of the elias starting from the third index, whose previous index is zero, which means One, two, three.", 'start': 577.069, 'duration': 8.518}, {'end': 587.989, 'text': "If you're here, the previous index is zero.", 'start': 586.208, 'duration': 1.781}, {'end': 593.192, 'text': 'What is the longest length you can get? If the previous is N that is what it means.', 'start': 588.389, 'duration': 4.803}, {'end': 594.192, 'text': 'Makes sense.', 'start': 593.772, 'duration': 0.42}, {'end': 596.333, 'text': 'That is the definition of the function.', 'start': 594.712, 'duration': 1.621}, {'end': 600.255, 'text': 'So I can say instead of index third, I can write index.', 'start': 596.854, 'duration': 3.401}, {'end': 603.877, 'text': 'And instead of this, I can write previous index.', 'start': 601.216, 'duration': 2.661}, {'end': 606.699, 'text': 'That is the definition of the function that we will define.', 'start': 604.338, 'duration': 2.361}, {'end': 612.802, 'text': 'Okay Now, since the definition is clear, we have expressed everything in terms of index and previous index.', 'start': 606.939, 'duration': 5.863}, {'end': 614.143, 'text': "So let's write it super quick.", 'start': 612.822, 'duration': 1.321}, {'end': 619.138, 'text': 'index and previous index.', 'start': 615.976, 'duration': 3.162}, {'end': 621.179, 'text': 'very, very simple thought process.', 'start': 619.138, 'duration': 2.041}, {'end': 623.861, 'text': "let's uh write the base cases afterwards.", 'start': 621.179, 'duration': 2.682}, {'end': 626.823, 'text': "now, what's the first thing that you write in recursion?", 'start': 623.861, 'duration': 2.962}, {'end': 636.248, 'text': 'very straightforward, it is Either you take that element into yourself or either you say this is not going to be the part of my subsequence.', 'start': 626.823, 'duration': 9.425}, {'end': 646.371, 'text': 'Because explore all possibilities means if you are standing at this particular 10, you say 10 come and be my part.', 'start': 636.728, 'duration': 9.643}], 'summary': 'Defining a function to find the longest length of elias sequence based on index and previous index.', 'duration': 51.659, 'max_score': 556.107, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc556107.jpg'}], 'start': 417.725, 'title': 'Longest increasing subsequence', 'summary': 'Discusses determining the longest increasing subsequence length using dynamic programming, expressing the recurrence in terms of index and previous index, and defining the function based on whether to include the current element or not.', 'chapters': [{'end': 667.142, 'start': 417.725, 'title': 'Longest increasing subsequence', 'summary': 'Discusses how to determine the longest increasing subsequence length using dynamic programming, expressing the recurrence in terms of index and previous index, and defining the function based on whether to include the current element or not.', 'duration': 249.417, 'highlights': ['The function is expressed in terms of index and previous index, allowing for a choice in including the current index in the subsequence, such as f(3, 0) meaning the length of the LIS starting from the third index with the previous index as zero.', 'The chapter emphasizes the importance of keeping track of the previous index to make decisions about including the current index in the subsequence, highlighting the need for a store of the previous element and expressing the recurrence in terms of index and previous.', 'The base case for the recursion is determined by either including the current element in the subsequence or moving to the next index, illustrating the decision-making process involved in forming the longest increasing subsequence.']}], 'duration': 249.417, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc417725.jpg', 'highlights': ['The function is expressed in terms of index and previous index, allowing for a choice in including the current index in the subsequence, such as f(3, 0) meaning the length of the LIS starting from the third index with the previous index as zero.', 'The chapter emphasizes the importance of keeping track of the previous index to make decisions about including the current index in the subsequence, highlighting the need for a store of the previous element and expressing the recurrence in terms of index and previous.', 'The base case for the recursion is determined by either including the current element in the subsequence or moving to the next index, illustrating the decision-making process involved in forming the longest increasing subsequence.']}, {'end': 1080.281, 'segs': [{'end': 696.793, 'src': 'embed', 'start': 667.142, 'weight': 1, 'content': [{'end': 676.408, 'text': 'and if this particular index is not the part of the sub sequence, can i say the previous index still stays the same.', 'start': 667.142, 'duration': 9.266}, {'end': 677.369, 'text': 'it does so.', 'start': 676.408, 'duration': 0.961}, {'end': 683.288, 'text': 'thereby the previous index still stays the same.', 'start': 677.369, 'duration': 5.919}, {'end': 688.755, 'text': "And if you're not including it into the part of your subsequence, will the length?", 'start': 683.689, 'duration': 5.066}, {'end': 691.017, 'text': 'because this function returns the length.', 'start': 688.755, 'duration': 2.262}, {'end': 694.613, 'text': 'if you remember the definition, it returns the length.', 'start': 691.017, 'duration': 3.596}, {'end': 696.793, 'text': 'so will the length increase?', 'start': 694.613, 'duration': 2.18}], 'summary': 'The function returns the length if the index is part of the subsequence.', 'duration': 29.651, 'max_score': 667.142, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc667142.jpg'}, {'end': 1059.127, 'src': 'embed', 'start': 1009.797, 'weight': 0, 'content': [{'end': 1017.62, 'text': "because for every index you're having two options take or not take, take or not take, take or not take.", 'start': 1009.797, 'duration': 7.823}, {'end': 1022.981, 'text': 'so in total it will yield two to the power n number of operations.', 'start': 1017.62, 'duration': 5.361}, {'end': 1030.144, 'text': 'so the time complexity becomes this and the space complexity will be an auxiliary stack space of v, go of n,', 'start': 1022.981, 'duration': 7.163}, {'end': 1035.268, 'text': "because you're going across a stack space of till till n.", 'start': 1030.144, 'duration': 5.124}, {'end': 1037.348, 'text': "this is the stack space that you'll be taking.", 'start': 1035.268, 'duration': 2.08}, {'end': 1043.434, 'text': 'so there will be an auxiliary stack space of v, go of n, and the time complexity will be true to the power n.', 'start': 1037.348, 'duration': 6.086}, {'end': 1048.137, 'text': 'obviously this is exponential and i will be looking to optimize this.', 'start': 1043.434, 'duration': 4.703}, {'end': 1050.839, 'text': 'and you have been going through the entire dp playlist.', 'start': 1048.137, 'duration': 2.702}, {'end': 1051.519, 'text': 'you know.', 'start': 1050.839, 'duration': 0.68}, {'end': 1053, 'text': 'how do you optimize a recursion?', 'start': 1051.519, 'duration': 1.481}, {'end': 1054.161, 'text': "that's very simple.", 'start': 1053, 'duration': 1.161}, {'end': 1059.127, 'text': 'you say I see for overlapping subproblems.', 'start': 1054.161, 'duration': 4.966}], 'summary': 'Using recursion for every index has exponential time complexity, with 2^n operations and auxiliary stack space of o(n). looking to optimize using overlapping subproblems.', 'duration': 49.33, 'max_score': 1009.797, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc1009797.jpg'}], 'start': 667.142, 'title': 'Finding longest increasing subsequence', 'summary': 'Explains the conditions for the take and not take case in finding the longest increasing subsequence, with a recursive solution having a time complexity of 2^n and a space complexity of o(n).', 'chapters': [{'end': 1080.281, 'start': 667.142, 'title': 'Finding longest increasing subsequence', 'summary': 'Explains the conditions for the take and not take case in finding the longest increasing subsequence, with a recursive solution having a time complexity of 2^n and a space complexity of o(n).', 'duration': 413.139, 'highlights': ['The chapter explains the conditions for the take and not take case in finding the longest increasing subsequence, with a recursive solution having a time complexity of 2^n and a space complexity of O(n.', 'The function returns the length of the subsequence, and if a particular index is not part of the subsequence, the previous index remains the same, leading to no increase in length.', 'In the take case, when an element without a previous index is chosen, the length of the subsequence increases by 1, and moving to the next index also affects the length.', 'The recursive solution has a time complexity of 2^n due to two options (take or not take) for every index, and a space complexity of O(n) due to the auxiliary stack space.', 'The optimization involves identifying and converting overlapping subproblems into memoization to improve the exponential time complexity of the recursive solution.']}], 'duration': 413.139, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc667142.jpg', 'highlights': ['The optimization involves identifying and converting overlapping subproblems into memoization to improve the exponential time complexity of the recursive solution.', 'In the take case, when an element without a previous index is chosen, the length of the subsequence increases by 1, and moving to the next index also affects the length.', 'The function returns the length of the subsequence, and if a particular index is not part of the subsequence, the previous index remains the same, leading to no increase in length.', 'The chapter explains the conditions for the take and not take case in finding the longest increasing subsequence, with a recursive solution having a time complexity of 2^n and a space complexity of O(n.']}, {'end': 1465.955, 'segs': [{'end': 1262.969, 'src': 'heatmap', 'start': 1179.791, 'weight': 0, 'content': [{'end': 1180.291, 'text': 'Okay, fine.', 'start': 1179.791, 'duration': 0.5}, {'end': 1186.978, 'text': "So, if I'm doing a coordinate shift, I require from 0 till n, which means.", 'start': 1180.992, 'duration': 5.986}, {'end': 1191.264, 'text': 'if I take n plus 1, that will suffice.', 'start': 1188.342, 'duration': 2.922}, {'end': 1192.025, 'text': "that's it.", 'start': 1191.264, 'duration': 0.761}, {'end': 1196.689, 'text': 'just do a coordinate change and you know how to just change it over here.', 'start': 1192.025, 'duration': 4.664}, {'end': 1205.055, 'text': 'instead of this, you write DP of previous sorry, DP of index and previous index.', 'start': 1196.689, 'duration': 8.366}, {'end': 1206.657, 'text': 'while storing, do a coordinate change.', 'start': 1205.055, 'duration': 1.602}, {'end': 1207.057, 'text': "that's it.", 'start': 1206.657, 'duration': 0.4}, {'end': 1211.501, 'text': 'plus 1 will do a coordinate change equal to length over here.', 'start': 1207.057, 'duration': 4.444}, {'end': 1220.708, 'text': 'while you come across DP of index, previous index, plus 1 is not equal to minus 1, then return.', 'start': 1211.501, 'duration': 9.207}, {'end': 1229.193, 'text': 'what I did was I just did a shuttle coordinate change and I converted this into a memoiation solution.', 'start': 1220.708, 'duration': 8.485}, {'end': 1233.896, 'text': 'and since I have converted this into a memoiation solution, now what is the time complexity?', 'start': 1229.193, 'duration': 4.703}, {'end': 1237.218, 'text': 'it is b, go into n into n.', 'start': 1233.896, 'duration': 3.322}, {'end': 1245.063, 'text': "space complexity will be n into n because of the dp array that you're creating of this size.", 'start': 1237.218, 'duration': 7.845}, {'end': 1251.705, 'text': "and there is an auxiliary stack space of bigo of n for the recursion call that you're making.", 'start': 1245.063, 'duration': 6.642}, {'end': 1256.287, 'text': "so i've trimmed down the time complexity into n square, which is quadratic,", 'start': 1251.705, 'duration': 4.582}, {'end': 1260.348, 'text': 'and the space complexity to n square plus something which is again quadratic.', 'start': 1256.287, 'duration': 4.061}, {'end': 1262.969, 'text': "so that's how you can easily solve this problem.", 'start': 1260.348, 'duration': 2.621}], 'summary': 'Coordinate shift for memoization solution reduces time complexity to n square and space complexity to n square.', 'duration': 51.468, 'max_score': 1179.791, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc1179791.jpg'}, {'end': 1451.896, 'src': 'embed', 'start': 1405.668, 'weight': 2, 'content': [{'end': 1408.276, 'text': 'include bits, std, c++, dot, h.', 'start': 1405.668, 'duration': 2.608}, {'end': 1411.618, 'text': 'okay, you see, all of them are running fine.', 'start': 1409.997, 'duration': 1.621}, {'end': 1414.139, 'text': "now let's quickly submit this off.", 'start': 1411.618, 'duration': 2.521}, {'end': 1417.961, 'text': 'so we see that this particular solution is giving you a runtime error.', 'start': 1414.139, 'duration': 3.822}, {'end': 1418.561, 'text': 'why is that?', 'start': 1417.961, 'duration': 0.6}, {'end': 1425.665, 'text': 'because if i just go across and check out the constraints of the solution of the question, rather, n is 10 to the power 5 right,', 'start': 1418.561, 'duration': 7.104}, {'end': 1438.048, 'text': "and if n is 10 to the power 5, and you're creating a size of n cross n cross array, n to the power 5, multiplied with 10 to the power 5,", 'start': 1425.665, 'duration': 12.383}, {'end': 1444.672, 'text': "that's a 10 to the power 10 size array you're trying to create, and that will definitely be not possible.", 'start': 1438.048, 'duration': 6.624}, {'end': 1446.633, 'text': "thereby you're getting a runtime error.", 'start': 1444.672, 'duration': 1.961}, {'end': 1451.896, 'text': 'so, guys, i hope in this video you have understood the recursion plus the memory solution.', 'start': 1446.633, 'duration': 5.263}], 'summary': 'Recursion & memory solution explained; array size limitation leads to runtime error.', 'duration': 46.228, 'max_score': 1405.668, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc1405668.jpg'}], 'start': 1080.801, 'title': 'Memoization and lis optimization', 'summary': 'Covers coordinate shift for memoization, reducing time complexity to o(n^2) and space complexity to o(n^2), and optimizing a recursive solution for lis, focusing on dynamic programming for memory optimization and constraints leading to a runtime error.', 'chapters': [{'end': 1262.969, 'start': 1080.801, 'title': 'Coordinate shift for memoization', 'summary': 'Explains how to convert a solution into memoization by using a coordinate shift, reducing the time complexity to o(n^2) and space complexity to o(n^2).', 'duration': 182.168, 'highlights': ['By using a coordinate shift, the solution is converted into memoization, reducing the time complexity to O(n^2) and space complexity to O(n^2).', 'The coordinate shift involves storing the -1 state at 0, 0 state at 1, 1 state at 2, and so on up to n-1 state at n, effectively allowing for the storage of the previous index.', 'The time complexity is reduced to O(n^2) and the space complexity to O(n^2) due to the coordinate shift and the creation of a dp array of size n.']}, {'end': 1465.955, 'start': 1262.969, 'title': 'Optimizing recursive solution for lis', 'summary': 'Discusses the process of optimizing a recursive solution for the longest increasing subsequence problem, highlighting the use of dynamic programming for memory optimization and the constraints leading to a runtime error in creating a large-sized array.', 'duration': 202.986, 'highlights': ['The chapter explains the process of optimizing a recursive solution for the Longest Increasing Subsequence problem by implementing dynamic programming to achieve memory optimization and overcome runtime errors due to large-sized arrays, with a focus on improving the efficiency of the code.', 'The chapter emphasizes the importance of considering constraints in problem-solving, particularly in scenarios where the creation of large-sized arrays, such as n cross n cross array for n to the power 5, could lead to runtime errors and inefficiencies, providing a practical example of the impact of constraints on algorithm design and implementation.', 'The chapter concludes by highlighting the significance of understanding recursion and memory solutions, encouraging viewers to like the video if they found the explanation helpful and to subscribe to the channel for more content, while also teasing the upcoming discussion on tabulation solution with space optimization for the Longest Increasing Subsequence problem in the next video.']}], 'duration': 385.154, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/ekcwMsSIzVc/pics/ekcwMsSIzVc1080801.jpg', 'highlights': ['The coordinate shift reduces time complexity to O(n^2) and space complexity to O(n^2)', 'The dp array of size n contributes to the reduction of time and space complexity to O(n^2)', 'The chapter emphasizes the importance of considering constraints in problem-solving', 'Implementing dynamic programming overcomes runtime errors due to large-sized arrays', 'Understanding recursion and memory solutions is highlighted as significant']}], 'highlights': ['The coordinate shift reduces time complexity to O(n^2) and space complexity to O(n^2)', 'The dp array of size n contributes to the reduction of time and space complexity to O(n^2)', 'The optimization involves identifying and converting overlapping subproblems into memoization to improve the exponential time complexity of the recursive solution', 'The function is expressed in terms of index and previous index, allowing for a choice in including the current index in the subsequence, such as f(3, 0) meaning the length of the LIS starting from the third index with the previous index as zero', 'The chapter emphasizes the importance of considering constraints in problem-solving']}