{"id":1336,"date":"2024-01-06T13:00:00","date_gmt":"2024-01-06T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1336"},"modified":"2024-01-09T10:34:28","modified_gmt":"2024-01-09T10:34:28","slug":"best-time-to-buy-and-sell-stock-ii","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/best-time-to-buy-and-sell-stock-ii\/","title":{"rendered":"Best Time to Buy &amp; Sell Stock II Problem (with Solution)"},"content":{"rendered":"\n<p>In the context of data structures and algorithms, the real-life scenario of when to buy and sell stocks for Profit maximization in stock trading can be framed as a problem. In this article, we will learn about the \u201cBest Time to Buy and Sell Stock II\u201d problem is an extension of the famous problem \u201c<a href=\"https:\/\/favtutor.com\/articles\/best-time-to-buy-and-sell-stock-problem\">Best Time to Buy and Sell Stock<\/a>\u201d, which can be solved with the help of dynamic programming. <\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Best Time to Buy and Sell Stock II Problem<\/strong><\/h2>\n\n\n\n<p><strong>In the famous leetcode problem to find the best time to buy and sell stock, we are given daily stock prices in an array, the task is to maximize profit through strategic buying and selling decisions.<\/strong><\/p>\n\n\n\n<p>We can buy and sell on the same day. We have to analyze the array to identify optimal transactions and to return the maximum achievable profit in this stock trading scenario. For example:<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><strong>Input: <\/strong>prices = [8,1,5,3,6,4]<br><strong>Output:<\/strong> 7<\/p>\n\n\n\n<p>Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.<\/p>\n\n\n\n<p>The following guidelines need to be followed:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>To sell the stock, we must first buy it on the same or any previous day.<\/li>\n\n\n\n<li>We can buy and sell the stock any number of times.<\/li>\n\n\n\n<li>We first buy a stock and then sell it. After selling we can buy and sell again. But we can\u2019t sell before buying and can\u2019t buy before selling any previously bought stock.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Recursive Approach<\/strong><\/h2>\n\n\n\n<p>As in this problem, we can buy and sell stocks multiple times and we have to maximize profit so we have to explore all possibilities, i.e. On each day we have two choices either to do nothing and move to the next day or to buy\/sell (based on the last transaction) and find out the profit.\u00a0 We can solve it using <a href=\"https:\/\/favtutor.com\/blogs\/recursion-cpp\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/blogs\/recursion-cpp\">recursion<\/a> easily.<\/p>\n\n\n\n<p>So to start our recursive solution we need to express our problem in terms of index: We will start from day 1 and will go to the last day exploring all possibilities of each index based on the previous transaction.<\/p>\n\n\n\n<p>Here are the steps to be performed for recurrence relation:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>We will start from day 1 and declare a buy variable that tells us on a particular day whether we can buy or sell the stock.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"239\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-d-1024x239.jpg\" alt=\"Either buy or sell the stock\" class=\"wp-image-1341\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-d-1024x239.jpg 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-d-300x70.jpg 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-d-768x179.jpg 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-d-750x175.jpg 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-d-1140x266.jpg 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-d.jpg 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>Every day we have two choices to either buy\/sell stock based on previous transactions or to do nothing and move on to the next day.<\/li>\n<\/ul>\n\n\n\n<p><strong>Case 1:<\/strong><\/p>\n\n\n\n<p>When buy == 0 where we can buy stock on a particular day so we have 2 options&nbsp;<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>To skip the transaction and go on to the following day:\n<ul class=\"wp-block-list\">\n<li>Since there will be no net profit from the current transaction, we will call f(ind+1,0) recursively to determine the maximum profit that may be made beginning on the next day.&nbsp;<\/li>\n\n\n\n<li>The &#8216;buy&#8217; variable value will remain at 0, meaning that we can purchase the stock the following day, since we haven&#8217;t purchased it yet.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If we decide to buy the stock on a particular day, it means we are choosing an alternative option.\n<ul class=\"wp-block-list\">\n<li>In this case, the profit we gain will be negative, represented by -Arr[i].&nbsp;<\/li>\n\n\n\n<li>This happens because we use our own money to buy the stock.&nbsp;<\/li>\n\n\n\n<li>The profit becomes zero since we are essentially spending our cash. By making a recursive call to f(ind+1,1), we figure out the best profit starting from the next day.&nbsp;<\/li>\n\n\n\n<li>Once we buy the stock, the &#8220;buy&#8221; variable becomes 1, indicating that we can&#8217;t buy it again and must sell it the following day<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p><strong>Case 2:<\/strong><\/p>\n\n\n\n<p>When buy == 1 where we can sell previously bought stock<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Choosing not to make any transaction means moving to the next day.\n<ul class=\"wp-block-list\">\n<li>In this situation, the profit earned from the current transaction is zero.&nbsp;<\/li>\n\n\n\n<li>To find the maximum profit from the next day onward, we use a recursive call to f(ind+1,1).&nbsp;<\/li>\n\n\n\n<li>Since we haven&#8217;t purchased the stock, the &#8216;buy&#8217; variable stays at 1, signaling that we can only sell the stock the following day and cannot make another purchase.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Another choice is to sell the stock in the present day.\n<ul class=\"wp-block-list\">\n<li>Here, the profit gained from the current transaction is +Arr[i].&nbsp;<\/li>\n\n\n\n<li>Since we are selling the stock, we are receiving money, resulting in a positive profit.&nbsp;<\/li>\n\n\n\n<li>To find the highest profit starting from the next day, we use a recursive call to f(ind+1,0).&nbsp;<\/li>\n\n\n\n<li>After selling the stock, the &#8216;buy&#8217; variable switches to 0, signalling that we can purchase the stock the following day.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"414\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-d-1024x414.jpg\" alt=\"Choices on particular day\" class=\"wp-image-1342\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-d-1024x414.jpg 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-d-300x121.jpg 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-d-768x310.jpg 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-d-750x303.jpg 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-d-1140x461.jpg 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-d.jpg 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<p>To return maximum profit we have to take the maximum value of both cases. If ind==n, we simply return 0 because it indicates that we have completed trading on all days and that there is no more money available.<\/p>\n\n\n\n<p>The worst-case time complexity of the recursive solution is exponential, O(2^n), where n is the number of days or the size of the input array.<\/p>\n\n\n\n<p>The space complexity is linear, O(n), where n is the number of days or the size of the input array. This is because the space required by the call stack is directly related to the number of recursive calls, which, in turn, is determined by the number of days.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Dynamic Programming Approach<\/strong><\/h2>\n\n\n\n<p>To optimize the recursive solution, we observe overlapping subproblems and introduce a dynamic programming approach:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Create a 2D array named dp with dimensions [n][2], where &#8216;n&#8217; is the size of the input array. This array will store solutions for subproblems and Initialize the dp array with -1.<\/li>\n\n\n\n<li>When calculating a solution for specific parameters (e.g., f(ind, buy)), first check if it&#8217;s already computed using the dp array (i.e., dp[ind][buy] != -1).<\/li>\n\n\n\n<li>If the solution is already available, return the stored value from the dp array.<\/li>\n<\/ul>\n\n\n\n<ul class=\"wp-block-list\">\n<li>If not, compute the solution using the standard recursive relation. Before exiting the function, update dp[ind][buy] with the calculated solution.<\/li>\n\n\n\n<li>This dynamic programming approach helps avoid redundant calculations by storing and reusing previously computed results, enhancing the efficiency of the solution.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is the C++ program that uses dynamic programming approach:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;iostream&gt;\n#include &lt;vector&gt;\n\nusing namespace std;\n\nint help(int ind, int buy, vector&lt;int&gt;&amp; prices, vector&lt;vector&lt;int&gt;&gt;&amp; dp) {\n    if (ind == prices.size())\n        return 0;\n\n    int profit = 0;\n\n    if (dp[ind][buy] != -1)\n        return dp[ind][buy];\n\n    if (buy) {\n        profit = max((-prices[ind] + help(ind + 1, 0, prices, dp)), help(ind + 1, 1, prices, dp));\n    } else {\n        profit = max((prices[ind] + help(ind + 1, 1, prices, dp)), help(ind + 1, 0, prices, dp));\n    }\n\n    return dp[ind][buy] = profit;\n}\n\nint maxProfit(vector&lt;int&gt;&amp; prices) {\n    vector&lt;vector&lt;int&gt;&gt; dp(prices.size() + 1, vector&lt;int&gt;(2, -1));\n    return help(0, 1, prices, dp);\n}\n\nint main() {\n    vector&lt;int&gt; prices = {8, 1, 5, 3, 6, 4};\n\n    \/\/ Call the maxProfit function and print the result\n    cout &lt;&lt; &quot;The maximum profit that can be generated is &quot; &lt;&lt; maxProfit(prices) &lt;&lt; endl;\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Here is the solution in Java:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Arrays;\n\npublic class StockProfit {\n\n    static int help(int ind, int buy, int[] prices, int[][] dp) {\n        if (ind == prices.length)\n            return 0;\n\n        int profit = 0;\n\n        if (dp[ind][buy] != -1)\n            return dp[ind][buy];\n\n        if (buy == 1) {\n            profit = Math.max((-prices[ind] + help(ind + 1, 0, prices, dp)), help(ind + 1, 1, prices, dp));\n        } else {\n            profit = Math.max((prices[ind] + help(ind + 1, 1, prices, dp)), help(ind + 1, 0, prices, dp));\n        }\n\n        return dp[ind][buy] = profit;\n    }\n\n    static int maxProfit(int[] prices) {\n        int n = prices.length;\n        int[][] dp = new int[n + 1][2];\n        for (int[] row : dp) {\n            Arrays.fill(row, -1);\n        }\n        return help(0, 1, prices, dp);\n    }\n\n    public static void main(String[] args) {\n        int[] prices = {8, 1, 5, 3, 6, 4};\n\n        \/\/ Call the maxProfit function and print the result\n        System.out.println(&quot;The maximum profit that can be generated is &quot; + maxProfit(prices));\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>You can implement it in Python as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def help(ind, buy, prices, dp):\n    if ind == len(prices):\n        return 0\n\n    if dp[ind][buy] != -1:\n        return dp[ind][buy]\n\n    if buy:\n        profit = max((-prices[ind] + help(ind + 1, 0, prices, dp)), help(ind + 1, 1, prices, dp))\n    else:\n        profit = max((prices[ind] + help(ind + 1, 1, prices, dp)), help(ind + 1, 0, prices, dp))\n\n    dp[ind][buy] = profit\n    return profit\n\ndef max_profit(prices):\n    n = len(prices)\n    dp = [[-1] * 2 for _ in range(n + 1)]\n    return help(0, 1, prices, dp)\n\nif __name__ == &quot;__main__&quot;:\n    prices = [8, 1, 5, 3, 6, 4]\n\n    # Call the max_profit function and print the result\n    print(&quot;The maximum profit that can be generated is&quot;, max_profit(prices))<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>The maximum profit that can be generated is 7<\/code><\/pre>\n\n\n\n<p>The time complexity is O(N*2) because there are N*2 states therefore at max \u2018N*2\u2019 new problems will be solved and we are running a for loop for \u2018N\u2019 times to calculate the total sum. The Space Complexity is O(N*2) + O(N) because We are using a recursion stack space(O(N)) and a 2D array ( O(N*2)).<\/p>\n\n\n\n<p>Here is brief comparison of both the approaches:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Approach&nbsp;<\/strong><\/td><td><strong>Time complexity<\/strong><\/td><td><strong>Space complexity<\/strong><\/td><td><strong>Details&nbsp;<\/strong><\/td><\/tr><tr><td>Recursive Approach<\/td><td>O(2^N)<\/td><td>O(N)<\/td><td>Because the number of recursive calls at each level of the tree doubles, leading to an exponential growth in the number of total calls.<\/td><\/tr><tr><td>Dynamic programming Approach<\/td><td>O(N*2)<\/td><td>O(N*2) + O(N)<\/td><td>There are N*2 states therefore at max \u2018N*2\u2019 new problems will be solved and we are running a for loop for \u2018N\u2019 times to calculate the total sum.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In Conclusion, the Best Time to Buy and Sell Stock II <a href=\"https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock-ii\/\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock-ii\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> can be easily solved using a recursive approach and it can be further optimized by using Dynamic Programming. It is one of the most asked problems in the interviews. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>In the context of data structures and algorithms, the real-life scenario of when to buy and sell stocks for Profit maximization in stock trading can be framed as a problem. In this article, we will learn about the \u201cBest Time to Buy and Sell Stock II\u201d problem is an extension of the famous problem \u201cBest [&hellip;]<\/p>\n","protected":false},"author":12,"featured_media":1338,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1336","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1336","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1336"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1336\/revisions"}],"predecessor-version":[{"id":1354,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1336\/revisions\/1354"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1338"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1336"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1336"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}