Best Time to Buy and Sell Stock

The problem description can be found in LeetCode.

Approach

As usual, we could apply a brute force approach. We could start from the first price and consider it as a buy price and then look for a higher price in the range [1, n - 1] to make a profit (n is the size of the prices list). Then, we could start from the second price and loop for values in the range [2, n - 1]. We could go on until the end of the prices list and store the maximum profit we can obtain.

This approach would require $O(n^2)$ time because of this double looping.

However, this is not really necessary. In fact, let's look at this example:

prices = [1, 2, 3, 4, 5, 6]

For an ordered list, the maximum profit we can achieve is between the minimum and the maximum values. So, for an increasing sequence, we need to consider the first value, which is the minimum of the sequence itself, as our buy price.

Now, let's look at the example of the question description:

prices = [7, 1, 5, 3, 6, 4]

We can easily understand that it makes no sense to consider the 7, since we will surely get a higher profit with its next element 1. In fact, if there is a higher price later in the list, we would get the best profit with 1 and not with 7.

So, we could point a first index to the minimum element we encountered so far and increment the second pointer by one at each iteration. Meanwhile, we also calculate the best profit so far by using these two pointers.

Solution

from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        buy_price = prices[0] if len(prices) > 0 else 0

        for price in prices[1:]:
            if buy_price > price:
                buy_price = price
            else:
                ans = max(ans, price - buy_price)

        return ans

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the size of the prices list.