title

DP 37. Buy and Sell Stocks III | Recursion to Space Optimisation

description

Lecture Notes/C++/Java Codes: https://takeuforward.org/dynamic-programming/striver-dp-series-dynamic-programming-problems/
Problem Link: https://bit.ly/3rLHkqQ
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 third problem on Buy and Sell stocks.
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 37. Buy and Sell Stocks III | Recursion to Space Optimisation', 'heatmap': [{'end': 1184.805, 'start': 1141.894, 'weight': 1}, {'end': 1376.015, 'start': 1354.089, 'weight': 0.734}], 'summary': 'Covers strategies for maximizing stock profits with at most two transactions, including insights into constraints and solutions, emphasizing the importance of buy-sell transactions, and optimizing recursion to achieve a time complexity of n*2*3 and constant space complexity.', 'chapters': [{'end': 288.345, 'segs': [{'end': 50.794, 'src': 'embed', 'start': 21.889, 'weight': 2, 'content': [{'end': 25.931, 'text': "you're just allowed to do one, yes, one transaction.", 'start': 21.889, 'duration': 4.042}, {'end': 29.592, 'text': 'so probably you could have bought over here and you could have sold it over here.', 'start': 25.931, 'duration': 3.661}, {'end': 33.754, 'text': "hence the profit that you'd have made was four correct.", 'start': 29.592, 'duration': 4.162}, {'end': 35.815, 'text': 'and with what was part two?', 'start': 33.754, 'duration': 2.061}, {'end': 47.391, 'text': "part two said that you can do as many like infinite transactions, but just make sure you don't engage in multiple transactions together.", 'start': 35.815, 'duration': 11.576}, {'end': 50.794, 'text': "so you could have said i will buy here, i'll sell it here.", 'start': 47.391, 'duration': 3.403}], 'summary': 'One transaction allowed with a profit of four. infinite transactions possible without engaging in multiple transactions together.', 'duration': 28.905, 'max_score': 21.889, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ21889.jpg'}, {'end': 116.904, 'src': 'embed', 'start': 72.571, 'weight': 0, 'content': [{'end': 74.132, 'text': 'what is part three?', 'start': 72.571, 'duration': 1.561}, {'end': 79.738, 'text': 'part three states at max two transactions.', 'start': 74.132, 'duration': 5.606}, {'end': 87.747, 'text': 'yes, at max, what you can do is two transactions, not more than two transactions, okay.', 'start': 79.738, 'duration': 8.009}, {'end': 92.232, 'text': 'so we are basically limiting the number of transactions that we are doing.', 'start': 87.747, 'duration': 4.485}, {'end': 98.478, 'text': 'so, apparently, if there was unlimited transactions, you could have gone this, Then this and then this.', 'start': 92.232, 'duration': 6.246}, {'end': 102.059, 'text': 'So you could have done three transactions to get the maximum profit.', 'start': 98.498, 'duration': 3.561}, {'end': 103.699, 'text': "But over here you're limited.", 'start': 102.399, 'duration': 1.3}, {'end': 108.761, 'text': 'So how can you do at max two transactions? Probably you can say I can do this.', 'start': 104.039, 'duration': 4.722}, {'end': 109.801, 'text': 'I can do this.', 'start': 109.161, 'duration': 0.64}, {'end': 110.982, 'text': "Then you'll get two.", 'start': 110.222, 'duration': 0.76}, {'end': 114.623, 'text': "Then you'll get three which makes it a total profit of five.", 'start': 111.242, 'duration': 3.381}, {'end': 116.904, 'text': 'In this way you can do two transactions.', 'start': 115.123, 'duration': 1.781}], 'summary': 'Part three restricts transactions to at most two, limiting potential profit to five.', 'duration': 44.333, 'max_score': 72.571, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ72571.jpg'}, {'end': 183.21, 'src': 'embed', 'start': 134.541, 'weight': 1, 'content': [{'end': 141.178, 'text': 'or i can say is hey listen, buy here, sell here to get a profit of three.', 'start': 134.541, 'duration': 6.637}, {'end': 145.26, 'text': 'again, buy here and again, sell here to get a profit of three.', 'start': 141.178, 'duration': 4.082}, {'end': 148.482, 'text': 'in total, you can make a profit of six.', 'start': 145.26, 'duration': 3.222}, {'end': 153.225, 'text': 'that means you can do these couple of transactions and you can make a profit of six.', 'start': 148.482, 'duration': 4.743}, {'end': 155.486, 'text': "and that's the maximum you can make.", 'start': 153.225, 'duration': 2.261}, {'end': 161.329, 'text': "that's three minus zero, equal to three, and four minus one, equal to three, which makes it a total sum of six.", 'start': 155.486, 'duration': 5.843}, {'end': 165.091, 'text': 'that is the maximum profit that you can make.', 'start': 162.029, 'duration': 3.062}, {'end': 171.754, 'text': 'yes, that is the maximum profit you can make by buying here, selling here, buying here, selling here.', 'start': 165.091, 'duration': 6.663}, {'end': 174.776, 'text': 'so you have done at max two transactions.', 'start': 171.754, 'duration': 3.022}, {'end': 180.739, 'text': 'now this problem is an extension of the buy and sell stock.', 'start': 174.776, 'duration': 5.963}, {'end': 183.21, 'text': 'two problem that we do.', 'start': 181.65, 'duration': 1.56}], 'summary': 'Maximize profit by making two transactions, yielding a total profit of six.', 'duration': 48.669, 'max_score': 134.541, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ134541.jpg'}, {'end': 236.24, 'src': 'embed', 'start': 205.257, 'weight': 6, 'content': [{'end': 207.338, 'text': "so that's how you started, correct?", 'start': 205.257, 'duration': 2.081}, {'end': 216.624, 'text': "and then what you did was if you're allowed to buy, you took that guy, you took that guy and when you took it, it did add a negative value to you.", 'start': 207.338, 'duration': 9.286}, {'end': 218.526, 'text': 'it did add a negative value to you.', 'start': 216.624, 'duration': 1.902}, {'end': 223.611, 'text': "why? because if you're taking that stock, that means you're investing money into the market.", 'start': 218.526, 'duration': 5.085}, {'end': 226.273, 'text': 'so the money is gone, thereby a minus.', 'start': 223.611, 'duration': 2.662}, {'end': 231.658, 'text': "and then you said i'll go to the next guy, i'll go to the next day and this guy is.", 'start': 226.273, 'duration': 5.385}, {'end': 233.059, 'text': 'this guy will be sell.', 'start': 231.658, 'duration': 1.401}, {'end': 236.24, 'text': 'that means you are not allowed to buy.', 'start': 233.479, 'duration': 2.761}], 'summary': 'Explanation of stock trading process with examples, emphasizing investing and selling.', 'duration': 30.983, 'max_score': 205.257, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ205257.jpg'}, {'end': 288.345, 'src': 'embed', 'start': 248.306, 'weight': 7, 'content': [{'end': 252.968, 'text': 'so if you are allowed to buy, either you can buy or either you cannot buy.', 'start': 248.306, 'duration': 4.662}, {'end': 256.009, 'text': "that's how you will do if you are allowed to buy right.", 'start': 252.968, 'duration': 3.041}, {'end': 261.172, 'text': "and if you are asked that, hey, listen, i am not allowed to buy, I'm allowed to just sell.", 'start': 256.009, 'duration': 5.163}, {'end': 262.453, 'text': 'So either you can sell.', 'start': 261.512, 'duration': 0.941}, {'end': 265.155, 'text': "So if you sell from the market, you'll get this value back.", 'start': 262.673, 'duration': 2.482}, {'end': 268.258, 'text': "So this is the value that you'll get back and it'll go to the next day.", 'start': 265.456, 'duration': 2.802}, {'end': 271.741, 'text': "So if you have sold on the next day, you're again allowed to buy.", 'start': 268.579, 'duration': 3.162}, {'end': 276.686, 'text': "You're again allowed to buy, right? And if you say that, hey, listen, I'm not interested to sell today.", 'start': 272.002, 'duration': 4.684}, {'end': 279.468, 'text': "That means the amount that you'll get from the market is zero.", 'start': 277.066, 'duration': 2.402}, {'end': 281.79, 'text': "It'll go to the next day and it's still.", 'start': 279.829, 'duration': 1.961}, {'end': 284.883, 'text': 'able to sell and not able to buy.', 'start': 282.862, 'duration': 2.021}, {'end': 288.345, 'text': "so that's how you can see sell or not sell.", 'start': 284.883, 'duration': 3.462}], 'summary': 'Explanation of buying and selling in the market with allowance and values.', 'duration': 40.039, 'max_score': 248.306, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ248306.jpg'}], 'start': 0.349, 'title': 'Maximizing stock profit with two transactions', 'summary': 'Covers strategies for maximizing stock profits with at most two transactions, providing insights into the constraints and solutions for each part, and illustrating the possibility of achieving a maximum profit of six. it also explains stock trading rules and actions, including the impact of buying and selling on value and permission to buy and sell on different days.', 'chapters': [{'end': 98.478, 'start': 0.349, 'title': 'Maximize stock profit with two transactions', 'summary': 'Covers the problem of maximizing profit with at most two stock transactions, following on from part one and part two, which allowed one and unlimited transactions respectively. it explains the constraints and solutions for each part, including quantifiable data on profits.', 'duration': 98.129, 'highlights': ['Part two allowed unlimited transactions, resulting in a total profit of eight by making three separate transactions (3+3+2).', 'Part one permitted only one transaction, yielding a profit of four from a single buy and sell.', 'Part three introduces the constraint of at most two transactions, limiting the number of possible transactions.']}, {'end': 205.257, 'start': 98.498, 'title': 'Maximize stock profit', 'summary': 'Discusses strategies for maximizing stock profits by conducting at most two transactions, with the possibility of achieving a maximum profit of six, as illustrated through various transaction scenarios.', 'duration': 106.759, 'highlights': ['You can make a total profit of six by conducting two transactions, with profits of three and three from the two pairs of buying and selling.', 'By conducting two transactions, you can achieve a total profit of five by selling at two different peaks and buying at two different dips.', 'The problem of maximizing stock profit by conducting at most two transactions is an extension of the buy and sell stock problem.']}, {'end': 288.345, 'start': 205.257, 'title': 'Stock trading rules and actions', 'summary': 'Explains the rules and actions involved in stock trading, including the impact of buying and selling on value, as well as permission to buy and sell on different days.', 'duration': 83.088, 'highlights': ['When you take a stock, it adds a negative value as you are investing money into the market, resulting in a loss.', 'Permission to buy or sell is based on the day, with zero indicating no more buy and the ability to sell.', 'Selling from the market results in getting a value back, allowing for further actions in the following days.', 'Deciding to not buy or sell affects the amount obtained from the market, with implications for future trading decisions.']}], 'duration': 287.996, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ349.jpg', 'highlights': ['Part two allowed unlimited transactions, resulting in a total profit of eight by making three separate transactions (3+3+2).', 'You can make a total profit of six by conducting two transactions, with profits of three and three from the two pairs of buying and selling.', 'Part one permitted only one transaction, yielding a profit of four from a single buy and sell.', 'By conducting two transactions, you can achieve a total profit of five by selling at two different peaks and buying at two different dips.', 'Part three introduces the constraint of at most two transactions, limiting the number of possible transactions.', 'The problem of maximizing stock profit by conducting at most two transactions is an extension of the buy and sell stock problem.', 'When you take a stock, it adds a negative value as you are investing money into the market, resulting in a loss.', 'Permission to buy or sell is based on the day, with zero indicating no more buy and the ability to sell.', 'Selling from the market results in getting a value back, allowing for further actions in the following days.', 'Deciding to not buy or sell affects the amount obtained from the market, with implications for future trading decisions.']}, {'end': 480.202, 'segs': [{'end': 361.108, 'src': 'embed', 'start': 318.394, 'weight': 0, 'content': [{'end': 319.815, 'text': "i'm putting a bound.", 'start': 318.394, 'duration': 1.421}, {'end': 324.576, 'text': "so can you relate this to the knapsack problem, where i'm saying hey listen, you can just do this much.", 'start': 319.815, 'duration': 4.761}, {'end': 326.196, 'text': 'you cannot do more than this.', 'start': 324.576, 'duration': 1.62}, {'end': 328.637, 'text': 'it just allowed to do two transactions.', 'start': 326.196, 'duration': 2.441}, {'end': 333.078, 'text': "so can i say okay, fine, if i'm allowed to do two transactions,", 'start': 328.637, 'duration': 4.441}, {'end': 339.24, 'text': 'can i rewrite the same code into something like similar code where i say index and buy?', 'start': 333.078, 'duration': 6.162}, {'end': 344.861, 'text': 'I put a cap like this is the maximum number of transactions I can do.', 'start': 340.359, 'duration': 4.502}, {'end': 348.783, 'text': 'I cannot exceed these cap of transactions.', 'start': 344.861, 'duration': 3.922}, {'end': 351.204, 'text': "so let's forget about the base case.", 'start': 348.783, 'duration': 2.421}, {'end': 357.246, 'text': "let's write the buy case if I'm allowed to buy and let's write the other case if I'm not allowed to buy.", 'start': 351.204, 'duration': 6.042}, {'end': 360.067, 'text': "so if I'm allowed to buy, what will I do?", 'start': 357.246, 'duration': 2.821}, {'end': 361.108, 'text': 'I will say if I buy.', 'start': 360.067, 'duration': 1.041}], 'summary': 'Relating problem to knapsack, limiting transactions, rewriting code for two transactions.', 'duration': 42.714, 'max_score': 318.394, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ318394.jpg'}, {'end': 439.72, 'src': 'embed', 'start': 406.122, 'weight': 2, 'content': [{'end': 410.783, 'text': 'for a transaction to be completed, it has to be a buy sell, it has to be a buy sell.', 'start': 406.122, 'duration': 4.661}, {'end': 414.004, 'text': 'so the transaction is yet not completed, right.', 'start': 410.783, 'duration': 3.221}, {'end': 414.544, 'text': 'so what do you do?', 'start': 414.004, 'duration': 0.54}, {'end': 417.905, 'text': 'is you say hey, the transaction is yet not completed.', 'start': 414.544, 'duration': 3.361}, {'end': 426.728, 'text': "so please go on with the number of transactions that you had, or else i can say hey, listen, on this given day i'm not interested to buy,", 'start': 417.905, 'duration': 8.823}, {'end': 429.649, 'text': "i'm not interested to buy, so i'm not interested to buy.", 'start': 426.728, 'duration': 2.921}, {'end': 431.209, 'text': "can i say i'll take a zero.", 'start': 429.649, 'duration': 1.56}, {'end': 439.72, 'text': "can i say i'll take a zero plus f off, i'll go to the next day, right, and i'll say still be able to buy,", 'start': 431.209, 'duration': 8.511}], 'summary': 'The transaction is not yet completed, asking for the number of transactions and expressing disinterest in buying.', 'duration': 33.598, 'max_score': 406.122, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ406122.jpg'}], 'start': 288.345, 'title': 'Transactions and market strategy', 'summary': 'Discusses introducing a cap on the number of transactions in the code, and the process of transaction completion, market strategy, and the factors influencing the decision-making process, emphasizing the importance of buy-sell transactions and the impact on market prices.', 'chapters': [{'end': 361.108, 'start': 288.345, 'title': 'Cap on transactions in code', 'summary': 'Discusses introducing a cap on the number of transactions in the code, drawing a parallel to the knapsack problem and modifying the code accordingly.', 'duration': 72.763, 'highlights': ['Introducing a cap on the number of transactions in the code, akin to the knapsack problem, to limit the transactions to a specified quantity.', 'Modifying the code to include conditions for buying and not buying based on the maximum number of allowed transactions.']}, {'end': 480.202, 'start': 361.108, 'title': 'Transaction completion and market strategy', 'summary': 'Discusses the process of transaction completion, market strategy, and the factors influencing the decision-making process, emphasizing the importance of buy-sell transactions and the impact on market prices.', 'duration': 119.094, 'highlights': ['Performing a buy-sell transaction is crucial for completion, as a transaction has to be a buy-sell for completion, and not performing a buy transaction allows for a zero return and maintains the number of transactions (quantifiable data: decision-making process and completion criteria).', "The process emphasizes the importance of buy-sell transactions and the impact on market prices, as the decision-making process is influenced by the market's price and the individual's interest in buying or selling (quantifiable data: market strategy and pricing influence).", "Selling adds value to the transaction, emphasizing the significance of the buy-sell process and its impact on the transaction's outcome (quantifiable data: transaction value and completion criteria)."]}], 'duration': 191.857, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ288345.jpg', 'highlights': ['Introducing a cap on the number of transactions in the code, akin to the knapsack problem, to limit the transactions to a specified quantity.', 'Modifying the code to include conditions for buying and not buying based on the maximum number of allowed transactions.', "The process emphasizes the importance of buy-sell transactions and the impact on market prices, as the decision-making process is influenced by the market's price and the individual's interest in buying or selling (quantifiable data: market strategy and pricing influence).", "Selling adds value to the transaction, emphasizing the significance of the buy-sell process and its impact on the transaction's outcome (quantifiable data: transaction value and completion criteria).", 'Performing a buy-sell transaction is crucial for completion, as a transaction has to be a buy-sell for completion, and not performing a buy transaction allows for a zero return and maintains the number of transactions (quantifiable data: decision-making process and completion criteria).']}, {'end': 612.284, 'segs': [{'end': 573.935, 'src': 'embed', 'start': 545.202, 'weight': 2, 'content': [{'end': 548.717, 'text': 'What will you do next? I can say that, okay, I have to write the base case.', 'start': 545.202, 'duration': 3.515}, {'end': 553.821, 'text': 'So, I know I will end up the transactions when I reach N.', 'start': 549.278, 'duration': 4.543}, {'end': 555.422, 'text': "That's when I reach N.", 'start': 553.821, 'duration': 1.601}, {'end': 556.222, 'text': 'And what did we write?', 'start': 555.422, 'duration': 0.8}, {'end': 557.703, 'text': 'the base case over here, if you remember?', 'start': 556.222, 'duration': 1.481}, {'end': 563.147, 'text': 'We simply returned a 0, because when you are reaching the like, you have exhausted all the days.', 'start': 558.024, 'duration': 5.123}, {'end': 564.628, 'text': 'you will not get anything from the market.', 'start': 563.147, 'duration': 1.481}, {'end': 567.951, 'text': 'Will you get anything from the market? Definitely not.', 'start': 565.549, 'duration': 2.402}, {'end': 570.572, 'text': 'So, you get a return 0.', 'start': 568.511, 'duration': 2.061}, {'end': 573.935, 'text': "What's the other case? If I also exhaust.", 'start': 570.572, 'duration': 3.363}], 'summary': 'Discussing base cases and returns in transaction analysis.', 'duration': 28.733, 'max_score': 545.202, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ545202.jpg'}, {'end': 619.81, 'src': 'embed', 'start': 587.911, 'weight': 0, 'content': [{'end': 591.192, 'text': "Or if I've exhausted the number of days, I'll not get anything from the market.", 'start': 587.911, 'duration': 3.281}, {'end': 593.753, 'text': 'So this is what I will be doing.', 'start': 591.512, 'duration': 2.241}, {'end': 605.579, 'text': 'A shuttle change on the cap of the transactions will enable me to convert the previous code to this problem where we are bounded with certain number of transactions,', 'start': 594.093, 'duration': 11.486}, {'end': 608.461, 'text': 'which says at most two.', 'start': 605.579, 'duration': 2.882}, {'end': 611.103, 'text': 'i hope you have got the fair bit of idea.', 'start': 608.461, 'duration': 2.642}, {'end': 612.284, 'text': 'so we are.', 'start': 611.103, 'duration': 1.181}, {'end': 619.81, 'text': 'we are doing as of now, recursion right, and you know you will be trying out all possibilities.', 'start': 612.284, 'duration': 7.526}], 'summary': 'Implementing a shuttle change to limit transactions to at most two, using recursion to explore all possibilities.', 'duration': 31.899, 'max_score': 587.911, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ587911.jpg'}], 'start': 480.222, 'title': 'Shuttle change in transactions', 'summary': 'Discusses the concept of shuttle change in transactions, emphasizing the reduction of transaction numbers and the base cases for ending transactions, while explaining the process of converting the previous code to the current problem.', 'chapters': [{'end': 612.284, 'start': 480.222, 'title': 'Shuttle change in transactions', 'summary': 'Discusses the concept of shuttle change in transactions, emphasizing the reduction of transaction numbers and the base cases for ending transactions, while explaining the process of converting the previous code to the current problem.', 'duration': 132.062, 'highlights': ['The concept of shuttle change in transactions is emphasized, focusing on the reduction of transaction numbers, which eventually means the number of transactions will get reduced by one.', 'The discussion covers the base cases for ending transactions, including the scenarios where no returns are obtained from the market due to exhaustion of days or transactions.', 'The process of converting the previous code to the current problem is explained, highlighting the concept of being bounded by a certain number of transactions, specifically at most two.']}], 'duration': 132.062, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ480222.jpg', 'highlights': ['The concept of shuttle change in transactions is emphasized, focusing on the reduction of transaction numbers, which eventually means the number of transactions will get reduced by one.', 'The process of converting the previous code to the current problem is explained, highlighting the concept of being bounded by a certain number of transactions, specifically at most two.', 'The discussion covers the base cases for ending transactions, including the scenarios where no returns are obtained from the market due to exhaustion of days or transactions.']}, {'end': 886.832, 'segs': [{'end': 636.371, 'src': 'embed', 'start': 612.284, 'weight': 4, 'content': [{'end': 619.81, 'text': 'we are doing as of now, recursion right, and you know you will be trying out all possibilities.', 'start': 612.284, 'duration': 7.526}, {'end': 622.312, 'text': 'so the time complexity will be exponential.', 'start': 619.81, 'duration': 2.502}, {'end': 629.525, 'text': 'I will give you a TLE, but the space complexity that you will be using will have auxiliary stack space of V.', 'start': 623.359, 'duration': 6.166}, {'end': 633.288, 'text': 'go of n, because you are performing on index plus 1..', 'start': 629.525, 'duration': 3.763}, {'end': 636.371, 'text': 'So the depth of the recursion will go on to index plus 1.', 'start': 633.288, 'duration': 3.083}], 'summary': 'Recursion leads to exponential time complexity, tle, and v space complexity.', 'duration': 24.087, 'max_score': 612.284, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ612284.jpg'}, {'end': 713.838, 'src': 'embed', 'start': 662.853, 'weight': 2, 'content': [{'end': 669.358, 'text': "so if there are overlapping sub problems, you can draw the recursion tree and you'll see that there are certain overlapping sub problems.", 'start': 662.853, 'duration': 6.505}, {'end': 679.266, 'text': 'thereby. what we can do is we can definitely apply something as memo iation to stop pre-computation of the repeated states.', 'start': 669.358, 'duration': 9.908}, {'end': 680.687, 'text': 'so what are the states?', 'start': 679.266, 'duration': 1.421}, {'end': 686.475, 'text': 'we have an index, we have a by, have a cap.', 'start': 680.687, 'duration': 5.788}, {'end': 687.436, 'text': "let's analyze what are.", 'start': 686.475, 'duration': 0.961}, {'end': 690.398, 'text': 'the maximum value of index can be.', 'start': 687.436, 'duration': 2.962}, {'end': 698.625, 'text': 'this index can be from 0 to n minus 1, which makes it a total of n different states from 0 to n minus 1.', 'start': 690.398, 'duration': 8.227}, {'end': 699.946, 'text': 'what can we buy?', 'start': 698.625, 'duration': 1.321}, {'end': 706.712, 'text': "buy can be either you are not allowed to buy or either you're allowed to buy two different states of buy.", 'start': 699.946, 'duration': 6.766}, {'end': 707.953, 'text': 'what can be capped?', 'start': 706.712, 'duration': 1.241}, {'end': 713.838, 'text': 'either you have zero transactions remaining, one transactions remaining, or two transactions remaining.', 'start': 707.953, 'duration': 5.885}], 'summary': 'Apply memoization to optimize computation for overlapping subproblems in index, buy, and cap states.', 'duration': 50.985, 'max_score': 662.853, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ662853.jpg'}, {'end': 770.234, 'src': 'embed', 'start': 741.239, 'weight': 0, 'content': [{'end': 746.503, 'text': "That's what you just need to do in order to convert this into a memoization solution.", 'start': 741.239, 'duration': 5.264}, {'end': 754.609, 'text': 'And if we are able to convert this into a memoization solution, the time complexity of that solution will be n cross 1.', 'start': 746.803, 'duration': 7.806}, {'end': 758.45, 'text': "2, cross 3, because that's what you have over here.", 'start': 754.609, 'duration': 3.841}, {'end': 760.131, 'text': 'n cross 2 cross 3,', 'start': 758.45, 'duration': 1.681}, {'end': 770.234, 'text': 'and the space complexity will be obviously n cross 2 cross 3 plus the auxiliary stack space plus the auxiliary stack space of the recursion.', 'start': 760.131, 'duration': 10.103}], 'summary': 'Converting to memoization solution will yield time complexity of n*1, 2*3 and space complexity of n*2*3, plus auxiliary stack space.', 'duration': 28.995, 'max_score': 741.239, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ741239.jpg'}], 'start': 612.284, 'title': 'Optimizing recursion and memoization for stock transactions', 'summary': 'Discusses optimizing recursion by identifying overlapping subproblems, emphasizing the importance of optimization and covers memoization to optimize a 3d dynamic programming solution for stock transactions, reducing time complexity to n*2*3.', 'chapters': [{'end': 662.853, 'start': 612.284, 'title': 'Optimizing recursion with overlapping', 'summary': 'Discusses the exponential time complexity of recursion, with an auxiliary stack space of v. it emphasizes the importance of optimizing recursion by identifying overlapping subproblems, which has been covered in previous 34 lectures.', 'duration': 50.569, 'highlights': ['Overlapping subproblems need to be identified for optimizing recursion, as discussed in previous 34 lectures.', 'Recursion has an exponential time complexity, resulting in TLE, with an auxiliary stack space of V.', 'Sequential understanding of the playlist is emphasized for comprehensive learning.', 'The depth of recursion increases with index plus 1, leading to an auxiliary stack space complexity of O(n).']}, {'end': 886.832, 'start': 662.853, 'title': 'Memoization for stock transactions', 'summary': 'Discusses using memoization to optimize a 3d dynamic programming solution for stock transactions, reducing time complexity to n*2*3 and addressing changing parameters involving index, buy, and cap.', 'duration': 223.979, 'highlights': ['The solution involves creating a 3D dynamic programming state of n*2*3, optimizing time complexity to n*2*3.', 'The changing parameters in the solution include index, buy, and cap, with a total of n different states for index and two different states for buy and three different states for cap.', 'The memoization solution reduces time complexity to n*2*3 and space complexity to n*2*3, while also accounting for auxiliary stack space.']}], 'duration': 274.548, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ612284.jpg', 'highlights': ['The memoization solution reduces time complexity to n*2*3 and space complexity to n*2*3, while also accounting for auxiliary stack space.', 'The solution involves creating a 3D dynamic programming state of n*2*3, optimizing time complexity to n*2*3.', 'Overlapping subproblems need to be identified for optimizing recursion, as discussed in previous 34 lectures.', 'The changing parameters in the solution include index, buy, and cap, with a total of n different states for index and two different states for buy and three different states for cap.', 'Recursion has an exponential time complexity, resulting in TLE, with an auxiliary stack space of V.']}, {'end': 1179.229, 'segs': [{'end': 922.665, 'src': 'embed', 'start': 887.915, 'weight': 1, 'content': [{'end': 888.736, 'text': 'Indeed, it does run.', 'start': 887.915, 'duration': 0.821}, {'end': 893.74, 'text': "Now, what's the next thing that we will do? We'll definitely try to have a 3DDP array.", 'start': 889.456, 'duration': 4.284}, {'end': 897.323, 'text': 'So generally, you can define something like vector, vector.', 'start': 894.04, 'duration': 3.283}, {'end': 900.385, 'text': 'This is how you define 3DDPs.', 'start': 897.923, 'duration': 2.462}, {'end': 904.649, 'text': 'Done Right after this, you can say the first state is n.', 'start': 900.926, 'duration': 3.723}, {'end': 906.911, 'text': 'Then just make sure you define the second state.', 'start': 904.649, 'duration': 2.262}, {'end': 908.312, 'text': 'And just go across.', 'start': 907.471, 'duration': 0.841}, {'end': 910.393, 'text': 'In the same way, just define the second state.', 'start': 908.572, 'duration': 1.821}, {'end': 914.317, 'text': "What's the second state? The second state, like I'll just, yeah.", 'start': 910.754, 'duration': 3.563}, {'end': 922.665, 'text': 'The second state is something like, Inside the 3D, there is a 2D, right? Of size 2x3.', 'start': 915.378, 'duration': 7.287}], 'summary': 'Defining and working with 3ddp array, including 2d size of 2x3.', 'duration': 34.75, 'max_score': 887.915, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ887915.jpg'}, {'end': 1001.183, 'src': 'embed', 'start': 940.509, 'weight': 0, 'content': [{'end': 947.411, 'text': 'And before returning, just make sure you have it memoized.', 'start': 940.509, 'duration': 6.902}, {'end': 950.174, 'text': 'So make sure you memorize it.', 'start': 949.113, 'duration': 1.061}, {'end': 956.077, 'text': "So once I've memorized it, also make sure this is memorized index by cap.", 'start': 950.514, 'duration': 5.563}, {'end': 973.728, 'text': 'Perfect Uh, and also before visiting, if any of these states are revisited, just make sure you do a return of DP of index by cap.', 'start': 960.059, 'duration': 13.669}, {'end': 976.72, 'text': 'Okay Perfect, it does run.', 'start': 974.388, 'duration': 2.332}, {'end': 979.764, 'text': "Let's quickly submit this and see if the memoization code is running fine.", 'start': 976.8, 'duration': 2.964}, {'end': 985.771, 'text': 'Okay, so we see that we are getting around 90% of score and it is giving us time limit exceeded.', 'start': 981.145, 'duration': 4.626}, {'end': 989.856, 'text': 'The probable reason is because we are having still auxiliary stack space.', 'start': 986.352, 'duration': 3.504}, {'end': 993.961, 'text': "So let's try to optimize this into the tabulation format and then we will see.", 'start': 990.376, 'duration': 3.585}, {'end': 997.32, 'text': 'we saw that the tabulation.', 'start': 995.519, 'duration': 1.801}, {'end': 1000.242, 'text': 'so we saw that the memory code gave you a tle right.', 'start': 997.32, 'duration': 2.922}, {'end': 1001.183, 'text': "so what's the next step?", 'start': 1000.242, 'duration': 0.941}], 'summary': 'Memoization code gave 90% score, but encountered time limit exceeded. optimize to tabulation format.', 'duration': 60.674, 'max_score': 940.509, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ940509.jpg'}, {'end': 1079.024, 'src': 'embed', 'start': 1046.996, 'weight': 3, 'content': [{'end': 1048.757, 'text': 'what are the base cases that you wrote?', 'start': 1046.996, 'duration': 1.761}, {'end': 1055.24, 'text': 'you said for any cap 0, any index n either cap 0 either n.', 'start': 1048.757, 'duration': 6.483}, {'end': 1062.163, 'text': 'that means whenever cap is 0, index and buy can be anything.', 'start': 1055.24, 'duration': 6.923}, {'end': 1065.325, 'text': 'index. i repeat, index and buy can be anything.', 'start': 1062.163, 'duration': 3.162}, {'end': 1069.957, 'text': 'If index is n, index and cap can be anything.', 'start': 1066.334, 'duration': 3.623}, {'end': 1071.358, 'text': 'Please hear me out properly.', 'start': 1070.497, 'duration': 0.861}, {'end': 1076.081, 'text': 'If index is n, index and cap can be anything.', 'start': 1071.918, 'duration': 4.163}, {'end': 1079.024, 'text': 'So, let me write.', 'start': 1076.682, 'duration': 2.342}], 'summary': 'Base cases: for cap 0, index n, cap can be anything. for index n, index and cap can be anything.', 'duration': 32.028, 'max_score': 1046.996, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1046996.jpg'}], 'start': 887.915, 'title': 'Optimizing 3ddp arrays and tabulation', 'summary': 'Discusses defining 3ddp arrays and memoization, emphasizing efficient array definition and memoization. it also covers optimizing code into tabulation format to address time limit issues, with an emphasis on base cases and recurrence for improved performance.', 'chapters': [{'end': 979.764, 'start': 887.915, 'title': 'Defining 3ddp arrays and memoization', 'summary': 'Discusses defining 3ddp arrays and memoization, emphasizing the process of defining the array and ensuring memoization to optimize the code for efficient execution.', 'duration': 91.849, 'highlights': ['Defining 3DDP arrays involves creating a vector of vectors to represent the array and carefully defining each state within the array.', 'Memoization is crucial for optimizing the code, ensuring that the results of expensive function calls are stored and reused to avoid redundant computations.', 'The process of defining 3DDP arrays and implementing memoization is critical for efficient code execution, impacting the performance and scalability of the program.']}, {'end': 1179.229, 'start': 981.145, 'title': 'Tabulation optimization for stack space', 'summary': 'Discusses optimizing the code into tabulation format to address time limit exceeded issue, emphasizing writing and implementing base cases and recurrence, to optimize auxiliary stack space and improve performance.', 'duration': 198.084, 'highlights': ['The chapter emphasizes converting the code into tabulation format to optimize auxiliary stack space and improve performance, aiming to address the time limit exceeded issue, with an observed score of around 90%.', 'It highlights the importance of writing and implementing base cases for different changing parameters, emphasizing the need to properly define base cases for index, buy, and cap, and explaining the significance of each base case with clear examples.', 'The transcript provides a detailed explanation of writing the base cases for index, buy, and cap, emphasizing the importance of correctly defining the base cases to ensure the proper functioning of the tabulation code.']}], 'duration': 291.314, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ887915.jpg', 'highlights': ['Converting code into tabulation format to optimize stack space and improve performance, aiming to address time limit issues, with a 90% observed score.', 'Defining 3DDP arrays involves creating a vector of vectors and carefully defining each state within the array.', 'Memoization is crucial for optimizing code, ensuring that results of expensive function calls are stored and reused to avoid redundant computations.', 'Importance of writing and implementing base cases for different changing parameters, emphasizing the need to properly define base cases for index, buy, and cap.']}, {'end': 1619.398, 'segs': [{'end': 1208.425, 'src': 'embed', 'start': 1179.98, 'weight': 2, 'content': [{'end': 1183.304, 'text': "That's how you convert this into a proper tabulated code.", 'start': 1179.98, 'duration': 3.324}, {'end': 1184.805, 'text': "So it's time to write the tabulation code.", 'start': 1183.324, 'duration': 1.481}, {'end': 1194.376, 'text': "So what we will do is we'll just make it zero, right? And we know there are base cases and the base cases will also have values as zero.", 'start': 1184.825, 'duration': 9.551}, {'end': 1200.223, 'text': "So practically thinking like there's no point because it's already assigned as zero initially.", 'start': 1194.817, 'duration': 5.406}, {'end': 1204.624, 'text': 'so writing conditions for base case will not make any sense.', 'start': 1200.743, 'duration': 3.881}, {'end': 1208.425, 'text': 'yes, i did write them in the ipad, but will it make sense?', 'start': 1204.624, 'duration': 3.801}], 'summary': 'Discusses writing tabulation code with base cases and zero values.', 'duration': 28.445, 'max_score': 1179.98, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1179980.jpg'}, {'end': 1379.641, 'src': 'heatmap', 'start': 1354.089, 'weight': 0.734, 'content': [{'end': 1361.023, 'text': "so once you've removed this, you know this will be dp of zero one and two, right.", 'start': 1354.089, 'duration': 6.934}, {'end': 1363.466, 'text': "so let's quickly omit this off as well.", 'start': 1361.023, 'duration': 2.443}, {'end': 1367.833, 'text': 'now try to run this and see if this is running fine.', 'start': 1363.466, 'duration': 4.367}, {'end': 1369.055, 'text': 'indeed, it is now.', 'start': 1367.833, 'duration': 1.222}, {'end': 1372.24, 'text': "let's try to submit this off and see if it is accepted.", 'start': 1369.055, 'duration': 3.185}, {'end': 1376.015, 'text': 'Indeed, it is accepted.', 'start': 1375.014, 'duration': 1.001}, {'end': 1379.641, 'text': 'So this is how you can easily change it into the tabulation format.', 'start': 1376.316, 'duration': 3.325}], 'summary': 'Successfully converted data to tabulation format, verified and submitted it, achieving acceptance.', 'duration': 25.552, 'max_score': 1354.089, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1354089.jpg'}, {'end': 1521.97, 'src': 'embed', 'start': 1496.303, 'weight': 0, 'content': [{'end': 1503.865, 'text': "so this is the space optimized solution where you you're definitely using a six size array which is as good as a constant array.", 'start': 1496.303, 'duration': 7.562}, {'end': 1514.248, 'text': 'so i can say the time complexity is n into two, into three, and the space complexity is constant, because two into three is just a six size array.', 'start': 1503.865, 'duration': 10.383}, {'end': 1518.089, 'text': "it's it's as good as a constant size array, right.", 'start': 1514.848, 'duration': 3.241}, {'end': 1521.97, 'text': 'so i can say the space complexity is constant as of now.', 'start': 1518.089, 'duration': 3.881}], 'summary': 'Space-optimized solution with time complexity of 2n*3 and constant space complexity.', 'duration': 25.667, 'max_score': 1496.303, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1496303.jpg'}, {'end': 1619.398, 'src': 'embed', 'start': 1595.402, 'weight': 4, 'content': [{'end': 1602.808, 'text': "So that's why I like try to be like, yes, but I don't think the solution should be even discussed in an interview.", 'start': 1595.402, 'duration': 7.406}, {'end': 1606.412, 'text': 'You should not come up with this because the interview will never expect you to come up with this.', 'start': 1602.849, 'duration': 3.563}, {'end': 1615.756, 'text': 'Either you say the n cross 2 cross 3 either you say that or either you go across and say the n cross 4 DP solution.', 'start': 1607.132, 'duration': 8.624}, {'end': 1619.398, 'text': 'Now you might be asking hey, what is n cross 4?', 'start': 1616.036, 'duration': 3.362}], 'summary': 'The interview solution should be n cross 2 cross 3 or n cross 4 dp, not discussed.', 'duration': 23.996, 'max_score': 1595.402, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1595402.jpg'}], 'start': 1179.98, 'title': 'Tabulation techniques in dynamic programming', 'summary': 'Covers writing tabulation code with emphasis on base cases and discusses the tabulation technique for dynamic programming, including space optimization with a time complexity of n*2*3 and constant space complexity.', 'chapters': [{'end': 1219.968, 'start': 1179.98, 'title': 'Tabulation code writing', 'summary': 'Discusses writing proper tabulation code, emphasizing the importance of base cases with a value of zero and the decision not to write conditions for base cases when they are already assigned as zero.', 'duration': 39.988, 'highlights': ['The importance of base cases with a value of zero is emphasized, as it is stated that writing conditions for base cases when they are already assigned as zero will not make any sense.', 'The decision not to write conditions for base cases when they are already assigned as zero is explained, with the rationale that it would only make sense if the base cases had a value other than zero.']}, {'end': 1619.398, 'start': 1219.968, 'title': 'Tabulation technique for dynamic programming', 'summary': 'Explains the tabulation technique for dynamic programming with detailed steps for space optimization, resulting in a time complexity of n*2*3 and constant space complexity.', 'duration': 399.43, 'highlights': ['The chapter explains the tabulation technique for dynamic programming with detailed steps for space optimization, resulting in a time complexity of n*2*3 and constant space complexity.', 'The space optimized solution uses a 6-size array, equivalent to a constant array, resulting in a time complexity of n*2*3 and constant space complexity.', 'The lecture also mentions alternative solutions, such as n*4 dp and using four different variables, but emphasizes the lack of intuitiveness and relevance to interview scenarios.']}], 'duration': 439.418, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1179980.jpg', 'highlights': ['The space optimized solution uses a 6-size array, equivalent to a constant array, resulting in a time complexity of n*2*3 and constant space complexity.', 'The chapter explains the tabulation technique for dynamic programming with detailed steps for space optimization, resulting in a time complexity of n*2*3 and constant space complexity.', 'The importance of base cases with a value of zero is emphasized, as it is stated that writing conditions for base cases when they are already assigned as zero will not make any sense.', 'The decision not to write conditions for base cases when they are already assigned as zero is explained, with the rationale that it would only make sense if the base cases had a value other than zero.', 'The lecture also mentions alternative solutions, such as n*4 dp and using four different variables, but emphasizes the lack of intuitiveness and relevance to interview scenarios.']}, {'end': 1900.154, 'segs': [{'end': 1649.916, 'src': 'embed', 'start': 1619.398, 'weight': 0, 'content': [{'end': 1621.219, 'text': 'Now, as of now, what did we do?', 'start': 1619.398, 'duration': 1.821}, {'end': 1632.805, 'text': "We stated let's start at the day 0, give him a permission of buy and have a maximum cap of 2 transactions, and then keep on doing buy a sell,", 'start': 1621.719, 'duration': 11.086}, {'end': 1638.67, 'text': 'buy a sell and whenever the sell is happening, Do a cap minus one.', 'start': 1632.805, 'duration': 5.865}, {'end': 1640.771, 'text': "That's what we have done in this particular solution.", 'start': 1638.73, 'duration': 2.041}, {'end': 1642.712, 'text': "But I'll not change it.", 'start': 1641.671, 'duration': 1.041}, {'end': 1643.893, 'text': "I'll not code it.", 'start': 1642.732, 'duration': 1.161}, {'end': 1645.314, 'text': "I'll just explain you the theory part.", 'start': 1644.013, 'duration': 1.301}, {'end': 1646.554, 'text': 'Probably you can code and submit.', 'start': 1645.334, 'duration': 1.22}, {'end': 1649.916, 'text': 'What if I say I will not have buy.', 'start': 1647.415, 'duration': 2.501}], 'summary': 'Implemented a strategy with a maximum of 2 transactions, reducing cap with each sell.', 'duration': 30.518, 'max_score': 1619.398, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1619398.jpg'}, {'end': 1702.423, 'src': 'embed', 'start': 1676.72, 'weight': 3, 'content': [{'end': 1684.843, 'text': "if i'm performing a buy, that's 0 or 2, or in short, can i say it's an even index,", 'start': 1676.72, 'duration': 8.123}, {'end': 1694.299, 'text': "it's an even number when i perform the buy portion and can i say It's the odd when I'm performing the sell?", 'start': 1684.843, 'duration': 9.456}, {'end': 1697.061, 'text': "It's the odd when I'm selling the stock.", 'start': 1694.86, 'duration': 2.201}, {'end': 1702.423, 'text': 'Make sense? So I can start from zero, and then I can go one, then I can go two, go three.', 'start': 1697.381, 'duration': 5.042}], 'summary': 'Perform buy at even index, sell at odd for stock transactions.', 'duration': 25.703, 'max_score': 1676.72, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1676720.jpg'}, {'end': 1777.796, 'src': 'embed', 'start': 1749.935, 'weight': 1, 'content': [{'end': 1756.559, 'text': "so whenever you performed all the four transactions or you have come to the end, that's when you return zero, perfect.", 'start': 1749.935, 'duration': 6.624}, {'end': 1757.76, 'text': 'what about the other thing?', 'start': 1756.559, 'duration': 1.201}, {'end': 1768.313, 'text': "can i say if the transaction number is even, this means it's a buy, or else it's a sell, or else it's a sell.", 'start': 1757.76, 'duration': 10.553}, {'end': 1771.774, 'text': 'and whenever it is a buy, how can you do a buy?', 'start': 1768.313, 'duration': 3.461}, {'end': 1775.575, 'text': 'you know you have to invest this much into the market.', 'start': 1771.774, 'duration': 3.801}, {'end': 1777.796, 'text': 'you move to the next day.', 'start': 1775.575, 'duration': 2.221}], 'summary': "Perform 4 transactions to end with zero. even transaction number is a buy, else it's a sell.", 'duration': 27.861, 'max_score': 1749.935, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1749935.jpg'}, {'end': 1871.59, 'src': 'embed', 'start': 1845.13, 'weight': 4, 'content': [{'end': 1855.217, 'text': 'then convert it into the space optimization and please post the space optimization or the tabulation code in the comment section.', 'start': 1845.13, 'duration': 10.087}, {'end': 1858.82, 'text': "like i can do this, but let's, let's have some homework for you.", 'start': 1855.217, 'duration': 3.603}, {'end': 1863.343, 'text': "so let's post the tabulation and the space optimization of this portion,", 'start': 1858.82, 'duration': 4.523}, {'end': 1871.59, 'text': 'where we use couple of variables index and transaction in the tabulation in the comment section.', 'start': 1863.343, 'duration': 8.247}], 'summary': 'Convert code for space optimization, post tabulation and space optimization code with index and transaction variables in comment section.', 'duration': 26.46, 'max_score': 1845.13, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1845130.jpg'}], 'start': 1619.398, 'title': 'Stock trading strategies and algorithmic transactions', 'summary': 'Discusses a stock trading strategy with a maximum cap of 2 transactions, involving alternating buy and sell actions. it also delves into algorithmic trading, demonstrating a recursive approach and encouraging implementation of memory code, tabulation, and space optimization.', 'chapters': [{'end': 1702.423, 'start': 1619.398, 'title': 'Stock trading strategy theory', 'summary': 'Discusses a stock trading strategy involving a maximum cap of 2 transactions and alternating buy and sell actions, with even indices representing buy and odd indices representing sell.', 'duration': 83.025, 'highlights': ['The strategy involves imposing a maximum cap of 2 transactions and performing buy and sell actions in an alternating manner, with even indices representing buy and odd indices representing sell.', 'Explaining the concept of using even indices for buy and odd indices for sell in the context of performing transactions.', 'Discussing the theoretical aspect of a stock trading strategy involving the use of even and odd indices to represent buy and sell actions.']}, {'end': 1900.154, 'start': 1702.883, 'title': 'Algorithmic trading transactions', 'summary': 'Discusses a trading algorithm that converts buy and sell decisions into transaction numbers, then demonstrates a recursive approach to the problem, and encourages viewers to implement the memory code, tabulation, and space optimization for the solution.', 'duration': 197.271, 'highlights': ['The algorithm converts buy and sell decisions into transaction numbers to express buy and sell via transaction numbers, aiming to perform all four transactions, with the base case reached when all transactions are performed, resulting in a return of zero.', 'The algorithm identifies buy and sell transactions based on whether the transaction number is even or odd, and executes the corresponding action of investing or selling in the market.', 'The speaker encourages viewers to implement the memory code, tabulation, and space optimization for the solution, and suggests posting the tabulation and space optimization code in the comment section for further practice and understanding.']}], 'duration': 280.756, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/-uQGzhYj8BQ/pics/-uQGzhYj8BQ1619398.jpg', 'highlights': ['The strategy involves imposing a maximum cap of 2 transactions and performing buy and sell actions in an alternating manner, with even indices representing buy and odd indices representing sell.', 'The algorithm converts buy and sell decisions into transaction numbers to express buy and sell via transaction numbers, aiming to perform all four transactions, with the base case reached when all transactions are performed, resulting in a return of zero.', 'The algorithm identifies buy and sell transactions based on whether the transaction number is even or odd, and executes the corresponding action of investing or selling in the market.', 'Explaining the concept of using even indices for buy and odd indices for sell in the context of performing transactions.', 'The speaker encourages viewers to implement the memory code, tabulation, and space optimization for the solution, and suggests posting the tabulation and space optimization code in the comment section for further practice and understanding.', 'Discussing the theoretical aspect of a stock trading strategy involving the use of even and odd indices to represent buy and sell actions.']}], 'highlights': ['The memoization solution reduces time complexity to n*2*3 and space complexity to n*2*3, accounting for auxiliary stack space.', 'The space optimized solution uses a 6-size array, equivalent to a constant array, resulting in a time complexity of n*2*3 and constant space complexity.', 'Converting code into tabulation format optimizes stack space and improves performance, addressing time limit issues, with a 90% observed score.', "The process emphasizes the importance of buy-sell transactions and the impact on market prices, as the decision-making process is influenced by the market's price and the individual's interest in buying or selling.", 'The concept of shuttle change in transactions is emphasized, focusing on the reduction of transaction numbers, which eventually means the number of transactions will get reduced by one.', 'The problem of maximizing stock profit by conducting at most two transactions is an extension of the buy and sell stock problem.', 'The strategy involves imposing a maximum cap of 2 transactions and performing buy and sell actions in an alternating manner, with even indices representing buy and odd indices representing sell.', 'The process of converting the previous code to the current problem is explained, highlighting the concept of being bounded by a certain number of transactions, specifically at most two.', 'The discussion covers the base cases for ending transactions, including the scenarios where no returns are obtained from the market due to exhaustion of days or transactions.', 'The decision not to write conditions for base cases when they are already assigned as zero is explained, with the rationale that it would only make sense if the base cases had a value other than zero.']}