{"id":415,"date":"2025-06-29T15:23:09","date_gmt":"2025-06-29T09:53:09","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=415"},"modified":"2025-06-29T15:23:11","modified_gmt":"2025-06-29T09:53:11","slug":"best-time-to-buy-and-sell-stock","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/","title":{"rendered":"Best Time to Buy and Sell Stock | Leetcode 121 | Explained with Images"},"content":{"rendered":"\n<p>You are given an array&nbsp;<code>prices<\/code>&nbsp;where&nbsp;<code>prices[i]<\/code>&nbsp;is the price of a given stock on the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;day.<\/p>\n\n\n\n<p>You want to maximize your profit by choosing a&nbsp;<strong>single day<\/strong>&nbsp;to buy one stock and choosing a&nbsp;<strong>different day in the future<\/strong>&nbsp;to sell that stock.<\/p>\n\n\n\n<p>Return&nbsp;<em>the maximum profit you can achieve from this transaction<\/em>. If you cannot achieve any profit, return&nbsp;<code>0<\/code>.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock\/description\/\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>Example 1:<\/strong><br><strong>Input:<\/strong> prices = [7,1,5,3,6,4]<br><strong>Output:<\/strong> 5<br><strong>Explanation:<\/strong> Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.<br><em>Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.<\/em><\/p>\n\n\n\n<p><strong>Example 2:<\/strong><br><strong>Input:<\/strong> prices = [7,6,4,3,1]<br><strong>Output:<\/strong> 0<br><strong>Explanation:<\/strong> In this case, no transactions are done and the max profit = 0.<\/p>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>1 &lt;= prices.length &lt;= 10<sup>5<\/sup><\/li>\n\n\n\n<li>0 &lt;= prices[i] &lt;= 10<sup>4<\/sup><\/li>\n<\/ul>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-64b0a396-2192-46c6-b312-bee79d39d51c\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#0-brute-force-solution\" style=\"\">BRUTE FORCE SOLUTION<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#1-1-understanding-the-problem-\" style=\"\">1. Understanding the Problem<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#2-2-grasping-the-strategy-brute-force-approach-\" style=\"\">2. Grasping the Strategy: Brute-Force Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#3-3-code-\" style=\"\">3. Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#4-4-dry-run-\" style=\"\">4. Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#5-5-time-and-space-complexity-\" style=\"\">5. Time and Space Complexity<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#6-optimal-solution\" style=\"\">OPTIMAL SOLUTION<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#7-1-understanding-the-problem-\" style=\"\">1. Understanding the Problem<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#8-2-grasping-the-strategy-optimized-linear-approach-\" style=\"\">2. Grasping the Strategy: Optimized Linear Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#9-3-code-\" style=\"\">3. Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#10-4-visualizing-the-process-\" style=\"\">4. Visualizing the Process<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/best-time-to-buy-and-sell-stock\/#11-5-time-and-space-complexity-\" style=\"\">5. Time and Space Complexity<\/a><\/li><\/ul><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-brute-force-solution\">BRUTE FORCE SOLUTION<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-1-understanding-the-problem-\"><strong>1. Understanding the Problem<\/strong><\/h3>\n\n\n\n<p><strong>Objective:<\/strong><\/p>\n\n\n\n<p>Given an integer array prices, where prices[i] represents the price of a given stock on the ithi^{th}ith day, you aim to maximize your profit by choosing <strong>exactly one day to buy one stock<\/strong> and <strong>choosing a different day in the future to sell that stock<\/strong>. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.<\/p>\n\n\n\n<p><strong>Problem Statement (LeetCode Reference):<\/strong><\/p>\n\n\n\n<p>You are given an array prices where prices[i] is the price of a given stock on the ithi^{th}ith day.<\/p>\n\n\n\n<p>You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.<\/p>\n\n\n\n<p>Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Input:<\/strong><strong><br><\/strong>prices = [7,1,5,3,6,4]<\/li>\n\n\n\n<li><strong>Output:<\/strong><strong><br><\/strong>5<\/li>\n\n\n\n<li><strong>Explanation:<br><\/strong>Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 &#8211; 1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price and days must follow.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-2-grasping-the-strategy-brute-force-approach-\"><strong>2. Grasping the Strategy: Brute-Force Approach<\/strong><\/h3>\n\n\n\n<p>The provided maxProfit function employs a <strong>brute-force approach<\/strong> to solve the problem. Here&#8217;s a high-level overview of the strategy:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Iterate Through All Possible Pairs of Days:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Use two nested loops to consider every possible pair of days where the first day (iii) is the buying day and the second day (jjj) is the selling day.<\/li>\n\n\n\n<li>The <strong>outer loop<\/strong> (for i in range(n)) selects the <strong>buying day<\/strong>.<\/li>\n\n\n\n<li>The <strong>inner loop<\/strong> (for j in range(i + 1, n)) selects the <strong>selling day<\/strong>, ensuring that the selling day is after the buying day.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Calculate the Profit for Each Valid Pair:<\/strong>\n<ul class=\"wp-block-list\">\n<li>For each pair (i,j)(i, j)(i,j), check if the selling price (prices[j]) is higher than the buying price (prices[i]).<\/li>\n\n\n\n<li>If so, calculate the profit (prices[j] &#8211; prices[i]).<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Track the Maximum Profit:<\/strong>\n<ul class=\"wp-block-list\">\n<li>Compare the calculated profit with the current maximum profit (maxPro).<\/li>\n\n\n\n<li>Update maxPro if the new profit is greater.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Return the Maximum Profit:<\/strong>\n<ul class=\"wp-block-list\">\n<li>After examining all possible pairs, return maxPro, which holds the largest profit found. If no profit is possible, maxPro remains 0.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p><strong>Visualization:<\/strong><\/p>\n\n\n\n<p>Imagine you&#8217;re at a stock market, and you have the opportunity to buy and sell a stock. For each day, you decide whether to buy the stock on that day and then consider selling it on any future day to maximize your profit.<\/p>\n\n\n\n<p><strong>Analogy:<\/strong><\/p>\n\n\n\n<p>Think of the array as a timeline of stock prices. Your goal is to find the lowest point to buy and the highest point after that to sell, ensuring that the selling day comes after the buying day.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-3-code-\"><strong>3. Code<\/strong><\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def maxProfit(self, prices: List[int]) -&gt; int:\n        maxPro = 0\n        n = len(prices)\n        for i in range(n):\n            for j in range(i + 1, n):\n                if prices[j] &gt; prices[i]:\n                    maxPro = max(prices[j] - prices[i], maxPro)\n        return maxPro\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">maxProfit<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">prices<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        maxPro = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        n = <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(prices)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> j <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, n):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> prices[j] &gt; prices[i]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    maxPro = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(prices[j] - prices[i], maxPro)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> maxPro<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-4-dry-run-\"><strong>4. Dry Run<\/strong><\/h3>\n\n\n\n<p>Let&#8217;s go through the code step by step, using images to illustrate the detailed dry run process.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-10-1024x576.png\" alt=\"\" class=\"wp-image-417\" srcset=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-10-1024x576.png 1024w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-10-300x169.png 300w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-10-768x432.png 768w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-10-1536x864.png 1536w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-10-150x84.png 150w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-10-450x253.png 450w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-10-1200x675.png 1200w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-10.png 1600w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" width=\"1024\" height=\"576\" src=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-11-1024x576.png\" alt=\"\" class=\"wp-image-418\" srcset=\"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-11-1024x576.png 1024w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-11-300x169.png 300w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-11-768x432.png 768w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-11-1536x864.png 1536w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-11-150x84.png 150w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-11-450x253.png 450w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-11-1200x675.png 1200w, https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/image-11.png 1600w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-5-time-and-space-complexity-\"><strong>5. Time and Space Complexity<\/strong><\/h3>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(n<sup>2<\/sup>)<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Explanation:<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>Outer Loop (<\/strong><strong>for i in range(n)<\/strong><strong>):<\/strong><strong><br><\/strong>Iterates n times, where n is the length of the prices array.<\/li>\n\n\n\n<li><strong>Inner Loop (<\/strong><strong>for j in range(i + 1, n)<\/strong><strong>):<\/strong><strong><br><\/strong>For each i, iterates approximately n &#8211; i &#8211; 1 times.<\/li>\n\n\n\n<li><strong>Overall:<\/strong><strong><br><\/strong>The combination of two nested loops results in a <strong>quadratic time complexity<\/strong>, O(n<sup>2<\/sup>), meaning that the execution time grows proportionally to the square of the input size. This approach is inefficient for large datasets.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(1)<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Explanation:<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>Variables Used:<\/strong>\n<ul class=\"wp-block-list\">\n<li>maxPro: Stores the maximum profit found so far.<\/li>\n\n\n\n<li>n: Stores the length of the prices array.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Utilization:<\/strong><strong><br><\/strong>The function uses a <strong>constant amount of additional space<\/strong>, regardless of the input size. No extra data structures (like arrays or hash maps) are used that scale with the input.<\/li>\n\n\n\n<li><strong>Overall:<\/strong><strong><br><\/strong>The <strong>space complexity<\/strong> is <strong>constant<\/strong>, O(1), making the function space-efficient.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p><strong>Efficiency Note:<\/strong><\/p>\n\n\n\n<p>While the brute-force approach correctly identifies the maximum profit by examining all possible pairs of days, its <strong>quadratic time complexity<\/strong> makes it impractical for large input sizes. For example, an array of size 10^5 would result in approximately 10<sup>10<\/sup> operations, leading to significant performance delays.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-optimal-solution\">OPTIMAL SOLUTION<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-1-understanding-the-problem-\"><strong>1. Understanding the Problem<\/strong><\/h3>\n\n\n\n<p><strong>Objective:<\/strong><\/p>\n\n\n\n<p>Given an integer array prices, where prices[i] represents the price of a given stock on the i<em><sup>th<\/sup><\/em> day, you aim to maximize your profit by choosing <strong>exactly one day to buy one stock<\/strong> and <strong>choosing a different day in the future to sell that stock<\/strong>. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.<\/p>\n\n\n\n<p><strong>Problem Statement (LeetCode Reference):<\/strong><\/p>\n\n\n\n<p>You are given an array prices where prices[i] is the price of a given stock on the i<em><sup>th<\/sup><\/em> day.<\/p>\n\n\n\n<p>You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.<\/p>\n\n\n\n<p>Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Input:<\/strong><strong><br><\/strong>prices = [7,1,5,3,6,4]<\/li>\n\n\n\n<li><strong>Output:<\/strong><strong><br><\/strong>5<\/li>\n\n\n\n<li><strong>Explanation:<\/strong><strong><br><\/strong>Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 &#8211; 1 = 5.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"8-2-grasping-the-strategy-optimized-linear-approach-\"><strong>2. Grasping the Strategy: Optimized Linear Approach<\/strong><\/h3>\n\n\n\n<p>The provided maxProfit function employs an <strong>optimized linear approach<\/strong> to solve the problem with <strong>linear time complexity<\/strong>. Here&#8217;s a high-level overview of the strategy:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialization:<\/strong>\n<ul class=\"wp-block-list\">\n<li>max_profit = 0:<br>Initialize the maximum profit to 0. This variable will keep track of the highest profit found.<\/li>\n\n\n\n<li>min_price = float(&#8220;inf&#8221;):<br>Initialize min_price to positive infinity. This variable will track the lowest price encountered so far.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Iterate Through the Array:<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>Loop (<\/strong><strong>for i in range(len(prices))<\/strong><strong>):<\/strong><strong><br><\/strong>Traverse each element in the array using its index i.<\/li>\n\n\n\n<li><strong>Update Minimum Price (<\/strong><strong>min_price<\/strong><strong>):<\/strong><strong><br><\/strong>At each step, update min_price to be the minimum of the current min_price and prices[i]. This ensures that min_price always holds the lowest price up to the current day.<\/li>\n\n\n\n<li><strong>Calculate Potential Profit and Update Maximum Profit (<\/strong><strong>max_profit<\/strong><strong>):<\/strong><strong><br><\/strong>Calculate the potential profit by subtracting the current min_price from prices[i] (i.e., prices[i] &#8211; min_price). Update max_profit if this potential profit is greater than the current max_profit.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Return the Result:<\/strong>\n<ul class=\"wp-block-list\">\n<li>After traversing the entire array, return the value of max_profit, which holds the largest profit found. If no profit is possible, max_profit remains 0.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p><strong>Visualization:<\/strong><\/p>\n\n\n\n<p>Imagine you&#8217;re at a stock market, and you&#8217;re tracking the lowest price you&#8217;ve seen so far. As you move through each day&#8217;s price, you calculate the profit you&#8217;d make if you sold on that day by subtracting the lowest price from the current price. You keep updating your maximum profit as you find better opportunities.<\/p>\n\n\n\n<p><strong>Analogy:<\/strong><\/p>\n\n\n\n<p>Think of the array as a timeline of stock prices. Your goal is to find the lowest valley (minimum price) and the highest peak (maximum price after the valley) to maximize your elevation gain (profit), ensuring that the peak comes after the valley.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-3-code-\"><strong>3. Code<\/strong><\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def maxProfit(self, prices: List[int]) -&gt; int:\n        max_profit = 0\n        min_price = float(&quot;inf&quot;)\n        for i in range(len(prices)):\n            min_price = min(min_price, prices[i])\n            max_profit = max(max_profit, prices[i] - min_price)\n        return max_profit\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">maxProfit<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">prices<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]) -&gt; <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        max_profit = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        min_price = <\/span><span style=\"color: #4EC9B0\">float<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #CE9178\">&quot;inf&quot;<\/span><span style=\"color: #D4D4D4\">)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(prices)):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            min_price = <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(min_price, prices[i])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            max_profit = <\/span><span style=\"color: #DCDCAA\">max<\/span><span style=\"color: #D4D4D4\">(max_profit, prices[i] - min_price)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> max_profit<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<p>Let&#8217;s walk through how the maxProfit function operates using an illustrative example.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Input:<\/strong><strong><br><\/strong>prices = [7,1,5,3,6,4]<\/li>\n\n\n\n<li><strong>Execution Steps:<\/strong>\n<ol class=\"wp-block-list\">\n<li><strong>Initialization:<\/strong>\n<ul class=\"wp-block-list\">\n<li>max_profit = 0<\/li>\n\n\n\n<li>min_price = float(&#8220;inf&#8221;)<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Iteration Through the Array:<\/strong><\/li>\n<\/ol>\n<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td><strong>Day (<\/strong><strong>i<\/strong><strong>)<\/strong><\/td><td><strong>Price (<\/strong><strong>prices[i]<\/strong><strong>)<\/strong><\/td><td><strong>min_price<\/strong><strong> Calculation<\/strong><\/td><td><strong>max_profit<\/strong><strong> Calculation<\/strong><\/td><td><strong>max_profit<\/strong><strong> Update<\/strong><\/td><\/tr><tr><td>0<\/td><td>7<\/td><td>min_price = min(inf, 7) = 7<\/td><td>profit = 7 &#8211; 7 = 0<\/td><td>max_profit = max(0, 0) = 0<\/td><\/tr><tr><td>1<\/td><td>1<\/td><td>min_price = min(7, 1) = 1<\/td><td>profit = 1 &#8211; 1 = 0<\/td><td>max_profit = max(0, 0) = 0<\/td><\/tr><tr><td>2<\/td><td>5<\/td><td>min_price = min(1, 5) = 1<\/td><td>profit = 5 &#8211; 1 = 4<\/td><td>max_profit = max(0, 4) = 4<\/td><\/tr><tr><td>3<\/td><td>3<\/td><td>min_price = min(1, 3) = 1<\/td><td>profit = 3 &#8211; 1 = 2<\/td><td>max_profit = max(4, 2) = 4<\/td><\/tr><tr><td>4<\/td><td>6<\/td><td>min_price = min(1, 6) = 1<\/td><td>profit = 6 &#8211; 1 = 5<\/td><td>max_profit = max(4, 5) = 5<\/td><\/tr><tr><td>5<\/td><td>4<\/td><td>min_price = min(1, 4) = 1<\/td><td>profit = 4 &#8211; 1 = 3<\/td><td>max_profit = max(5, 3) = 5<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<ol start=\"3\" class=\"wp-block-list\">\n<li><strong>Final Result:<\/strong>\n<ul class=\"wp-block-list\">\n<li>After traversing the entire array, the maximum profit found is 5, achieved by buying on day 1 (price = 1) and selling on day 4 (price = 6).<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Return:<\/strong>\n<ul class=\"wp-block-list\">\n<li>The function returns 5.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-4-visualizing-the-process-\"><strong>4. Visualizing the Process<\/strong><\/h3>\n\n\n\n<p>To better comprehend how the optimized linear approach works, let&#8217;s visualize the traversal and the state of the variables at each step.<\/p>\n\n\n\n<p>Array: [7, 1, 5, 3, 6, 4]<\/p>\n\n\n\n<p>Index:&nbsp; 0&nbsp; 1&nbsp; 2&nbsp; 3&nbsp; 4&nbsp; 5<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Initial State:<\/strong>\n<ul class=\"wp-block-list\">\n<li>max_profit = 0<\/li>\n\n\n\n<li>min_price = \u221e<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Steps:<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>Day 0 (Price = 7):<\/strong>\n<ul class=\"wp-block-list\">\n<li>min_price = min(\u221e, 7) = 7<\/li>\n\n\n\n<li>profit = 7 &#8211; 7 = 0<\/li>\n\n\n\n<li>max_profit = max(0, 0) = 0<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Day 1 (Price = 1):<\/strong>\n<ul class=\"wp-block-list\">\n<li>min_price = min(7, 1) = 1<\/li>\n\n\n\n<li>profit = 1 &#8211; 1 = 0<\/li>\n\n\n\n<li>max_profit = max(0, 0) = 0<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Day 2 (Price = 5):<\/strong>\n<ul class=\"wp-block-list\">\n<li>min_price = min(1, 5) = 1<\/li>\n\n\n\n<li>profit = 5 &#8211; 1 = 4<\/li>\n\n\n\n<li>max_profit = max(0, 4) = 4<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Day 3 (Price = 3):<\/strong>\n<ul class=\"wp-block-list\">\n<li>min_price = min(1, 3) = 1<\/li>\n\n\n\n<li>profit = 3 &#8211; 1 = 2<\/li>\n\n\n\n<li>max_profit = max(4, 2) = 4<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Day 4 (Price = 6):<\/strong>\n<ul class=\"wp-block-list\">\n<li>min_price = min(1, 6) = 1<\/li>\n\n\n\n<li>profit = 6 &#8211; 1 = 5<\/li>\n\n\n\n<li>max_profit = max(4, 5) = 5<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Day 5 (Price = 4):<\/strong>\n<ul class=\"wp-block-list\">\n<li>min_price = min(1, 4) = 1<\/li>\n\n\n\n<li>profit = 4 &#8211; 1 = 3<\/li>\n\n\n\n<li>max_profit = max(5, 3) = 5<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Final State:<\/strong>\n<ul class=\"wp-block-list\">\n<li>max_profit = 5<\/li>\n\n\n\n<li>The subarray contributing to max_profit is buying on day 1 and selling on day 4.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-5-time-and-space-complexity-\"><strong>5. Time and Space Complexity<\/strong><\/h3>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(n)<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Explanation:<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>Single Pass Traversal:<\/strong><strong><br><\/strong>The function iterates through the array prices <strong>once<\/strong>, performing constant-time operations at each step.<\/li>\n\n\n\n<li><strong>Loop Operations:<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>Finding Minimum Price (<\/strong><strong>min_price = min(min_price, prices[i])<\/strong><strong>):<\/strong><strong><br><\/strong>Takes constant time.<\/li>\n\n\n\n<li><strong>Calculating and Updating Maximum Profit (<\/strong><strong>max_profit = max(max_profit, prices[i] &#8211; min_price)<\/strong><strong>):<\/strong><strong><br><\/strong>Takes constant time.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Overall:<\/strong><strong><br><\/strong>Since all operations within the loop are constant time and the loop runs n times (where n is the length of prices), the <strong>total time complexity<\/strong> is <strong>linear<\/strong>, O(n).<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(1)<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Explanation:<\/strong>\n<ul class=\"wp-block-list\">\n<li><strong>Variables Used:<\/strong>\n<ul class=\"wp-block-list\">\n<li>max_profit: Stores the maximum profit found so far.<\/li>\n\n\n\n<li>min_price: Stores the minimum price encountered so far.<\/li>\n\n\n\n<li>n: Stores the length of the prices array.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Space Utilization:<\/strong><strong><br><\/strong>The function uses a <strong>constant amount of additional space<\/strong>, regardless of the input size. No extra data structures (like arrays or hash maps) are used that scale with the input.<\/li>\n\n\n\n<li><strong>Overall:<\/strong><strong><br><\/strong>The <strong>space complexity<\/strong> is <strong>constant<\/strong>, O(1), making the function space-efficient.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<p><strong>Efficiency Note:<\/strong><\/p>\n\n\n\n<p>This optimized linear approach is highly efficient for the Best Time to Buy and Sell Stock problem due to its linear time and constant space complexities. It ensures that even for large datasets, the function performs optimally without unnecessary computational overhead.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/www.codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array&nbsp;prices&nbsp;where&nbsp;prices[i]&nbsp;is the price of a given stock on the&nbsp;ith&nbsp;day. You want to maximize your profit by choosing a&nbsp;single day&nbsp;to buy one stock and choosing a&nbsp;different day in the future&nbsp;to sell that stock. Return&nbsp;the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return&nbsp;0. Here&#8217;s the [Problem<\/p>\n","protected":false},"author":1,"featured_media":419,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,4],"tags":[7,8],"class_list":{"0":"post-415","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-beginner","9":"tag-array","10":"tag-easy"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/best-time-to-buy-and-sell-stock-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/415","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=415"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/415\/revisions"}],"predecessor-version":[{"id":420,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/415\/revisions\/420"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/419"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=415"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=415"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=415"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}