121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximise your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

Let $(i, j)$ represent buying on day $i$ and selling on day $j$, and $p_i$ be the price on day $i$. The brute force solution requires us to check every pair $(i, j)$ and calculate the maximum profit from that. We can reduce the solution space, however, if we consider a few insights:

• We must buy before we sell, so for any day $i$ we buy on, we only need to check days $j > i$ for the price.
• If $(i, j)$ results in a loss, then buying on $j$ and selling on subsequent days results in higher profit than buying on $i$ and selling on subsequent days.
  • Since buying and selling on $(i, j)$ results in a loss, $p_j$ must be smaller than $p_i$. Then for any subsequent $k > j$, we have $p_k - p_i < p_k - p_j$, so all resulting trades $(j, k)$ will have greater profit than $(i, k)$.

We can thus start our search from the indices $(0, 1)$—buy on the first day, and sell on the next. If there is a profit, then we can check selling on the subsequent day, $(0, 2)$, and so on.

• Notice we don’t need to check $(1, 2)$—since $(0, 1)$ results in a profit, day 1 has higher stock price than day 0, so buying on day 1 and selling on day 2 would have lower profit than buying on day 0! If we ever reach a day $(0, j)$ that results in a loss, then we stop checking $(0, k)$ for $k > j$, since $(j, k)$ will always outperform $(0, k)$ anyways. At this point, we always start to buy on $j$, and we check the subsequent trades from that point onwards.

In general, if $(0, j)$ results in a loss, why don’t we need to check $(i, k)$ for some $0 < i < j < k$ and can move straight to checking $(j, k)$? Since the algorithm has moved the selling day past $i$ to $k$, that means that $(0, i)$ has resulted in a profit—in other words, $p_{i} \geq p_0$. Since $(0, j)$ is a loss, we have $p_i \geq p_0 > p_j$. Thus, $p_k - p_{i} \leq p_k - p_0 < p_k - p_j$, so $(i, k)$ always underperforms compared to $(j, k)$.

• This is the key loop invariant that is maintained. For any iteration j in the loop, the profit at $(j, k)$ for any $j < k$ is bigger than $(i, k)$ for any $i < j$.

def maxProfit(self, prices: List[int]) -> int:
	buy = 0
	max_profit = 0
	
	for sell in range(1, len(prices)):
		profit = prices[sell] - prices[buy]
		if profit < 0:
			# (sell, k) always outperforms (buy, k) for subsequent k
			buy = sell
		else:
			# update max_profit if needed; otherwise, keep checking 
			max_profit = max(max_profit, profit)
	
	return max_profit

Another way to think about this is that we always buy at the lowest price we have seen. Notice that checking if profit < 0 is the same thing as checking if prices[sell] < prices[buy]. If so, we update buy = sell. And since buying at the lowest price will outperform buying at any other price seen before, we won’t miss any bigger trades.

Time Complexity

Notice the while loop is dependant on the value of sell, and not buy, and that sell always increments by 1 at every iteration. Therefore, a maximum of $n$ iterations are performed, so the algorithm has a worst case runtime in $\mathcal{O}(n)$.

Space Complexity

We don’t store any complex structures—the only variables declared are constant integers, so the space complexity is constant—$\mathcal{O}(1)$.