title
DP 42. Printing Longest Increasing Subsequence | Tabulation | Algorithm

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 DP using tabulation method, then we go on to print the LIS as well. 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 42. Printing Longest Increasing Subsequence | Tabulation | Algorithm', 'heatmap': [{'end': 250.12, 'start': 216.443, 'weight': 0.712}, {'end': 1323.529, 'start': 1276.172, 'weight': 0.816}, {'end': 1387.962, 'start': 1336.156, 'weight': 0.747}], 'summary': 'Covers tabulation approach for dynamic programming, recurrence copying, finding longest increasing subsequence, and backtracking techniques. it emphasizes time complexity of o(n) and space optimization, with a focus on reducing space complexity to n*2 for better solutions.', 'chapters': [{'end': 136.909, 'segs': [{'end': 107.585, 'src': 'embed', 'start': 28.311, 'weight': 0, 'content': [{'end': 34.998, 'text': 'okay. so going back, going back to the recursive code okay, going back to the recursive code,', 'start': 28.311, 'duration': 6.687}, {'end': 39.763, 'text': 'how do you convert this portion of recursive code into a tabulated code?', 'start': 34.998, 'duration': 4.765}, {'end': 40.865, 'text': "that's a very big question.", 'start': 39.763, 'duration': 1.102}, {'end': 47.507, 'text': 'now i, if you have been following this dp series right from the first, you know the rules.', 'start': 41.784, 'duration': 5.723}, {'end': 53.529, 'text': 'the rules are very simple write the base case and before that declare the dp of the same size.', 'start': 47.507, 'duration': 6.022}, {'end': 57.211, 'text': "so i'll declare a dp of n plus 1 and then write the base case.", 'start': 53.529, 'duration': 3.682}, {'end': 60.072, 'text': 'now, if you look at the code, what is the base case?', 'start': 57.211, 'duration': 2.861}, {'end': 66.775, 'text': 'we just have one base case, which is if index is equal to equal to n, we have to return a 0.', 'start': 60.072, 'duration': 6.703}, {'end': 77.301, 'text': 'so Since we are declaring a DP of size n and n plus 1 and assigning everything to 0, since everything is already assigned to 0,', 'start': 66.775, 'duration': 10.526}, {'end': 79.723, 'text': "we don't need to specifically write for the base case.", 'start': 77.301, 'duration': 2.422}, {'end': 80.703, 'text': 'I hope that makes sense.', 'start': 79.903, 'duration': 0.8}, {'end': 84.926, 'text': 'Next, write the changing parameters.', 'start': 81.784, 'duration': 3.142}, {'end': 89.569, 'text': 'So, if I look at the code, these are the couple of changing parameters that we have.', 'start': 85.166, 'duration': 4.403}, {'end': 92.931, 'text': 'So, write down the changing parameters in the opposite fashion.', 'start': 90.309, 'duration': 2.622}, {'end': 98.14, 'text': 'strict rules, easy rules, which we have been following right from the start.', 'start': 94.318, 'duration': 3.822}, {'end': 101.722, 'text': 'So, the index will be from n minus 1 to 0.', 'start': 98.76, 'duration': 2.962}, {'end': 107.585, 'text': 'The previous index will be from n minus 1 to minus 1.', 'start': 101.722, 'duration': 5.863}], 'summary': 'Converting recursive code to tabulated code, following dp rules, base case is if index==n, declare dp of n+1', 'duration': 79.274, 'max_score': 28.311, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc28311.jpg'}], 'start': 0.189, 'title': 'Tabulation approach for dynamic programming', 'summary': 'Discusses the rules and steps to convert recursive code into tabulated code, emphasizing declaring the dp array, defining the base case, and handling changing parameters.', 'chapters': [{'end': 136.909, 'start': 0.189, 'title': 'Tabulation approach for dynamic programming', 'summary': 'Discusses the tabulation approach for dynamic programming, emphasizing the rules and steps to convert recursive code into tabulated code, with a focus on declaring the dp array, defining the base case, and handling changing parameters.', 'duration': 136.72, 'highlights': ['The chapter emphasizes the rules for converting recursive code into tabulated code, including the declaration of the DP array, definition of the base case, and handling changing parameters.', 'The video delves into the process of declaring a DP array of size n plus 1 and writing the base case, which entails returning 0 when the index is equal to n.', 'It outlines the strict rules of writing changing parameters in the opposite fashion, following a specific pattern from n minus 1 to 0 for index and n minus 1 to -1 for the previous index.']}], 'duration': 136.72, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc189.jpg', 'highlights': ['The chapter emphasizes the rules for converting recursive code into tabulated code, including the declaration of the DP array, definition of the base case, and handling changing parameters.', 'The video delves into the process of declaring a DP array of size n plus 1 and writing the base case, which entails returning 0 when the index is equal to n.', 'It outlines the strict rules of writing changing parameters in the opposite fashion, following a specific pattern from n minus 1 to 0 for index and n minus 1 to -1 for the previous index.']}, {'end': 337.061, 'segs': [{'end': 207.1, 'src': 'embed', 'start': 136.909, 'weight': 0, 'content': [{'end': 142.01, 'text': 'next is copy the recurrence, as simple as it can get.', 'start': 136.909, 'duration': 5.101}, {'end': 153.095, 'text': 'copy the recurrence and make sure you follow the coordinate shift that i taught you, follow coordinate shift that i taught you.', 'start': 142.01, 'duration': 11.085}, {'end': 159.239, 'text': 'okay, just make sure you do follow, uh, the coordinate shift that i taught you.', 'start': 153.095, 'duration': 6.144}, {'end': 166.124, 'text': "so what i'll do is i will go across over here and this is how the code looks like and over here.", 'start': 159.239, 'duration': 6.885}, {'end': 175.13, 'text': "what i'll do is i'll do a 0, and this is the index which i'll start from n minus 1 index greater than equal to 0, index minus minus.", 'start': 166.124, 'duration': 9.006}, {'end': 181.012, 'text': "and i'll have the previous index right, starting from index minus one till, uh,", 'start': 175.13, 'duration': 5.882}, {'end': 187.974, 'text': 'previous index greater than equal to minus one and previous index minus minus, perfect.', 'start': 181.012, 'duration': 6.962}, {'end': 196.217, 'text': "and now what i'll do is i will simply take this portion and i'll copy paste over here once i've taken this.", 'start': 187.974, 'duration': 8.243}, {'end': 202.619, 'text': "now what i will do is i will be like okay, let's convert this into a dp.", 'start': 197.037, 'duration': 5.582}, {'end': 207.1, 'text': 'so remember, whenever you convert it into a dp, the coordinate shift has to be done.', 'start': 202.619, 'duration': 4.481}], 'summary': 'Teaching to copy recurrence with coordinate shift for coding.', 'duration': 70.191, 'max_score': 136.909, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc136909.jpg'}, {'end': 250.12, 'src': 'heatmap', 'start': 216.443, 'weight': 0.712, 'content': [{'end': 220.484, 'text': 'it is as it is and the second parameter goes into the plus one state.', 'start': 216.443, 'duration': 4.041}, {'end': 225.449, 'text': 'perfect, so we moved the second parameter into the plus one state Over here.', 'start': 220.484, 'duration': 4.965}, {'end': 226.89, 'text': 'this will go off.', 'start': 225.449, 'duration': 1.441}, {'end': 230.29, 'text': 'Over here, this will be DP of 0.', 'start': 227.53, 'duration': 2.76}, {'end': 232.231, 'text': 'And instead of minus 1, it will be a plus 1 state.', 'start': 230.29, 'duration': 1.941}, {'end': 234.791, 'text': 'So you just do a plus 1.', 'start': 232.811, 'duration': 1.98}, {'end': 240.032, 'text': 'Once you have done this, and if you try running this, you will see that this is indeed giving you the correct answer.', 'start': 234.791, 'duration': 5.241}, {'end': 241.672, 'text': 'No, it did not.', 'start': 241.212, 'duration': 0.46}, {'end': 247.514, 'text': "Why? Because you are at n minus 1, and you're doing an index plus 1.", 'start': 241.792, 'duration': 5.722}, {'end': 250.12, 'text': 'So make sure this is declared for n plus 1.', 'start': 247.514, 'duration': 2.606}], 'summary': 'Adjust parameter to plus one state for correct answer at n plus 1.', 'duration': 33.677, 'max_score': 216.443, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc216443.jpg'}, {'end': 301.556, 'src': 'embed', 'start': 270.263, 'weight': 2, 'content': [{'end': 275.547, 'text': "now. now, if you're following my dp lectures right from the start, you know the space optimization technique.", 'start': 270.263, 'duration': 5.284}, {'end': 281.852, 'text': 'yes, whenever you see something like index plus one, index plus one, what comes to your brain?', 'start': 275.547, 'duration': 6.305}, {'end': 285.213, 'text': 'yes, space optimization.', 'start': 281.852, 'duration': 3.361}, {'end': 287.754, 'text': "so what you'll do is you will just space optimize.", 'start': 285.213, 'duration': 2.541}, {'end': 294.835, 'text': "this, because in order to compute index, you're just requiring the next row, just the next row.", 'start': 287.754, 'duration': 7.081}, {'end': 301.556, 'text': 'so please, space of space, optimize this by saying next row, and you can also declare a current row of n plus one.', 'start': 294.835, 'duration': 6.721}], 'summary': 'Space optimize by using next row and declaring current row of n+1.', 'duration': 31.293, 'max_score': 270.263, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc270263.jpg'}], 'start': 136.909, 'title': 'Recurrence copy and dynamic programming', 'summary': 'Covers copying a recurrence using coordinate shift and converting code into dynamic programming, emphasizing time complexity of o(n) and including space optimization techniques.', 'chapters': [{'end': 187.974, 'start': 136.909, 'title': 'Recurrence copy and coordinate shift', 'summary': 'Covers the process of copying a recurrence by following a taught coordinate shift, which involves using a specific index and code structure.', 'duration': 51.065, 'highlights': ['The process involves copying a recurrence using a specific index structure starting from n minus 1 index, and following a taught coordinate shift.', 'The code structure includes starting from index minus one and iterating till the previous index is greater than or equal to minus one.', 'The emphasis is on following the taught coordinate shift and using specific index manipulation in the code.']}, {'end': 337.061, 'start': 187.974, 'title': 'Converting code into dynamic programming', 'summary': 'Discusses converting code into dynamic programming, including shifting coordinates, space optimization techniques, and ensuring correct index declarations, with emphasis on maintaining a time complexity of o(n).', 'duration': 149.087, 'highlights': ['The key point highlighted is the process of converting code into dynamic programming, which includes shifting coordinates and ensuring correct index declarations, with the emphasis on maintaining a time complexity of O(n).', 'Another important highlight is the space optimization technique used in dynamic programming to optimize memory usage by declaring next row and current row of n plus one.', 'The importance of ensuring correct index declarations is highlighted, particularly in relation to time complexity and ensuring the code runs correctly.']}], 'duration': 200.152, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc136909.jpg', 'highlights': ['The process involves copying a recurrence using a specific index structure starting from n minus 1 index, and following a taught coordinate shift.', 'The key point highlighted is the process of converting code into dynamic programming, which includes shifting coordinates and ensuring correct index declarations, with the emphasis on maintaining a time complexity of O(n).', 'The importance of ensuring correct index declarations is highlighted, particularly in relation to time complexity and ensuring the code runs correctly.', 'The code structure includes starting from index minus one and iterating till the previous index is greater than or equal to minus one.', 'The emphasis is on following the taught coordinate shift and using specific index manipulation in the code.', 'Another important highlight is the space optimization technique used in dynamic programming to optimize memory usage by declaring next row and current row of n plus one.']}, {'end': 610.379, 'segs': [{'end': 393.065, 'src': 'embed', 'start': 338.533, 'weight': 0, 'content': [{'end': 348.518, 'text': 'so in this way, what i have done is i have converted this code into something, uh, which is like if i show you, uh,', 'start': 338.533, 'duration': 9.985}, {'end': 356.061, 'text': 'the time complexity is still b go of n square, but the space complexity has been boiled down to n into 2..', 'start': 348.518, 'duration': 7.543}, {'end': 357.622, 'text': 'now. is this the best solution?', 'start': 356.061, 'duration': 1.561}, {'end': 365.459, 'text': 'no, the best solution uses a like weird method tabulation method, like i personally feel.', 'start': 357.622, 'duration': 7.837}, {'end': 367.06, 'text': 'if you know this, you know this.', 'start': 365.459, 'duration': 1.601}, {'end': 369.021, 'text': 'otherwise you cannot intuitively write it.', 'start': 367.06, 'duration': 1.961}, {'end': 370.422, 'text': 'that is what i feel.', 'start': 369.021, 'duration': 1.401}, {'end': 373.423, 'text': "so it's a tabulation method that you have to learn.", 'start': 370.422, 'duration': 3.001}, {'end': 374.864, 'text': "it's a different way.", 'start': 373.423, 'duration': 1.441}, {'end': 379.766, 'text': "so let's take a quick example and try to understand the tabulation method.", 'start': 374.864, 'duration': 4.902}, {'end': 380.106, 'text': 'so 5, 4, 11, 1, 16, 8.', 'start': 379.766, 'duration': 0.34}, {'end': 381.627, 'text': "okay, let's take this array.", 'start': 380.106, 'duration': 1.521}, {'end': 392.104, 'text': "okay. and now what I'll declare is I'll declare a dp of size n.", 'start': 387.478, 'duration': 4.626}, {'end': 393.065, 'text': "that is what I'll declare.", 'start': 392.104, 'duration': 0.961}], 'summary': 'Code optimized to reduce space complexity, but not the best solution. recommends learning tabulation method for improved performance.', 'duration': 54.532, 'max_score': 338.533, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc338533.jpg'}, {'end': 493.356, 'src': 'embed', 'start': 462.784, 'weight': 2, 'content': [{'end': 470.071, 'text': 'So, I can say it can have a length of 2 because either 5, 11, either 4, 11.', 'start': 462.784, 'duration': 7.287}, {'end': 475.265, 'text': 'It can still have a length of 2, right? Next, you go to 1.', 'start': 470.072, 'duration': 5.193}, {'end': 480.214, 'text': 'Can I have a longest increasing subsequence? Anyone before 1.', 'start': 475.265, 'duration': 4.949}, {'end': 481.557, 'text': '5 cannot be before 1.', 'start': 480.214, 'duration': 1.343}, {'end': 482.839, 'text': '4 cannot be before 1.', 'start': 481.557, 'duration': 1.282}, {'end': 484.282, 'text': '11 cannot be before 1.', 'start': 482.839, 'duration': 1.443}, {'end': 487.488, 'text': 'So the longest increasing subsequence will be of length 1 again.', 'start': 484.282, 'duration': 3.206}, {'end': 493.356, 'text': '16 For 16, I can say I can have 1 before 16.', 'start': 489.332, 'duration': 4.024}], 'summary': 'The transcript discusses the length of longest increasing subsequences, with specific examples.', 'duration': 30.572, 'max_score': 462.784, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc462784.jpg'}, {'end': 557.901, 'src': 'embed', 'start': 521.155, 'weight': 3, 'content': [{'end': 524.317, 'text': 'So I can have a length 3.', 'start': 521.155, 'duration': 3.162}, {'end': 528.279, 'text': 'For 8, can I have 16 before 8? No.', 'start': 524.317, 'duration': 3.962}, {'end': 529.88, 'text': 'Can I have 1 before 8? Yes.', 'start': 528.66, 'duration': 1.22}, {'end': 531.842, 'text': 'So 1 and 8 can be together.', 'start': 530.341, 'duration': 1.501}, {'end': 535.124, 'text': 'Can I have 11 and 8? No.', 'start': 533.202, 'duration': 1.922}, {'end': 536.445, 'text': 'Can I have 4 and 8? No.', 'start': 535.664, 'duration': 0.781}, {'end': 542.558, 'text': 'yes, so i can have one and eight, four and eight, five and eight.', 'start': 537.637, 'duration': 4.921}, {'end': 543.398, 'text': "i can't see.", 'start': 542.558, 'duration': 0.84}, {'end': 546.239, 'text': 'uh, more than length two, that end set over here.', 'start': 543.398, 'duration': 2.841}, {'end': 557.901, 'text': 'so i can still have a length two, thereby i know all the longest, like at 11 a length of two ends, at 16 a length of three ends.', 'start': 546.239, 'duration': 11.662}], 'summary': 'Numbers 1, 4, and 5 can be paired with 8, forming sets of length 2 or 3.', 'duration': 36.746, 'max_score': 521.155, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc521155.jpg'}, {'end': 610.379, 'src': 'embed', 'start': 576.08, 'weight': 4, 'content': [{'end': 579.565, 'text': 'Yes, I can have both of them as the length.', 'start': 576.08, 'duration': 3.485}, {'end': 594.112, 'text': "So I can have both of them, as the longest increasing subsequence and the LIS will be the max of all dpi's, max of all dp of index,", 'start': 581.041, 'duration': 13.071}, {'end': 598.276, 'text': 'where i ranges from 0 to n-1..', 'start': 594.112, 'duration': 4.164}, {'end': 603.433, 'text': 'This is the formula, but funda is how do you compute this portion?', 'start': 598.776, 'duration': 4.657}, {'end': 606.075, 'text': "that's important, that is, that is the key.", 'start': 603.433, 'duration': 2.642}, {'end': 610.379, 'text': "so you have figured out what's the uh thought process behind this algorithm.", 'start': 606.075, 'duration': 4.304}], 'summary': 'Algorithm computes max lis using dpis, with i ranging from 0 to n-1.', 'duration': 34.299, 'max_score': 576.08, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc576080.jpg'}], 'start': 338.533, 'title': 'Longest increasing subsequence', 'summary': 'Explains the tabulation method for finding the longest increasing subsequence and reducing space complexity to n*2, emphasizing the need to learn this method for better solutions. it also discusses different ways to form the subsequence and the concept of dynamic programming to compute the length of the subsequence for each index.', 'chapters': [{'end': 493.356, 'start': 338.533, 'title': 'Tabulation method explained', 'summary': 'Explains the tabulation method for finding the longest increasing subsequence, reducing space complexity to n*2, and emphasizes the need to learn this method for better solutions.', 'duration': 154.823, 'highlights': ['The tabulation method reduces space complexity to n*2 for finding the longest increasing subsequence, keeping time complexity at O(n^2).', 'Emphasizes the need to learn the tabulation method for better solutions, which may not be intuitive but can significantly improve the code.', 'Explanation of the longest increasing subsequence using the tabulation method, illustrating the process with specific elements and their respective subsequence lengths.']}, {'end': 610.379, 'start': 493.356, 'title': 'Finding longest increasing subsequence', 'summary': 'Discusses finding the longest increasing subsequence in a sequence of numbers, exploring different ways to form the subsequence and the concept of dynamic programming to compute the length of the subsequence for each index.', 'duration': 117.023, 'highlights': ['The longest increasing subsequence can be formed by picking 5, 11, and 16, resulting in a length of 3.', 'Exploring different combinations, it is observed that 1 and 8, 4 and 8, and 5 and 8 can be together, resulting in a length of 2.', 'The formula for finding the longest increasing subsequence involves dynamic programming, and the key is to compute the length of the subsequence for each index.']}], 'duration': 271.846, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc338533.jpg', 'highlights': ['The tabulation method reduces space complexity to n*2 for finding the longest increasing subsequence, keeping time complexity at O(n^2).', 'Emphasizes the need to learn the tabulation method for better solutions, which may not be intuitive but can significantly improve the code.', 'The longest increasing subsequence can be formed by picking 5, 11, and 16, resulting in a length of 3.', 'Exploring different combinations, it is observed that 1 and 8, 4 and 8, and 5 and 8 can be together, resulting in a length of 2.', 'The formula for finding the longest increasing subsequence involves dynamic programming, and the key is to compute the length of the subsequence for each index.', 'Explanation of the longest increasing subsequence using the tabulation method, illustrating the process with specific elements and their respective subsequence lengths.']}, {'end': 1027.239, 'segs': [{'end': 640.851, 'src': 'embed', 'start': 610.379, 'weight': 4, 'content': [{'end': 619.988, 'text': "so now let's again copy paste the same example of 5, 4, 11, 1, 16, 8, and now let's try to figure out the dp.", 'start': 610.379, 'duration': 9.609}, {'end': 623.712, 'text': "okay, So what I'll do is have a keen focus.", 'start': 619.988, 'duration': 3.724}, {'end': 625.375, 'text': 'I know one thing for sure.', 'start': 624.293, 'duration': 1.082}, {'end': 629.321, 'text': 'Even if there does not exist any element before that.', 'start': 626.096, 'duration': 3.225}, {'end': 635.271, 'text': 'I repeat, even if there does not exist any element before that, I know the length will always be one.', 'start': 629.321, 'duration': 5.95}, {'end': 640.851, 'text': 'the max length will be one, he itself itself.', 'start': 636.687, 'duration': 4.164}], 'summary': 'Using dynamic programming to find max length of a sequence with specific numbers.', 'duration': 30.472, 'max_score': 610.379, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc610379.jpg'}, {'end': 766.725, 'src': 'embed', 'start': 738.102, 'weight': 0, 'content': [{'end': 741.404, 'text': 'Like I know there is a subsequence of length 1.', 'start': 738.102, 'duration': 3.302}, {'end': 744.346, 'text': 'LIS There is an LIS of length 1 that ends at 4.', 'start': 741.404, 'duration': 2.942}, {'end': 745.787, 'text': 'So can this be with 11? Yes.', 'start': 744.346, 'duration': 1.441}, {'end': 749.936, 'text': 'This plus 1 is 2.', 'start': 747.915, 'duration': 2.021}, {'end': 751.477, 'text': 'That is already 2.', 'start': 749.936, 'duration': 1.541}, {'end': 754.158, 'text': 'So, no need to update it because I already have a length 2.', 'start': 751.477, 'duration': 2.681}, {'end': 755.919, 'text': "Perfect Let's move ahead.", 'start': 754.158, 'duration': 1.761}, {'end': 758.801, 'text': "3 So, I'm moving ahead to this index.", 'start': 755.939, 'duration': 2.862}, {'end': 761.122, 'text': 'Now, I have a 1.', 'start': 759.621, 'duration': 1.501}, {'end': 763.643, 'text': 'Can this be apart with 1? No.', 'start': 761.122, 'duration': 2.521}, {'end': 766.725, 'text': 'Can this be apart with 1? No.', 'start': 764.404, 'duration': 2.321}], 'summary': 'Finding the longest increasing subsequence, reaching length 2 at index 4.', 'duration': 28.623, 'max_score': 738.102, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc738102.jpg'}, {'end': 894.261, 'src': 'embed', 'start': 863.715, 'weight': 1, 'content': [{'end': 866.779, 'text': 'So this is how you fill up the entire DP table.', 'start': 863.715, 'duration': 3.064}, {'end': 871.846, 'text': "Once you have filled up the entire DP table, figure out the maximum and that's 3.", 'start': 867.48, 'duration': 4.366}, {'end': 873.829, 'text': 'And that is going to be your LIS.', 'start': 871.846, 'duration': 1.983}, {'end': 876.773, 'text': 'That is going to be your length of LIS.', 'start': 874.309, 'duration': 2.464}, {'end': 879.576, 'text': 'So can I say, what am I doing?', 'start': 877.794, 'duration': 1.782}, {'end': 885.916, 'text': "can I say I'm actually starting from index 0 and I'm going on till index minus 1.", 'start': 880.353, 'duration': 5.563}, {'end': 887.157, 'text': "that's what I'm doing.", 'start': 885.916, 'duration': 1.241}, {'end': 890.239, 'text': "I'm starting from 0 and I'm going till n minus 1.", 'start': 887.157, 'duration': 3.082}, {'end': 894.261, 'text': "and whenever I'm standing at, let's say, 16, I checked for 5, 4, 11, 1.", 'start': 890.239, 'duration': 4.022}], 'summary': 'Filling dp table yields lis of length 3, starting from index 0 to n-1.', 'duration': 30.546, 'max_score': 863.715, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc863715.jpg'}, {'end': 1035.489, 'src': 'embed', 'start': 1006.32, 'weight': 3, 'content': [{'end': 1009.743, 'text': 'whenever all the dp of i is computed and then i can return the maximum.', 'start': 1006.32, 'duration': 3.423}, {'end': 1015.527, 'text': "that's how, uh, this particular algorithm will be and it's a very straightforward one.", 'start': 1010.441, 'duration': 5.086}, {'end': 1019.931, 'text': "so yeah, again, ydp, because you're storing the previous states.", 'start': 1015.527, 'duration': 4.404}, {'end': 1023.175, 'text': "that's how you can easily do this lis.", 'start': 1019.931, 'duration': 3.244}, {'end': 1027.239, 'text': 'now, if i ask you the time complexity again, if i submit this, you will see it will be giving you a tle,', 'start': 1023.175, 'duration': 4.064}, {'end': 1031.925, 'text': 'because the time complexity is still n squared.', 'start': 1028.22, 'duration': 3.705}, {'end': 1035.489, 'text': 'yeah, if i talk about the time complexity, it is still.', 'start': 1031.925, 'duration': 3.564}], 'summary': 'Algorithm computes maximum dp of i, has time complexity of n squared.', 'duration': 29.169, 'max_score': 1006.32, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc1006320.jpg'}], 'start': 610.379, 'title': 'Finding longest increasing subsequence', 'summary': 'Explains how to find the longest increasing subsequence (lis) in a given sequence using dynamic programming, with a detailed example and a step-by-step approach. it determines the length of the longest increasing subsequence (lis) in a given sequence, and explains the time complexity.', 'chapters': [{'end': 663.263, 'start': 610.379, 'title': 'Dynamic programming example', 'summary': "Explains a dynamic programming example using an array and illustrates how to determine the length of the longest subsequence, with a key emphasis on the initial values of the dynamic programming array and the impact of previous elements on the current element's length.", 'duration': 52.884, 'highlights': ['The initial values of the dynamic programming array are all set to one, indicating that even if there are no previous elements, the length of the subsequence will be one.', 'The chapter emphasizes the impact of previous elements on the length of the current element, demonstrating the process of determining the maximum length of the subsequence based on the presence of previous elements.']}, {'end': 1027.239, 'start': 663.263, 'title': 'Finding longest increasing subsequence', 'summary': 'Explains how to find the longest increasing subsequence (lis) in a given sequence using dynamic programming, with a detailed example and a step-by-step approach. the algorithm determines the length of the longest increasing subsequence (lis) in a given sequence, and the time complexity is explained.', 'duration': 363.976, 'highlights': ['The algorithm determines the length of the longest increasing subsequence (LIS) in a given sequence, and the time complexity is explained.', 'The process involves iterating through the elements and checking the previous elements to determine the longest increasing subsequence (LIS), with examples of the comparisons and updates.', 'A step-by-step approach is detailed, including examples of how each element is evaluated and updated to find the longest increasing subsequence (LIS) and the use of dynamic programming to store previous states and determine the maximum.', 'The time complexity of the algorithm is discussed, with considerations for efficient implementation and potential challenges such as time limit exceeded (TLE) errors.']}], 'duration': 416.86, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc610379.jpg', 'highlights': ['The algorithm determines the length of the longest increasing subsequence (LIS) in a given sequence, and the time complexity is explained.', 'A step-by-step approach is detailed, including examples of how each element is evaluated and updated to find the longest increasing subsequence (LIS) and the use of dynamic programming to store previous states and determine the maximum.', 'The process involves iterating through the elements and checking the previous elements to determine the longest increasing subsequence (LIS), with examples of the comparisons and updates.', 'The time complexity of the algorithm is discussed, with considerations for efficient implementation and potential challenges such as time limit exceeded (TLE) errors.', 'The initial values of the dynamic programming array are all set to one, indicating that even if there are no previous elements, the length of the subsequence will be one.', 'The chapter emphasizes the impact of previous elements on the length of the current element, demonstrating the process of determining the maximum length of the subsequence based on the presence of previous elements.']}, {'end': 1547.325, 'segs': [{'end': 1105.277, 'src': 'embed', 'start': 1028.22, 'weight': 0, 'content': [{'end': 1031.925, 'text': 'because the time complexity is still n squared.', 'start': 1028.22, 'duration': 3.705}, {'end': 1035.489, 'text': 'yeah, if i talk about the time complexity, it is still.', 'start': 1031.925, 'duration': 3.564}, {'end': 1040.114, 'text': 'we go of n squared, but the space complexity has now boiled down to.', 'start': 1035.489, 'duration': 4.625}, {'end': 1041.435, 'text': 'we go often.', 'start': 1040.114, 'duration': 1.321}, {'end': 1044.118, 'text': 'now, this solution will be required.', 'start': 1041.435, 'duration': 2.683}, {'end': 1047.782, 'text': 'if you want to trace back the l is.', 'start': 1044.118, 'duration': 3.664}, {'end': 1053.383, 'text': 'If you want to trace back the alias, this solution will be required.', 'start': 1049.181, 'duration': 4.202}, {'end': 1056.764, 'text': "So it's time that we now trace back the alias.", 'start': 1053.663, 'duration': 3.101}, {'end': 1059.546, 'text': "Now we'll be learning how to print the alias.", 'start': 1057.105, 'duration': 2.441}, {'end': 1060.326, 'text': "That's very important.", 'start': 1059.586, 'duration': 0.74}, {'end': 1061.767, 'text': "So let's learn how to print the alias.", 'start': 1060.346, 'duration': 1.421}, {'end': 1066.529, 'text': 'So till now we have understood how to figure out the length of the alias.', 'start': 1062.207, 'duration': 4.322}, {'end': 1072.991, 'text': 'But what if someone comes up and says, hey, can you print me the alias? Can you actually print the alias? We can.', 'start': 1067.009, 'duration': 5.982}, {'end': 1079.849, 'text': 'What if we apply some backtrack? Can we print it? We can.', 'start': 1073.732, 'duration': 6.117}, {'end': 1086.333, 'text': 'So the backtrack that we will do is, what we will do is, as of now we were creating a DP array.', 'start': 1080.37, 'duration': 5.963}, {'end': 1092.517, 'text': 'If you remember well, we were creating a DP array and we were initially saying everyone to be one right?', 'start': 1086.393, 'duration': 6.124}, {'end': 1096.76, 'text': "Now let's create one backtrack array, another array.", 'start': 1093.278, 'duration': 3.482}, {'end': 1103.514, 'text': 'Okay, you can call whatever you can just name it as hash or something others.', 'start': 1098.226, 'duration': 5.288}, {'end': 1105.277, 'text': "So let's create one more array.", 'start': 1104.175, 'duration': 1.102}], 'summary': 'Time complexity is still n squared, space complexity reduced. learning to print aliases and applying backtracking.', 'duration': 77.057, 'max_score': 1028.22, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc1028220.jpg'}, {'end': 1323.529, 'src': 'heatmap', 'start': 1276.172, 'weight': 0.816, 'content': [{'end': 1279.852, 'text': 'same 11 no, 1, 1 plus 1, 2, 16.', 'start': 1276.172, 'duration': 3.68}, {'end': 1289.515, 'text': 'no, so apparently your hash array is storing something like this, and the maximum value you got was at this index, index 4.', 'start': 1279.852, 'duration': 9.663}, {'end': 1293.858, 'text': 'so you start at index 4, take up that value 16.', 'start': 1289.515, 'duration': 4.343}, {'end': 1299.922, 'text': 'next you go to the previous index and you can easily get by hash, which is 2.', 'start': 1293.858, 'duration': 6.064}, {'end': 1302.364, 'text': 'so you go to 2.', 'start': 1299.922, 'duration': 2.442}, {'end': 1305.346, 'text': 'so at the second index you see a value 0.', 'start': 1302.364, 'duration': 2.982}, {'end': 1307.333, 'text': 'so you go to 0.', 'start': 1305.346, 'duration': 1.987}, {'end': 1308.775, 'text': 'at zero you see zero itself.', 'start': 1307.333, 'duration': 1.442}, {'end': 1309.756, 'text': 'so you stop.', 'start': 1308.775, 'duration': 0.981}, {'end': 1312.198, 'text': 'so apparently index 4 has 16.', 'start': 1309.756, 'duration': 2.442}, {'end': 1313.379, 'text': 'index 2 has 11.', 'start': 1312.198, 'duration': 1.181}, {'end': 1314.5, 'text': 'index 0 has 5.', 'start': 1313.379, 'duration': 1.121}, {'end': 1320.767, 'text': "so if you reverse it, it's 5, 11, 16 which is your answer.", 'start': 1314.5, 'duration': 6.267}, {'end': 1323.529, 'text': 'in this way you can easily get your answer.', 'start': 1320.767, 'duration': 2.762}], 'summary': 'The sequence 11, 1, 1 plus 1, 2, 16 leads to the reverse sequence 5, 11, 16.', 'duration': 47.357, 'max_score': 1276.172, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc1276172.jpg'}, {'end': 1387.962, 'src': 'heatmap', 'start': 1336.156, 'weight': 0.747, 'content': [{'end': 1343.177, 'text': 'okay, and what you need to do at the next step is just go across whenever this is getting updated.', 'start': 1336.156, 'duration': 7.021}, {'end': 1356.977, 'text': "so instead of writing this, you can simply write and, and whenever this guy is greater than dp of i, i know i'll update this to this portion.", 'start': 1343.177, 'duration': 13.8}, {'end': 1361.985, 'text': "at the same time i'll say hash of i to store the previous guy perfect.", 'start': 1356.977, 'duration': 5.008}, {'end': 1377.65, 'text': 'and over here you can definitely keep the last index as 1 as 0 initially and whenever, yes, whenever dp of i exceeds maximum,', 'start': 1361.985, 'duration': 15.665}, {'end': 1385.841, 'text': 'you can simply say maximum to be dp of i and the last index to be i.', 'start': 1377.65, 'duration': 8.191}, {'end': 1387.962, 'text': 'so you have stored the last index.', 'start': 1385.841, 'duration': 2.121}], 'summary': 'Update dp and hash of i when dp[i] exceeds maximum; store last index.', 'duration': 51.806, 'max_score': 1336.156, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc1336156.jpg'}, {'end': 1432.319, 'src': 'embed', 'start': 1401.051, 'weight': 5, 'content': [{'end': 1403.592, 'text': 'in this way you can just bump up and over here.', 'start': 1401.051, 'duration': 2.541}, {'end': 1413.8, 'text': 'probably you can say int lis and you know the this is the length right and lias of zero will be nothing but array of last index.', 'start': 1403.592, 'duration': 10.208}, {'end': 1415.723, 'text': "that's the last guy.", 'start': 1413.8, 'duration': 1.923}, {'end': 1426.074, 'text': 'and over here what you can do is you can say last index to bump up to hash of last index and you can say lias of like.', 'start': 1415.723, 'duration': 10.351}, {'end': 1432.319, 'text': 'you can probably keep an index equal to zero, index equal to one because the first index has been done so.', 'start': 1426.074, 'duration': 6.245}], 'summary': 'Demonstrates array manipulation in a code snippet.', 'duration': 31.268, 'max_score': 1401.051, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc1401051.jpg'}], 'start': 1028.22, 'title': 'Backtracking techniques', 'summary': 'Covers the use of backtracking for printing aliases and finding the longest increasing subsequence (lis) in an array. it emphasizes reducing space complexity to o(n) while maintaining time complexity of o(n^2) and discusses the importance of tracing back aliases and learning to print them, as well as the use of a hash array to store previous indices and backtracking to obtain the lis. the time complexity for both cases is o(n^2).', 'chapters': [{'end': 1079.849, 'start': 1028.22, 'title': 'Printing aliases backtracking', 'summary': 'Introduces a solution for printing aliases using backtracking, reducing space complexity to o(n) while maintaining time complexity of o(n^2). it emphasizes the importance of tracing back aliases and learning to print them.', 'duration': 51.629, 'highlights': ['The solution reduces space complexity to O(n) while maintaining time complexity of O(n^2), making it essential for tracing back and printing aliases.', 'Emphasizes the importance of tracing back aliases and learning how to print them, following the understanding of alias length calculation.', 'Introduces the concept of using backtracking to print aliases, providing a solution for the query of printing aliases.']}, {'end': 1547.325, 'start': 1080.37, 'title': 'Backtracking for longest increasing subsequence', 'summary': 'Discusses the backtracking process for finding the longest increasing subsequence (lis) in an array, using a hash array to store the previous indices and then backtracking to obtain the lis. the time complexity is o(n^2) and the space complexity is the length of the lis.', 'duration': 466.955, 'highlights': ['The backtracking process involves creating a hash array to store the previous indices of the given elements, thereby facilitating the backtracking to obtain the Longest Increasing Subsequence (LIS).', 'The time complexity for the backtracking process is O(n^2), where n is the length of the input array, and the space complexity is determined by the length of the obtained LIS.', 'The process involves iterating through the elements of the array, updating the hash array, and backtracking from the maximum value in the hash array to obtain the LIS in reverse order.', 'The chapter concludes with a call to action inviting viewers to like the video and subscribe to the channel, followed by a preview of the next video on solving LIS using binary search.']}], 'duration': 519.105, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/IFfYfonAFGc/pics/IFfYfonAFGc1028220.jpg', 'highlights': ['The solution reduces space complexity to O(n) while maintaining time complexity of O(n^2), making it essential for tracing back and printing aliases.', 'The backtracking process involves creating a hash array to store the previous indices of the given elements, thereby facilitating the backtracking to obtain the Longest Increasing Subsequence (LIS).', 'Emphasizes the importance of tracing back aliases and learning how to print them, following the understanding of alias length calculation.', 'Introduces the concept of using backtracking to print aliases, providing a solution for the query of printing aliases.', 'The time complexity for the backtracking process is O(n^2), where n is the length of the input array, and the space complexity is determined by the length of the obtained LIS.', 'The process involves iterating through the elements of the array, updating the hash array, and backtracking from the maximum value in the hash array to obtain the LIS in reverse order.']}], 'highlights': ['The tabulation method reduces space complexity to n*2 for finding the longest increasing subsequence, keeping time complexity at O(n^2).', 'The solution reduces space complexity to O(n) while maintaining time complexity of O(n^2), making it essential for tracing back and printing aliases.', 'The chapter emphasizes the rules for converting recursive code into tabulated code, including the declaration of the DP array, definition of the base case, and handling changing parameters.', 'The process involves copying a recurrence using a specific index structure starting from n minus 1 index, and following a taught coordinate shift.', 'The video delves into the process of declaring a DP array of size n plus 1 and writing the base case, which entails returning 0 when the index is equal to n.', 'The process involves iterating through the elements and checking the previous elements to determine the longest increasing subsequence (LIS), with examples of the comparisons and updates.']}