121. Best Time To Buy And Sell Stock

Problem Statement in English

You’re given an integer array prices, where prices[i] is the price of a given stock on the $i^{th}$ day.

Your task is to find the maximum profit you can achieve from buying one stock on day i and selling it on day j, such that $i < j$.

Approach

We iterate over the array, keeping track of the minimum price we have seen so far. We also keep track of the maximum profit we can achieve, by selling the stock at the current price.

At the end of the iteration, we return the maximum profit that we’ve calculated up until that point.

Solution in Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # some really large number
        bought = float("inf")

        # profit
        profit = 0

        for price in prices:
            # ensure `bought` is the minimum
            bought = min(bought, price)
            # ensure `profit` is the maximum
            profit = max(profit, price - bought)

        return profit

Complexity

• Time: $O(n)$
  Since we iterate over $n$ elements at most.

• Space: $O(1)$
  Since we only store a few integer variables.

And we are done.