What if, you were given an access to a particular stock?
What if, you could know the price of that stock prior to a day through that access?
What if, the stock price only changed everyday and not every second?
What if, you could hold a single stock each day?
So you know the price of the stock for today and for tomorrow.
You go and see, today its priced at ₹7. You also found out through your access, that tomorrow it will be priced at ₹10. So, will you buy and sell it tomorrow?
Hell yes! Why not. We are getting ₹3 profit just by doing so.
But, am I losing on selling it at a higher price the day after tomorrow?
What if, the price for the day after tomorrow was ₹17? Can I still make the same profit as ₹17 - ₹7 = ₹10 (price at day after tomorrow - price today)?
If I made a profit of ₹3 by buying today and selling tomorrow, I can do the same tomorrow, right? Since, I know day after tomorrow's price when I am living at tomorrow. So, a profit of ₹17 - ₹10 = ₹7 from it as well. Add to the previous profit of ₹3, gives ₹10, same as selling day after tomorrow directly.
Now, what if, the price for today was ₹10 and tomorrow it would be ₹7?
I would rather not buy.
Wait. Why? It could have been ₹17 the day after tomorrow.
Then did I miss a profit of ₹7 (price the day after tomorrow - price today = ₹17 - ₹10)?
But if it was ₹10 today, and ₹7 tomorrow, would it not be better to buy it tomorrow? Since it has got a lesser price than today.
Well yes!
So, did we see that we only need to know two days' prices (today's and tomorrow's) to make the best decisions?
Conclusion:
If today's price is higher than tomorrow's, lets not buy
If vice versa, lets buy today and sell tomorrow and add to the profit
We traversed once, two days at a time. So, ~O(n) where n is the number of days!
Here you go: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
See you, until next time;