title
DP 11. Triangle | Fixed Starting Point and Variable Ending Point | DP on GRIDS

description
Lecture Notes/C++/Java Codes: https://takeuforward.org/data-structure/minimum-path-sum-in-triangular-grid-dp-11/ Problem Link: https://bit.ly/3K1cvqv 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 problem triangle which teaches you about solving DP on Grids when we have Fixed Starting and Variable Ending Points. 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 11. Triangle | Fixed Starting Point and Variable Ending Point | DP on GRIDS', 'heatmap': [{'end': 821.072, 'start': 785.763, 'weight': 0.784}, {'end': 999.861, 'start': 934.646, 'weight': 0.719}, {'end': 1235.277, 'start': 1119.269, 'weight': 0.819}, {'end': 1309.812, 'start': 1247.248, 'weight': 0.798}, {'end': 1372.694, 'start': 1322.807, 'weight': 1}, {'end': 1480.715, 'start': 1454.814, 'weight': 0.728}], 'summary': "Lecture covers dynamic programming lecture 11, solving the 'triangle' problem and finding the minimum path sum in a triangle array with n rows, emphasizing variable starting and ending points, exploring all possible paths in grids, implementing dynamic programming logic, addressing time and space complexity, and optimizing memory usage for reduced space complexity.", 'chapters': [{'end': 283.762, 'segs': [{'end': 90.195, 'src': 'embed', 'start': 0.509, 'weight': 0, 'content': [{'end': 1.85, 'text': 'Hey viewers, welcome back to the channel.', 'start': 0.509, 'duration': 1.341}, {'end': 3.652, 'text': 'I hope you guys are doing extremely well.', 'start': 1.85, 'duration': 1.802}, {'end': 7.174, 'text': 'so this is the 11th lecture of the dynamic programming playlist.', 'start': 3.652, 'duration': 3.522}, {'end': 16.921, 'text': 'yes, till now we have done DP on grids like we have done three problems on the DP on grids, where there was a shuttle pattern,', 'start': 7.174, 'duration': 9.747}, {'end': 25.447, 'text': 'where we always stated that the starting point is 0, 0 and the ending point is n minus 1 and m minus 1.', 'start': 16.921, 'duration': 8.526}, {'end': 27.87, 'text': 'This was the pattern of questions that we have done.', 'start': 25.447, 'duration': 2.423}, {'end': 30.673, 'text': "Now going forward, I'll be solving three problems.", 'start': 28.29, 'duration': 2.383}, {'end': 36.079, 'text': 'Yes, three problems where we will be having variable starting points.', 'start': 30.753, 'duration': 5.326}, {'end': 40.304, 'text': 'Yes, might be there like there might be a variable or a fixed starting point.', 'start': 36.099, 'duration': 4.205}, {'end': 43.622, 'text': 'the ending point will also be variable.', 'start': 40.919, 'duration': 2.703}, {'end': 47.586, 'text': 'when we will see the questions, you will understand what does variable mean.', 'start': 43.622, 'duration': 3.964}, {'end': 49.868, 'text': 'but yeah, the variable it will be variable.', 'start': 47.586, 'duration': 2.282}, {'end': 53.151, 'text': "that's that's going to be the next set of three questions.", 'start': 49.868, 'duration': 3.283}, {'end': 58.497, 'text': 'so, in order to start off, we will be taking the first question, which is triangle.', 'start': 53.151, 'duration': 5.346}, {'end': 61.56, 'text': "so yeah, without without wasting any time, let's get started, keep in.", 'start': 58.497, 'duration': 3.063}, {'end': 64.885, 'text': 'It states that you are given a triangular array.', 'start': 62.105, 'duration': 2.78}, {'end': 66.166, 'text': "that's basically a triangle.", 'start': 64.885, 'duration': 1.281}, {'end': 71.348, 'text': 'Your task is to return the minimum path sum to reach from the top till the bottom row.', 'start': 66.607, 'duration': 4.741}, {'end': 78.331, 'text': 'The triangle array will have n rows and the ith row will have i plus 1 elements.', 'start': 72.009, 'duration': 6.322}, {'end': 79.251, 'text': "So let's understand this.", 'start': 78.351, 'duration': 0.9}, {'end': 85.633, 'text': 'So basically there will be n rows and the ith row will be having i plus 1 elements.', 'start': 79.591, 'duration': 6.042}, {'end': 90.195, 'text': 'Now you can move only to adjacent number of row below each step.', 'start': 85.653, 'duration': 4.542}], 'summary': '11th lecture on dynamic programming, solving 3 problems with variable starting and ending points, first problem is triangle array with n rows and i+1 elements per row.', 'duration': 89.686, 'max_score': 0.509, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0509.jpg'}, {'end': 199.316, 'src': 'embed', 'start': 172.122, 'weight': 3, 'content': [{'end': 179.527, 'text': 'the ending point might vary, because what they are concerned is as long as you are reaching the last row, you can either reach here.', 'start': 172.122, 'duration': 7.405}, {'end': 181.404, 'text': 'You can either reach here.', 'start': 180.063, 'duration': 1.341}, {'end': 183.205, 'text': 'or you can either reach here, or you can either reach here.', 'start': 181.404, 'duration': 1.801}, {'end': 187.928, 'text': "As long as you're reaching the ending row, we are satisfied.", 'start': 183.726, 'duration': 4.202}, {'end': 193.632, 'text': 'And in order to reach from the first row till the last row, there might be a path.', 'start': 188.309, 'duration': 5.323}, {'end': 199.316, 'text': 'How many different paths can be there? You might go from here to here, then from here to here, then from here to here.', 'start': 193.672, 'duration': 5.644}], 'summary': 'There are multiple paths from the first to the last row, with the number of different paths being uncertain.', 'duration': 27.194, 'max_score': 172.122, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0172122.jpg'}, {'end': 293.367, 'src': 'embed', 'start': 265.195, 'weight': 5, 'content': [{'end': 269.837, 'text': 'so uniformity is not there, because the values might be bigger, might be lesser.', 'start': 265.195, 'duration': 4.642}, {'end': 279.841, 'text': 'so whenever there is no uniformity in the increment of values or decrement of values, then we can see that something like a greedy cannot be applied.', 'start': 269.837, 'duration': 10.004}, {'end': 281.802, 'text': 'something like a greedy cannot be applied.', 'start': 279.841, 'duration': 1.961}, {'end': 283.762, 'text': 'so what do we tend to apply over there?', 'start': 281.802, 'duration': 1.96}, {'end': 293.367, 'text': 'yes, we try out all the paths, we try out all the paths, right, and how do you do that?', 'start': 283.762, 'duration': 9.605}], 'summary': 'Uniformity in value increments affects application of greedy algorithm. all paths are tried for non-uniform increments.', 'duration': 28.172, 'max_score': 265.195, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0265195.jpg'}], 'start': 0.509, 'title': 'Solving triangle problem with dynamic programming', 'summary': "Covers dynamic programming lecture 11, focusing on solving the 'triangle' problem and finding the minimum path sum in a triangle array with n rows, emphasizing variable starting and ending points, and adjacent number movement.", 'chapters': [{'end': 66.166, 'start': 0.509, 'title': 'Dynamic programming lecture 11: triangle problem', 'summary': "Introduces the 11th lecture of the dynamic programming playlist, focusing on solving three problems involving variable starting points and variable ending points, with a specific emphasis on the 'triangle' problem.", 'duration': 65.657, 'highlights': ['The lecture introduces the transition from DP on grids to solving problems with variable starting and ending points.', 'The upcoming set of three problems will involve variable starting points and ending points, presenting a new challenge in dynamic programming.', "The first problem to be addressed is the 'triangle' problem, which involves working with a triangular array."]}, {'end': 283.762, 'start': 66.607, 'title': 'Minimum path sum in triangle', 'summary': 'Discusses finding the minimum path sum in a triangle array with n rows, where movement is only allowed to adjacent numbers in the row below, and the minimum path sum needs to be identified among the different paths from the top to the bottom row.', 'duration': 217.155, 'highlights': ['The triangle array has n rows and the ith row will have i plus 1 elements, with movement allowed only to adjacent numbers in the row below, leading to the identification of the minimum path sum among the different paths from the top to the bottom row.', 'The starting point is fixed, but the ending point may vary, with the goal being to reach the last row through different paths, and identifying the path with the minimum path sum.', 'Uniformity concept is discussed to highlight that a greedy solution may fail due to non-uniform values, making it unsuitable for this problem.']}], 'duration': 283.253, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0509.jpg', 'highlights': ['The triangle array has n rows and the ith row will have i plus 1 elements, with movement allowed only to adjacent numbers in the row below, leading to the identification of the minimum path sum among the different paths from the top to the bottom row.', 'The lecture introduces the transition from DP on grids to solving problems with variable starting and ending points.', 'The upcoming set of three problems will involve variable starting points and ending points, presenting a new challenge in dynamic programming.', 'The starting point is fixed, but the ending point may vary, with the goal being to reach the last row through different paths, and identifying the path with the minimum path sum.', "The first problem to be addressed is the 'triangle' problem, which involves working with a triangular array.", 'Uniformity concept is discussed to highlight that a greedy solution may fail due to non-uniform values, making it unsuitable for this problem.']}, {'end': 424.614, 'segs': [{'end': 324.675, 'src': 'embed', 'start': 302.692, 'weight': 0, 'content': [{'end': 310.936, 'text': "what you need to do is you need to find the path which gives you the minimum sum, and once you've done this, you're done so in the grid problems.", 'start': 302.692, 'duration': 8.244}, {'end': 311.877, 'text': 'what have i told you?', 'start': 310.936, 'duration': 0.941}, {'end': 316.549, 'text': "i've told you represent everything in terms of indexes.", 'start': 311.877, 'duration': 4.672}, {'end': 318.33, 'text': 'and what are the indexes over here?', 'start': 316.549, 'duration': 1.781}, {'end': 322.733, 'text': 'i enjoy, because in a grid we will always have the row number and the column number.', 'start': 318.33, 'duration': 4.403}, {'end': 324.675, 'text': 'what is the next thing that i have told you?', 'start': 322.733, 'duration': 1.942}], 'summary': 'Find path with minimum sum using grid indexes.', 'duration': 21.983, 'max_score': 302.692, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0302692.jpg'}, {'end': 424.614, 'src': 'embed', 'start': 377.648, 'weight': 2, 'content': [{'end': 380.67, 'text': 'so there is no fixed ending point.', 'start': 377.648, 'duration': 3.022}, {'end': 391.478, 'text': 'so logically it will not make sense if I write the recurrence, because i might be ending here, i might be ending here.', 'start': 380.67, 'duration': 10.808}, {'end': 400.68, 'text': 'so there can be four different recurrence one that starts from here, the other that starts from here, the other that starts from here,', 'start': 391.478, 'duration': 9.202}, {'end': 402.16, 'text': 'the other that starts from here.', 'start': 400.68, 'duration': 1.48}, {'end': 404.321, 'text': 'there will be four different kind of recurrence.', 'start': 402.16, 'duration': 2.161}, {'end': 410.102, 'text': 'in the previous video there was only one recurrence that you called and you got the answer.', 'start': 404.321, 'duration': 5.781}, {'end': 413.143, 'text': 'but over here you have to call four different recurrence.', 'start': 410.102, 'duration': 3.041}, {'end': 419.506, 'text': 'one is from here, one is from here, one is from here, one is from here, and In all the four recurrence,', 'start': 413.143, 'duration': 6.363}, {'end': 423.372, 'text': 'whichever recurrence gives you the minimum path.', 'start': 419.506, 'duration': 3.866}, {'end': 424.614, 'text': 'that will be your answer right.', 'start': 423.372, 'duration': 1.242}], 'summary': 'Four different recurrences are called to find the minimum path.', 'duration': 46.966, 'max_score': 377.648, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0377648.jpg'}], 'start': 283.762, 'title': 'Finding minimum sum paths in grids', 'summary': 'Discusses using recursion and indexes to find the minimum sum path in a grid, emphasizing the exploration of all possible paths to determine the optimal solution.', 'chapters': [{'end': 424.614, 'start': 283.762, 'title': 'Finding minimum sum paths in grids', 'summary': 'Discusses finding the minimum sum path in a grid using recursion and indexes, emphasizing the exploration of all possible paths to determine the optimal solution.', 'duration': 140.852, 'highlights': ['The approach involves exploring all possible paths in a grid to find the minimum sum, accomplished through recursion and representation in terms of indexes.', 'Emphasizes the importance of representing everything in terms of indexes, particularly using row and column numbers in a grid for clarity and precision.', 'The challenge of not having a fixed ending point in the grid is highlighted, leading to the need for multiple different recurrences to account for the various possible endpoints.', 'The need to call and evaluate four different recurrences to determine the minimum path in scenarios where there is no fixed ending point is explained.']}], 'duration': 140.852, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0283762.jpg', 'highlights': ['The approach involves exploring all possible paths in a grid to find the minimum sum, accomplished through recursion and representation in terms of indexes.', 'Emphasizes the importance of representing everything in terms of indexes, particularly using row and column numbers in a grid for clarity and precision.', 'The challenge of not having a fixed ending point in the grid is highlighted, leading to the need for multiple different recurrences to account for the various possible endpoints.', 'The need to call and evaluate four different recurrences to determine the minimum path in scenarios where there is no fixed ending point is explained.']}, {'end': 743.594, 'segs': [{'end': 511.753, 'src': 'embed', 'start': 483.826, 'weight': 0, 'content': [{'end': 486.747, 'text': 'it can start from 0, 0 and go till the last row.', 'start': 483.826, 'duration': 2.921}, {'end': 492.848, 'text': 'so we have figured out that the recurrence has to start from, instead of f of n, minus 1, m minus 1.', 'start': 486.747, 'duration': 6.101}, {'end': 495.469, 'text': 'we know the recurrence will start from 0, comma 0.', 'start': 492.848, 'duration': 2.621}, {'end': 499.27, 'text': "that is something which we have figured out and i've told you the reason right.", 'start': 495.469, 'duration': 3.801}, {'end': 500.75, 'text': "it's time to write the recurrence.", 'start': 499.27, 'duration': 1.48}, {'end': 504.491, 'text': 'so we know the recurrence is something like i, comma j correct.', 'start': 500.75, 'duration': 3.741}, {'end': 507.39, 'text': 'so what do we initially write?', 'start': 504.949, 'duration': 2.441}, {'end': 511.753, 'text': "if i'm writing this represent ij, then you have to write the base case.", 'start': 507.39, 'duration': 4.363}], 'summary': 'Recurrence starts from 0,0 to last row. recurrence represented by i, j. base case must be written.', 'duration': 27.927, 'max_score': 483.826, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0483826.jpg'}, {'end': 633.172, 'src': 'embed', 'start': 602.188, 'weight': 1, 'content': [{'end': 603.628, 'text': 'Does this guy have a diagonal? Yes.', 'start': 602.188, 'duration': 1.44}, {'end': 605.069, 'text': "We've reached the last row.", 'start': 604.008, 'duration': 1.061}, {'end': 611.512, 'text': 'So I know no matter how you move, because we can only move down and diagonal, we will never.', 'start': 605.489, 'duration': 6.023}, {'end': 615.052, 'text': 'never go outside this boundary.', 'start': 613.129, 'duration': 1.923}, {'end': 618.878, 'text': 'so we know that there will be no out outside boundary condition.', 'start': 615.052, 'duration': 3.826}, {'end': 621.101, 'text': 'so there is only one base case.', 'start': 618.878, 'duration': 2.223}, {'end': 624.806, 'text': 'so step one completed.', 'start': 621.101, 'duration': 3.705}, {'end': 630.512, 'text': 'now step two explore all the paths And we know we are looking for minimum path sum.', 'start': 624.806, 'duration': 5.706}, {'end': 633.172, 'text': 'What kind of path is there? One is this.', 'start': 631.012, 'duration': 2.16}], 'summary': 'Identifying minimum path sum in a diagonal grid with one base case and exploration of all paths.', 'duration': 30.984, 'max_score': 602.188, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0602188.jpg'}, {'end': 743.594, 'src': 'embed', 'start': 715.694, 'weight': 2, 'content': [{'end': 719.335, 'text': 'So what we have done, the next step is also done, explore all the paths.', 'start': 715.694, 'duration': 3.641}, {'end': 723.118, 'text': 'what is the third step, minimal of all the paths?', 'start': 719.835, 'duration': 3.283}, {'end': 736.589, 'text': 'yes, so can i say i will return the minimal of d and dg, which is down and diagonal, so i can just complete the function.', 'start': 723.118, 'duration': 13.471}, {'end': 741.513, 'text': 'this is how the recurrence will be pretty straightforward, right.', 'start': 736.589, 'duration': 4.924}, {'end': 743.594, 'text': 'so we have written down the recurrence.', 'start': 741.513, 'duration': 2.081}], 'summary': 'Exploring all paths, finding minimal of all paths, and implementing straightforward recurrence for the function.', 'duration': 27.9, 'max_score': 715.694, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0715694.jpg'}], 'start': 425.035, 'title': 'Dynamic programming logic implementation and minimum path sum calculation', 'summary': "Discusses the implementation of dynamic programming logic to find the minimum path sum in a matrix, starting from f(0,0) and ending at the last row's column. it also covers the process of calculating the minimum path sum by exploring all possible paths with established base case and defined recursion, ensuring boundary conditions are not exceeded.", 'chapters': [{'end': 574.871, 'start': 425.035, 'title': 'Dynamic programming logic implementation', 'summary': "Discusses the implementation of a dynamic programming logic for finding the minimum path sum from the top-left to the bottom-right of a matrix, starting the recursion from f(0,0) and returning the value at the last row's column as the base case.", 'duration': 149.836, 'highlights': ['The recursion starts from f(0,0) instead of f(n-1,m-1) due to the preferable logic of starting from the top and going down, resulting in a more efficient approach.', 'The base case is determined as reaching the n-1th row, where the value in the jth column is returned and added to the answer, simplifying the process of finding the minimum path sum.']}, {'end': 743.594, 'start': 574.871, 'title': 'Minimum path sum calculation', 'summary': 'Discusses the process of calculating the minimum path sum by exploring all possible paths with the base case established and the recursion defined, emphasizing that the boundary conditions will never be exceeded and the minimal path sum will be returned as the result.', 'duration': 168.723, 'highlights': ['The chapter emphasizes the establishment of the base case for calculating the minimum path sum, asserting that there will be no out-of-boundary conditions, thus ensuring that only one base case is required.', 'It discusses exploring all possible paths by moving down and diagonally, highlighting the process of considering the minimal cost path sum and the minimal of all the paths to ultimately return the minimal path sum as the result.', 'The chapter explains the recursion process, detailing the exploration of all paths and the determination of the minimal path sum, providing a clear and straightforward approach to the problem.']}], 'duration': 318.559, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0425035.jpg', 'highlights': ['The recursion starts from f(0,0) for a more efficient approach', 'The base case simplifies the process of finding the minimum path sum', 'The chapter explains the recursion process and the determination of the minimal path sum', 'Exploring all possible paths ensures the minimal cost path sum']}, {'end': 1264.801, 'segs': [{'end': 821.072, 'src': 'heatmap', 'start': 772.558, 'weight': 0, 'content': [{'end': 777.201, 'text': 'We have exactly n column at the last row.', 'start': 772.558, 'duration': 4.643}, {'end': 785.763, 'text': 'so what we know is these are the number of rows, and for every column we have couple of options, either to go down or to go bottom.', 'start': 777.856, 'duration': 7.907}, {'end': 790.91, 'text': 'so we can say twice into twice, across every one right.', 'start': 785.763, 'duration': 5.147}, {'end': 800.678, 'text': "so 2 to the power, the summation of this, 2 to the power, summation of this, which is exponential in nature because you're going twice for everyone.", 'start': 790.91, 'duration': 9.768}, {'end': 803.32, 'text': 'right recursion and the space complexity.', 'start': 800.678, 'duration': 2.642}, {'end': 805.042, 'text': 'there will be a stack space involved.', 'start': 803.32, 'duration': 1.722}, {'end': 806.423, 'text': 'what will be the stack space?', 'start': 805.042, 'duration': 1.381}, {'end': 808.624, 'text': "you're going from the 0th row to the bottom.", 'start': 806.423, 'duration': 2.201}, {'end': 813.468, 'text': 'so the length of the rows, which is b, go of n.', 'start': 808.624, 'duration': 4.844}, {'end': 821.072, 'text': 'so i can say the recursion is this and you know how to Converter recursion like how to optimize this.', 'start': 813.468, 'duration': 7.604}], 'summary': 'The algorithm involves exponential complexity due to recursive computations, resulting in a large stack space.', 'duration': 28.12, 'max_score': 772.558, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0772558.jpg'}, {'end': 900.081, 'src': 'embed', 'start': 872.543, 'weight': 2, 'content': [{'end': 876.266, 'text': 'So we are seeing there will always be overlapping subproblems if you draw the tree.', 'start': 872.543, 'duration': 3.723}, {'end': 878.948, 'text': "I said I'll not draw, but still I did draw.", 'start': 876.606, 'duration': 2.342}, {'end': 883.05, 'text': 'So if you draw this, you will see that there are overlapping subproblems.', 'start': 879.588, 'duration': 3.462}, {'end': 891.416, 'text': 'And you know whenever there are overlapping subproblems, What can you apply? Yes, you can apply something as memoiation.', 'start': 883.451, 'duration': 7.965}, {'end': 893.917, 'text': 'Yes, you can apply something as memoiation.', 'start': 891.576, 'duration': 2.341}, {'end': 900.081, 'text': "Now, what's the next step? Can I say this? Can I say this? If I can apply memoiation, I had to figure out.", 'start': 894.297, 'duration': 5.784}], 'summary': 'Identified overlapping subproblems, applied memoization, and the need for further steps.', 'duration': 27.538, 'max_score': 872.543, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0872543.jpg'}, {'end': 999.861, 'src': 'heatmap', 'start': 934.646, 'weight': 0.719, 'content': [{'end': 939.407, 'text': "and if you're able to do this, it should be absolutely fine with the memorization solution.", 'start': 934.646, 'duration': 4.761}, {'end': 944.028, 'text': 'so once you convert it into a memorization solution, what is the time complexity?', 'start': 939.407, 'duration': 4.621}, {'end': 953.058, 'text': 'can i say the time complexity will be the number of states which is n into n, and the space complexity like it will not be exactly n into n,', 'start': 944.028, 'duration': 9.03}, {'end': 958.14, 'text': "because it's a triangle, right like if you, if you think it properly, it's a triangle.", 'start': 953.058, 'duration': 5.082}, {'end': 966.083, 'text': 'so one state, two states, these will be the number of states which is one plus two plus three, plus this portion of the dp will not be required.', 'start': 958.14, 'duration': 7.943}, {'end': 967.703, 'text': "but i'm not going into depth.", 'start': 966.083, 'duration': 1.62}, {'end': 971.064, 'text': 'you will, you can understand if you just do a dry run on yourself.', 'start': 967.703, 'duration': 3.361}, {'end': 972.185, 'text': "i'm not going into the depth.", 'start': 971.064, 'duration': 1.121}, {'end': 973.666, 'text': 'so the time complexity,', 'start': 972.705, 'duration': 0.961}, {'end': 981.43, 'text': 'like you can just generally say this is the time complexity and the space complexity will be this which is recursion stack space,', 'start': 973.666, 'duration': 7.764}, {'end': 984.532, 'text': "and i've already told you about what is recursion stack space.", 'start': 981.43, 'duration': 3.102}, {'end': 988.914, 'text': 'so this is the time complexity and the recursion stack space.', 'start': 984.532, 'duration': 4.382}, {'end': 990.435, 'text': 'perfect, guys, okay.', 'start': 988.914, 'duration': 1.521}, {'end': 993.997, 'text': 'so how do you remove the stack space?', 'start': 990.435, 'duration': 3.562}, {'end': 999.861, 'text': 'because you know, in a lot of platforms you will get TLA time limit exceeded.', 'start': 994.858, 'duration': 5.003}], 'summary': 'Converting to a memorization solution impacts time complexity; space complexity relates to recursion stack space.', 'duration': 65.215, 'max_score': 934.646, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0934646.jpg'}, {'end': 966.083, 'src': 'embed', 'start': 944.028, 'weight': 4, 'content': [{'end': 953.058, 'text': 'can i say the time complexity will be the number of states which is n into n, and the space complexity like it will not be exactly n into n,', 'start': 944.028, 'duration': 9.03}, {'end': 958.14, 'text': "because it's a triangle, right like if you, if you think it properly, it's a triangle.", 'start': 953.058, 'duration': 5.082}, {'end': 966.083, 'text': 'so one state, two states, these will be the number of states which is one plus two plus three, plus this portion of the dp will not be required.', 'start': 958.14, 'duration': 7.943}], 'summary': 'Time complexity: n^2, states: 1+2+3, triangular space complexity.', 'duration': 22.055, 'max_score': 944.028, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0944028.jpg'}, {'end': 1235.277, 'src': 'heatmap', 'start': 1119.269, 'weight': 0.819, 'content': [{'end': 1126.494, 'text': "So there can be four different base cases, agreed? So if I'm saying that there can be four different base cases, I just need to write it.", 'start': 1119.269, 'duration': 7.225}, {'end': 1135.621, 'text': 'So I know for sure that J, there can be J equal to zero till J lesser than N.', 'start': 1127.255, 'duration': 8.366}, {'end': 1137.383, 'text': 'So all the columns.', 'start': 1135.621, 'duration': 1.762}, {'end': 1142.456, 'text': 'And I know n minus one will stay common,', 'start': 1138.263, 'duration': 4.193}, {'end': 1151.763, 'text': 'but this column number will always change because it might be the first column and every time i just need to make sure i take the value from the matrix,', 'start': 1142.456, 'duration': 9.307}, {'end': 1155.426, 'text': 'because this is what i have been doing in the recursion right.', 'start': 1151.763, 'duration': 3.663}, {'end': 1157.508, 'text': 'we have been writing this only right.', 'start': 1155.426, 'duration': 2.082}, {'end': 1160.19, 'text': 'return this what can be the j?', 'start': 1157.508, 'duration': 2.682}, {'end': 1165.274, 'text': 'j can be 0, 1, 2 and 3, which is up till n minus 1..', 'start': 1160.19, 'duration': 5.084}, {'end': 1170.017, 'text': "that's what i wrote in the base case, so something different from the previous ones.", 'start': 1165.274, 'duration': 4.743}, {'end': 1172.078, 'text': 'we have written the base case ourselves.', 'start': 1170.017, 'duration': 2.061}, {'end': 1174.419, 'text': 'so you have written this particular base case.', 'start': 1172.078, 'duration': 2.341}, {'end': 1175.7, 'text': 'what is the next step?', 'start': 1174.419, 'duration': 1.281}, {'end': 1178.942, 'text': 'the next step is definitely writing the for loop.', 'start': 1175.7, 'duration': 3.242}, {'end': 1181.183, 'text': 'so we need to understand.', 'start': 1178.942, 'duration': 2.241}, {'end': 1186.186, 'text': 'if we write the recurrence from 0 to n minus 1, the tab, the tabulation will be opposite.', 'start': 1181.183, 'duration': 5.003}, {'end': 1190.307, 'text': 'why? because you know the base case is n at n minus 1.', 'start': 1186.186, 'duration': 4.121}, {'end': 1195.272, 'text': 'So you fill the table from n minus one, then to n minus two, then to n minus three, and so on.', 'start': 1190.307, 'duration': 4.965}, {'end': 1197.234, 'text': 'you go until zero, comma zero.', 'start': 1195.272, 'duration': 1.962}, {'end': 1206.183, 'text': 'So you go opposite, right? So what I know is, there will be the row number i will definitely start from n minus 2.', 'start': 1197.254, 'duration': 8.929}, {'end': 1209.606, 'text': "There's no need to do for n minus 1 because you've already done for it.", 'start': 1206.183, 'duration': 3.423}, {'end': 1212.468, 'text': 'We go till 0 and i minus minus.', 'start': 1210.246, 'duration': 2.222}, {'end': 1219.313, 'text': 'Now remember, whenever you write tabulation, you go and see what are the references.', 'start': 1213.028, 'duration': 6.285}, {'end': 1221.495, 'text': "There is a i and there's a j.", 'start': 1219.533, 'duration': 1.962}, {'end': 1226.339, 'text': "So for an i, what can be the particular j's? You think in your brain.", 'start': 1221.495, 'duration': 4.844}, {'end': 1235.277, 'text': "So if I see, if I is 0, what can be the possible j? I'll be like, for 0th row, there will be 0 columns.", 'start': 1226.929, 'duration': 8.348}], 'summary': 'Discussing the base cases and writing the recurrence using for loop. explaining the tabulation process.', 'duration': 116.008, 'max_score': 1119.269, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01119269.jpg'}, {'end': 1212.468, 'src': 'embed', 'start': 1186.186, 'weight': 3, 'content': [{'end': 1190.307, 'text': 'why? because you know the base case is n at n minus 1.', 'start': 1186.186, 'duration': 4.121}, {'end': 1195.272, 'text': 'So you fill the table from n minus one, then to n minus two, then to n minus three, and so on.', 'start': 1190.307, 'duration': 4.965}, {'end': 1197.234, 'text': 'you go until zero, comma zero.', 'start': 1195.272, 'duration': 1.962}, {'end': 1206.183, 'text': 'So you go opposite, right? So what I know is, there will be the row number i will definitely start from n minus 2.', 'start': 1197.254, 'duration': 8.929}, {'end': 1209.606, 'text': "There's no need to do for n minus 1 because you've already done for it.", 'start': 1206.183, 'duration': 3.423}, {'end': 1212.468, 'text': 'We go till 0 and i minus minus.', 'start': 1210.246, 'duration': 2.222}], 'summary': 'Fill table from n-1 to 0, i starts at n-2, no need for n-1.', 'duration': 26.282, 'max_score': 1186.186, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01186186.jpg'}], 'start': 743.594, 'title': 'Recursion time & space complexity', 'summary': 'Discusses the time complexity of recursive algorithms, highlighting the exponential nature caused by doubling options for every column, resulting in a complexity of 2^n. it covers optimizing recursion with dynamic programming, including converting to memoization, identifying overlapping subproblems, implementing tabulation, and insights on time and space complexity as well as stack space removal.', 'chapters': [{'end': 800.678, 'start': 743.594, 'title': 'Time complexity of recursion', 'summary': 'Discusses the time complexity of a recursive algorithm, illustrating the exponential nature of the algorithm due to the doubling of options for every column, resulting in a time complexity of 2 to the power of the summation.', 'duration': 57.084, 'highlights': ['The time complexity of the recursion is exponential, with a growth rate of 2 to the power of the summation, due to the doubling of options for every column.', 'The number of columns in each row increases by one, resulting in n columns in the last row.']}, {'end': 1264.801, 'start': 800.678, 'title': 'Optimizing recursion with dynamic programming', 'summary': 'Explains the process of converting a recursive solution to a memoization solution, identifying overlapping subproblems, and implementing tabulation method for optimizing space complexity, with examples and explanations. it also discusses the time complexity and space complexity of the solutions and provides insights on removing the stack space.', 'duration': 464.123, 'highlights': ['The process of converting a recursive solution to a memoization solution involves identifying overlapping subproblems by exploring the tree structure and applying memoization for optimization.', 'Implementing the tabulation method involves filling the table from n-1 to 0, considering the base case and iterating through the rows and columns in the opposite direction of the recursive approach.', 'The time complexity is determined by the number of states, which is n*n, while the space complexity is affected by the recursion stack space and the triangular nature of the problem, impacting the total number of states required for the solution.']}], 'duration': 521.207, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC0743594.jpg', 'highlights': ['The time complexity of the recursion is exponential, with a growth rate of 2 to the power of the summation, due to the doubling of options for every column.', 'The number of columns in each row increases by one, resulting in n columns in the last row.', 'The process of converting a recursive solution to a memoization solution involves identifying overlapping subproblems by exploring the tree structure and applying memoization for optimization.', 'Implementing the tabulation method involves filling the table from n-1 to 0, considering the base case and iterating through the rows and columns in the opposite direction of the recursive approach.', 'The time complexity is determined by the number of states, which is n*n, while the space complexity is affected by the recursion stack space and the triangular nature of the problem, impacting the total number of states required for the solution.']}, {'end': 1548.663, 'segs': [{'end': 1372.694, 'src': 'heatmap', 'start': 1264.801, 'weight': 2, 'content': [{'end': 1271.346, 'text': "So first variable you'll write, and then you'll create a nested loop, that's a tabulation concept for j.", 'start': 1264.801, 'duration': 6.545}, {'end': 1273.648, 'text': 'So create the nested loop for the tabulation concept.', 'start': 1271.346, 'duration': 2.302}, {'end': 1278.172, 'text': 'So I create a nested loop for the tabulation concept.', 'start': 1275.209, 'duration': 2.963}, {'end': 1282.558, 'text': "And what did I tell you? The nested now, you might ask, okay, let's try now.", 'start': 1278.612, 'duration': 3.946}, {'end': 1286.92, 'text': 'How will the nested loop run? Now, the nested loop will also run in the similar fashion.', 'start': 1282.718, 'duration': 4.202}, {'end': 1291.563, 'text': 'How did j move? j move like plus plus, right? Plus one something.', 'start': 1287.421, 'duration': 4.142}, {'end': 1298.947, 'text': 'You run the nested loop in the opposite direction, which is j equal to i, j greater than equal to zero, j minus minus.', 'start': 1291.923, 'duration': 7.024}, {'end': 1302.848, 'text': "If you're moving both of them in the plus plus, the tabulation will be the opposite.", 'start': 1299.707, 'duration': 3.141}, {'end': 1303.289, 'text': "That's it.", 'start': 1302.888, 'duration': 0.401}, {'end': 1306.39, 'text': "That's the simple tabulation nested.", 'start': 1304.129, 'duration': 2.261}, {'end': 1309.452, 'text': 'For every i, you write the particular j.', 'start': 1306.73, 'duration': 2.722}, {'end': 1309.812, 'text': "That's it.", 'start': 1309.452, 'duration': 0.36}, {'end': 1312.165, 'text': 'And after that, copy paste the recurrence.', 'start': 1310.285, 'duration': 1.88}, {'end': 1317.006, 'text': 'What is the recurrence? a of ij plus f of i plus 1j.', 'start': 1312.225, 'duration': 4.781}, {'end': 1322.407, 'text': "That's the recurrence relationship, right? So you write dp of i plus 1j.", 'start': 1317.126, 'duration': 5.281}, {'end': 1335.389, 'text': "What's the other one? You wrote dg equal to a of ij is a of ij plus dp of i plus 1 and j plus 1.", 'start': 1322.807, 'duration': 12.582}, {'end': 1345.172, 'text': 'Perfect. And then you wrote dp of ij equal to minimum of d comma dg.', 'start': 1335.389, 'duration': 9.783}, {'end': 1346.333, 'text': 'what will be answer?', 'start': 1345.172, 'duration': 1.161}, {'end': 1348.834, 'text': 'what is the recursion that you call to get the answer?', 'start': 1346.333, 'duration': 2.501}, {'end': 1353.215, 'text': 'the recursion that you call to get the answer was f of zero, comma zero.', 'start': 1348.834, 'duration': 4.381}, {'end': 1359.058, 'text': 'so over here the answer will be print of dp of zero and zero.', 'start': 1353.215, 'duration': 5.843}, {'end': 1362.099, 'text': "that's it.", 'start': 1359.058, 'duration': 3.041}, {'end': 1363.059, 'text': 'that is the answer.', 'start': 1362.099, 'duration': 0.96}, {'end': 1364.76, 'text': 'yes, that is the answer.', 'start': 1363.059, 'duration': 1.701}, {'end': 1366.821, 'text': 'perfect. so what is the time?', 'start': 1364.76, 'duration': 2.061}, {'end': 1372.694, 'text': "complexity. now again we go of n into n, because that's, that's the kind of like near.", 'start': 1366.821, 'duration': 5.873}], 'summary': 'The transcript discusses creating nested loops for tabulation concept with specific recurrence relationships and finding the answer for a given problem, with a time complexity of o(n^2).', 'duration': 81.532, 'max_score': 1264.801, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01264801.jpg'}, {'end': 1426.65, 'src': 'embed', 'start': 1395.419, 'weight': 0, 'content': [{'end': 1398.26, 'text': 'So the recursion stack space has been omitted.', 'start': 1395.419, 'duration': 2.841}, {'end': 1407.044, 'text': "And I just left off with this nCrosset nMatrix that you're using for this particular DP table.", 'start': 1398.861, 'duration': 8.183}, {'end': 1415.227, 'text': 'So we have made sure that the space complexity of the stack space has been removed.', 'start': 1407.964, 'duration': 7.263}, {'end': 1418.706, 'text': 'Can we optimize this? Yes.', 'start': 1417.045, 'duration': 1.661}, {'end': 1421.067, 'text': 'Why? I did tell you.', 'start': 1419.566, 'duration': 1.501}, {'end': 1426.65, 'text': 'If there is something like i plus 1, if there is something like i plus 1, you can always do it.', 'start': 1421.647, 'duration': 5.003}], 'summary': 'Optimized space complexity of recursion stack for dp table.', 'duration': 31.231, 'max_score': 1395.419, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01395419.jpg'}, {'end': 1486.699, 'src': 'heatmap', 'start': 1450.527, 'weight': 1, 'content': [{'end': 1451.669, 'text': 'i plus one.', 'start': 1450.527, 'duration': 1.142}, {'end': 1452.491, 'text': 'so how?', 'start': 1451.669, 'duration': 0.822}, {'end': 1454.814, 'text': 'how will this dp a table fill up?', 'start': 1452.491, 'duration': 2.323}, {'end': 1462.248, 'text': "so i'll always recommend, in order to understand space complexity better like, or space optimization better,", 'start': 1454.814, 'duration': 7.434}, {'end': 1467.27, 'text': 'try to do a dry run of this table format that the guy tushar roy does like.', 'start': 1462.248, 'duration': 5.022}, {'end': 1469.111, 'text': 'we have seen his videos.', 'start': 1467.27, 'duration': 1.841}, {'end': 1474.173, 'text': 'you will understand how he, like he, just comes up and writes the formula and fills up the dp table.', 'start': 1469.111, 'duration': 5.062}, {'end': 1478.274, 'text': 'so now you know how to how to derive this particular formula.', 'start': 1474.173, 'duration': 4.101}, {'end': 1480.715, 'text': 'now you can just fill up the dp table.', 'start': 1478.274, 'duration': 2.441}, {'end': 1486.699, 'text': 'so if you try to fill up the dp table, what happens is the last row is the base case,', 'start': 1480.715, 'duration': 5.984}], 'summary': "To understand space complexity, try a dry run of tushar roy's table format for filling up the dp table.", 'duration': 36.172, 'max_score': 1450.527, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01450527.jpg'}], 'start': 1264.801, 'title': 'Nested loop and dp table', 'summary': "Explains tabulation nested loop concept, demonstrating forward and backward loop creation, and discusses dp table's near n^2 time complexity and space optimization.", 'chapters': [{'end': 1309.812, 'start': 1264.801, 'title': 'Tabulation nested loop concept', 'summary': 'Explains the concept of tabulation nested loop, demonstrating how to create and run the nested loop in both forward and backward directions and emphasizing the importance of tabulation for every i.', 'duration': 45.011, 'highlights': ['The nested loop will also run in the similar fashion, emphasizing the consistent behavior of the nested loop.', 'The tabulation will be the opposite if you run the nested loop in the opposite direction, demonstrating the impact of changing the loop direction on tabulation.', 'For every i, you write the particular j, highlighting the importance of tabulation for every i.']}, {'end': 1548.663, 'start': 1310.285, 'title': 'Dp table and space optimization', 'summary': 'Discusses the recursion relationship, time complexity, and space optimization of a dp table, emphasizing the near n^2 time complexity and the removal of recursion stack space in the space complexity.', 'duration': 238.378, 'highlights': ['The recursion relationship is given by dp[i+1][j] = min(d, dg), where dg = a[i][j] + dp[i+1][j+1], and the answer is obtained by calling the recursion f(0, 0) and printing dp[0][0].', 'The time complexity is O(n^2) due to the number of rows, while the space complexity is optimized by removing the recursion stack space and using the nCrosset n matrix for the DP table.', 'Space optimization is achieved by storing and exchanging the previous values and filling up the DP table using a specific formula, leading to a near n^2 time complexity and better understanding of space optimization through a dry run of the table format.']}], 'duration': 283.862, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01264801.jpg', 'highlights': ['The time complexity is O(n^2) due to the number of rows, while the space complexity is optimized by removing the recursion stack space and using the nCrosset n matrix for the DP table.', 'Space optimization is achieved by storing and exchanging the previous values and filling up the DP table using a specific formula, leading to a near n^2 time complexity and better understanding of space optimization through a dry run of the table format.', 'The nested loop will also run in the similar fashion, emphasizing the consistent behavior of the nested loop.', 'The tabulation will be the opposite if you run the nested loop in the opposite direction, demonstrating the impact of changing the loop direction on tabulation.', 'For every i, you write the particular j, highlighting the importance of tabulation for every i.', 'The recursion relationship is given by dp[i+1][j] = min(d, dg), where dg = a[i][j] + dp[i+1][j+1], and the answer is obtained by calling the recursion f(0, 0) and printing dp[0][0].']}, {'end': 1883.218, 'segs': [{'end': 1605.097, 'src': 'embed', 'start': 1575.779, 'weight': 0, 'content': [{'end': 1577.5, 'text': "i'll not require this deleted.", 'start': 1575.779, 'duration': 1.721}, {'end': 1578.601, 'text': "then i'll compute this row.", 'start': 1577.5, 'duration': 1.101}, {'end': 1580.182, 'text': "i'll not require deleted.", 'start': 1578.601, 'duration': 1.581}, {'end': 1588.263, 'text': 'so can i say instead of storing the entire triangle, i just need to store two rows rows.', 'start': 1580.182, 'duration': 8.081}, {'end': 1595.309, 'text': 'one is the previous or like the front row, and one is the current row that you are traversing.', 'start': 1588.263, 'duration': 7.046}, {'end': 1598.591, 'text': 'and once this current row is computed and you move to this guy.', 'start': 1595.309, 'duration': 3.282}, {'end': 1601.073, 'text': 'this current row becomes the front row.', 'start': 1598.591, 'duration': 2.482}, {'end': 1602.895, 'text': 'can i say this i can.', 'start': 1601.073, 'duration': 1.822}, {'end': 1605.097, 'text': "that's what you have to just do in the code.", 'start': 1602.895, 'duration': 2.202}], 'summary': 'Optimize storage by storing only two rows for triangle computation.', 'duration': 29.318, 'max_score': 1575.779, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01575779.jpg'}, {'end': 1659.083, 'src': 'embed', 'start': 1626.614, 'weight': 2, 'content': [{'end': 1629.135, 'text': 'so the front is computed by this.', 'start': 1626.614, 'duration': 2.521}, {'end': 1634.297, 'text': 'next, this is front i plus one is front.', 'start': 1629.135, 'duration': 5.162}, {'end': 1636.078, 'text': 'the entire i plus one is front.', 'start': 1634.297, 'duration': 1.781}, {'end': 1646.636, 'text': 'say right front, correct now, instead of carrying dp of ij, because dp of ij means understand, dp of ij means this guy, this guy, this guy.', 'start': 1636.078, 'duration': 10.558}, {'end': 1648.958, 'text': 'so instead of dp of ij, what do you say?', 'start': 1646.636, 'duration': 2.322}, {'end': 1653.4, 'text': "is you just create this particular row, let's create one more row.", 'start': 1648.958, 'duration': 4.442}, {'end': 1659.083, 'text': "so what you basically do is you say okay, what i'm going to do is i'm not going to do anything.", 'start': 1653.4, 'duration': 5.683}], 'summary': 'Discussing computation and creation of rows for optimization.', 'duration': 32.469, 'max_score': 1626.614, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01626614.jpg'}, {'end': 1707.778, 'src': 'embed', 'start': 1668.492, 'weight': 1, 'content': [{'end': 1677.818, 'text': 'And once the entire row has been created by this particular for loop, you know this particular current for the next I will become the front.', 'start': 1668.492, 'duration': 9.326}, {'end': 1679.84, 'text': "So you'll say front, who is the front?", 'start': 1678.319, 'duration': 1.521}, {'end': 1685.757, 'text': 'current will be the front, for the next i, because i will go minus, minus.', 'start': 1680.732, 'duration': 5.025}, {'end': 1687.359, 'text': "that's the space optimization.", 'start': 1685.757, 'duration': 1.602}, {'end': 1692.024, 'text': "and once you do the space optimization you can be like okay, i've done the space optimization.", 'start': 1687.359, 'duration': 4.665}, {'end': 1695.287, 'text': 'so now the time complexity is still the same.', 'start': 1692.024, 'duration': 3.263}, {'end': 1701.613, 'text': "but the space complexity has boiled down to because when It's twice of n, but yeah it's near about big of n.", 'start': 1695.287, 'duration': 6.326}, {'end': 1703.415, 'text': "We're not using an n cross n matrix.", 'start': 1701.613, 'duration': 1.802}, {'end': 1707.778, 'text': "We're just using couple of rows and we're able to compute the entire answer.", 'start': 1703.935, 'duration': 3.843}], 'summary': 'Optimized space complexity to almost o(n) by using fewer rows for computation.', 'duration': 39.286, 'max_score': 1668.492, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01668492.jpg'}], 'start': 1548.663, 'title': 'Memory and space optimization', 'summary': 'Discusses optimizing memory usage for triangle computation and space complexity in a code, resulting in reduced memory consumption and significant reduction in space complexity.', 'chapters': [{'end': 1668.492, 'start': 1548.663, 'title': 'Optimizing memory usage for triangle computation', 'summary': 'Discusses optimizing memory usage for triangle computation by storing only two rows instead of the entire triangle, resulting in reduced memory consumption and improved efficiency.', 'duration': 119.829, 'highlights': ['Storing only two rows (previous and current) instead of the entire triangle reduces memory usage and improves efficiency.', "Utilizing the 'front row' and 'current row' approach for storing and computing triangle values results in optimized memory consumption and computational efficiency.", "Replacing 'dp of ij' with 'curve of J' reduces memory overhead and enhances computational performance."]}, {'end': 1883.218, 'start': 1668.492, 'title': 'Space optimization in code', 'summary': 'Discusses optimizing space complexity in a code by using dynamic programming and tabulation, resulting in a significant reduction in space complexity and improvement in time complexity.', 'duration': 214.726, 'highlights': ['The process of space optimization involves reducing space complexity, resulting in a significant improvement in the overall performance of the code.', 'The use of dynamic programming and tabulation is crucial for optimizing space complexity in the code, leading to a reduction in time complexity and efficient computation.']}], 'duration': 334.555, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01548663.jpg', 'highlights': ['Storing only two rows (previous and current) reduces memory usage and improves efficiency.', "Utilizing the 'front row' and 'current row' approach optimizes memory consumption and computational efficiency.", "Replacing 'dp of ij' with 'curve of J' reduces memory overhead and enhances computational performance.", 'The process of space optimization involves reducing space complexity, resulting in a significant improvement in overall performance.', 'Dynamic programming and tabulation are crucial for optimizing space complexity, leading to a reduction in time complexity and efficient computation.']}, {'end': 2070.129, 'segs': [{'end': 1913.141, 'src': 'embed', 'start': 1883.678, 'weight': 0, 'content': [{'end': 1886.3, 'text': 'And I know there is a last row that has to be filled.', 'start': 1883.678, 'duration': 2.622}, {'end': 1887.861, 'text': 'So kindly fill up the last row.', 'start': 1886.34, 'duration': 1.521}, {'end': 1889.002, 'text': "That's very simple.", 'start': 1888.281, 'duration': 0.721}, {'end': 1890.863, 'text': 'DP of the last row.', 'start': 1889.042, 'duration': 1.821}, {'end': 1896.969, 'text': 'and the column will be nothing but the triangle of the last row and the column.', 'start': 1891.543, 'duration': 5.426}, {'end': 1899.512, 'text': "that's how you can easily fill that up.", 'start': 1896.969, 'duration': 2.543}, {'end': 1905.939, 'text': 'and apart from that, there will be a couple of nested loops right, starting from the back, so we can just run it off.', 'start': 1899.512, 'duration': 6.427}, {'end': 1913.141, 'text': 'there will also be a for intj, equal to starting from the back, and it can go on something like this.', 'start': 1905.939, 'duration': 7.202}], 'summary': 'Fill the last row with the triangle values using nested loops.', 'duration': 29.463, 'max_score': 1883.678, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01883678.jpg'}, {'end': 1994.178, 'src': 'embed', 'start': 1931.007, 'weight': 1, 'content': [{'end': 1938.692, 'text': "that's the shuttle change that you need to do instead of f, and it will always be dp of the recurrence that you are calling.", 'start': 1931.007, 'duration': 7.685}, {'end': 1940.193, 'text': 'so just carry it on.', 'start': 1938.692, 'duration': 1.501}, {'end': 1943.374, 'text': 'dp of i plus 1 to j plus 1.', 'start': 1940.193, 'duration': 3.181}, {'end': 1945.015, 'text': "that's how you will do it.", 'start': 1943.374, 'duration': 1.641}, {'end': 1949.778, 'text': 'and at the end of the day you can say dp of i, j will be minimal, of d, comma d, g.', 'start': 1945.015, 'duration': 4.763}, {'end': 1952.099, 'text': 'so once you have done this, you know what will you return.', 'start': 1949.778, 'duration': 2.321}, {'end': 1958.384, 'text': "you will always return dp of zero, zero, because that's sorry, db of, is it zero zero?", 'start': 1952.099, 'duration': 6.285}, {'end': 1959.425, 'text': "yeah, that's zero zero.", 'start': 1958.384, 'duration': 1.041}, {'end': 1961.848, 'text': "so zero zero is what you're going to return.", 'start': 1959.425, 'duration': 2.423}, {'end': 1964.99, 'text': "let's quickly run this off should be running fine.", 'start': 1961.848, 'duration': 3.142}, {'end': 1966.192, 'text': "yeah, that's run.", 'start': 1964.99, 'duration': 1.202}, {'end': 1967.653, 'text': "let's quickly submit this off.", 'start': 1966.192, 'duration': 1.461}, {'end': 1968.914, 'text': "let's see if this is getting your tle.", 'start': 1967.653, 'duration': 1.261}, {'end': 1971.777, 'text': 'okay, this is not giving okay.', 'start': 1968.914, 'duration': 2.863}, {'end': 1975.86, 'text': "so this, uh, appears to be the correct answer and you're getting your 100 school.", 'start': 1971.777, 'duration': 4.083}, {'end': 1979.648, 'text': 'so now, what are the changes that i require?', 'start': 1975.86, 'duration': 3.788}, {'end': 1980.529, 'text': "what's the next step?", 'start': 1979.648, 'duration': 0.881}, {'end': 1981.63, 'text': 'space optimization.', 'start': 1980.529, 'duration': 1.101}, {'end': 1982.911, 'text': 'let me quickly raise the software.', 'start': 1981.63, 'duration': 1.281}, {'end': 1985.172, 'text': 'get some space, any space optimization, right.', 'start': 1982.911, 'duration': 2.261}, {'end': 1989.455, 'text': 'so we need to delete this and we just need to store the last row.', 'start': 1985.172, 'duration': 4.283}, {'end': 1994.178, 'text': 'so what we can do is we can say vector of int, probably front row.', 'start': 1989.455, 'duration': 4.723}], 'summary': 'The transcript discusses implementing shuttle change for dp recurrence and achieving 100% score, followed by space optimization.', 'duration': 63.171, 'max_score': 1931.007, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01931007.jpg'}], 'start': 1883.678, 'title': 'Dynamic programming and space optimization', 'summary': 'Covers dynamic programming, focusing on filling up the last row using nested loops and space optimization through vector storage, resulting in improved performance and correct results.', 'chapters': [{'end': 1971.777, 'start': 1883.678, 'title': 'Dynamic programming explanation', 'summary': 'Discusses the process of filling up the last row using dynamic programming and nested loops, with emphasis on creating a dp of i plus 1 and j, and returning dp of zero, zero.', 'duration': 88.099, 'highlights': ['The process of filling up the last row using dynamic programming and nested loops is explained, with emphasis on creating a dp of i plus 1 and j. (Relevance: 5)', 'The explanation highlights the importance of returning dp of zero, zero at the end of the process. (Relevance: 4)', "The speaker emphasizes the need to copy specific parts and make a shuttle change by creating a dp of i plus 1 and j instead of 'f'. (Relevance: 3)"]}, {'end': 2070.129, 'start': 1971.777, 'title': 'Space optimization in dynamic programming', 'summary': 'Explains space optimization in dynamic programming through the example of optimizing space in a software to store the last row using vectors, resulting in improved performance and correct results.', 'duration': 98.352, 'highlights': ['The chapter explains the process of optimizing space in a software to store the last row using vectors, resulting in improved performance and correct results.', 'The speaker demonstrates the use of vectors and reinitialization of variables to achieve space optimization in dynamic programming.', "The video concludes by encouraging viewers to like the video and comment 'understood' to motivate the creator."]}], 'duration': 186.451, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/SrP-PiLSYC0/pics/SrP-PiLSYC01883678.jpg', 'highlights': ['The process of filling up the last row using dynamic programming and nested loops is explained, with emphasis on creating a dp of i plus 1 and j. (Relevance: 5)', 'The explanation highlights the importance of returning dp of zero, zero at the end of the process. (Relevance: 4)', 'The process of optimizing space in a software to store the last row using vectors is explained, resulting in improved performance and correct results. (Relevance: 3)', 'The speaker demonstrates the use of vectors and reinitialization of variables to achieve space optimization in dynamic programming. (Relevance: 2)', "The speaker emphasizes the need to copy specific parts and make a shuttle change by creating a dp of i plus 1 and j instead of 'f'. (Relevance: 1)"]}], 'highlights': ['The time complexity is O(n^2) due to the number of rows, while the space complexity is optimized by removing the recursion stack space and using the nCrosset n matrix for the DP table. (Relevance: 1)', 'The process of converting a recursive solution to a memoization solution involves identifying overlapping subproblems by exploring the tree structure and applying memoization for optimization. (Relevance: 2)', 'The process of space optimization involves reducing space complexity, resulting in a significant improvement in overall performance. (Relevance: 3)', 'The explanation highlights the importance of returning dp of zero, zero at the end of the process. (Relevance: 4)', 'The process of filling up the last row using dynamic programming and nested loops is explained, with emphasis on creating a dp of i plus 1 and j. (Relevance: 5)']}