Max Profit Trading Stocks [Google Python Interview Question]

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.

Example 1:

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).

Example 2:

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:

Brute-Force Solution Complexity:

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.

Clever Solution

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:

Clever Solution Complexity:

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.