What if, I was greedy?

Sometimes, "laalchi acche hein"!

  • 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;