What is the time complexity of this code for Best Time to Buy and Sell Stock

Question

I am a beginner in coding, I was doing a leetcode problem "121. Best Time to Buy and Sell Stock". I wrote a code that works pretty well but when I try to run it, it says Time Limit Exceeded. Looking at this code, this would be O(n) time complexity and for the space complexity it would be O(1). I have seen other solutions using a while loop (kadane's algorithm) and it runs perfectly.

l = 0
r = 1
maxx = 0
if len(prices) <= 1:
    return 0
while l <= r:
    profit = prices[r] - prices[l]
    if r != len(prices) - 1:
        r += 1
    elif l == len(prices) - 2:
        if maxx < profit:
            maxx = profit
        break
    else:
        l += 1
        r = l + 1

    if maxx < profit:
        maxx = profit

return maxx

Answer 1

Some observations:

• Either l is updated and r is set to one more, or l is not updated and r does not diminish. This means that the while condition is always satisfied. The only way to exit the loop is via the break. This means the loop header could also have been written as while True:

• The r index visits the same index multiple times, as r = l + 1 generally decreases its value The algorithm produces all possible pairs of [l, r] where l < r. There are n(n-1)/2 of those pairs, so the algorithm has a complexity of O(n²).

This complexity is not optimal -- as you know. We can get a "feel" of that inefficiency by realising the following: when we have found the optimal r for a given l, it makes no sense to look at lesser values of r when l has been increased. Surely that optimal r for that previous l is still going to be the optimal one for the next value of l. Only when that optimum was at l + 1 we need a "fresh" one. So your algorithm is wasting time on values of r that we already know cannot be optimal.

Similarly, when the price at l is greater than a previous one, there is no way that the optimal r (for that l) will improve the best profit we already had. So then there should be no reason at all to have r iterate over the rest of the array: it will be fruitless.

Optimal algorithm

You have already mentioned Kadane's algorithm (based on day-to-day price differences)

I find the following one-pass algorithm quite intuitive:

When at a certain index during that single pass, let's assume you have correctly identified the following, using only the part of the list that was already processed:

1. The best profit in that list. If this sub list would be all there was, this would be the final answer.

2. The minimum price in that list. This is a good candidate to buy and try to make even better profits when going further.

Then, when reading the next price from the list, there are the following cases:

• Maybe that price is high enough to improve on the best profit (considering a buy at the minimum price we had so far, and selling at this current price): if so, we just have to update that best profit.

• Maybe that price is lower than the minimum price we opted for. In that case we can forget about the previous minimum we had, since any future improvement we could get by using that previous minimum price would immediately be improved by taking the current price as buying price instead, so we don't need the previous minimum price anymore.

• In all other cases we have a price that is non interesting, nor as buying price, nor as selling price.

After this step we are again sure we have determined the best profit for the range of prices that was processed, knowing also the minimum price in that range.

So by induction this process will give the correct answer.

Code:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        maxprofit = 0
        minprice = prices[0]
        for price in prices:
            if price < minprice:
                minprice = price
            elif price - minprice > maxprofit:
                maxprofit = price - minprice  # buy at minprice & sell at price
                
        return maxprofit