Solving Best Time to Buy and Sell Stock Problem
This is a pretty classic algorithm question that you might encounter on any interview. Let’s take a look into the context of this problem.
Let’s say you have a list of stock prices [7, 1, 3, 5, 14, 12]. You have to decide when to buy stocks and and when to sell them.
There are two ways to go about solving this. One is to find all the possible buying prices and selling prices and find out the maximum selling price:
This works but it is O(N²) in performance. Let’s take a look at an alternative solution:
Here, we grab the minimum pricein the beginning. For each iteration, we check our current profit. If that is greater than the profit we have currently, we replace it. Likewise, as we iterate through the list of prices if there is a price that is lower than our current lowest price, we replace it.
This also works but it is O(N) performance, which is more optimal than the other solution we suggested.
