Back to questions

You are given a list of stock , where the stock's price on the $i^{th}$ day is stored as the $i^{th}$ element of the prices list.

You want to maximize your profit trading the stock, but are only allowed to buy the stock once and sell it once on a future day.

Write a function called which takes in this list of stock prices, and computes the max profit possible. Return if you can't make any profit.

Input: prices = [9, 1, 3, 6, 4, 8, 3, 5, 5] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 6 (price = 8), $profit = 8 - 1 = 7$.

Note that buying on day 2 and selling on day 1 is not allowed because you have to buy the stock BEFORE you can sell it (unless your a time-traveller in which case just trade bitcoin).

Input: prices = [6, 4, 3, 3, 2] Output: 0 Explanation: In this case, no trades should be made since the stock is tanking like a brick. The max profit here is 0.

Let's start with the brute-force solution, where we generate every possible pair of days to buy and sell. This code should look similar to the brute-force solutions of two sum interview question and the contains duplicate questions.

Here's that code:

The time complexity is $O(n{2})$ because we run through all pairs of n elements. The space complexity is constant $O(1)$ because we only use two varaibles max_profit and cur_profit.

Here's a more efficient, clever solution, that relies on a fundamental insight: for any given day X, if you **had to sell the stock on that date X**, the potential profit for that specific day occurs if you were to buy the stock on any day preceding X where the price of the stock was the lowest.

Mathematically said, $PotentiallProfit_{DayX} = price[X] - min(price[1], price[2], .....price[X-1])$

So essentially, we'll loop through the list, and keep track of the minimum stock price seen so far in a variable called .

Every day, we'll compare the current stock price, to the minimum stock price seen so far, and record that as the potential profit for that specific day.

We'll also track a second variable – the . At the end, we'll return . Here's that code:

The time complexity is $O(n)$ because only a single pass through the prices list is needed. The space used is constant ($O(n)$) because only two variables are used.

Python