This will be a series of problems, getting more and more difficult.
Problem 1: Infinite buying/selling
Let’s say you have a list of stock prices, which reflect the price of the stock on a given day:
What’s the maximum profit you can get from buying/selling stocks, completing as many transactions as you like (i.e., buy one and sell one share of the stock multiple times)?
Answer: 9 (1 -> 5, 3 -> 8)
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
For me, the way I thought about this was that every long-term transaction can be broken into smaller transactions. Buying on day 4 and selling on day 6 is equivalent to buying on day 4 and selling on day 5, then buying on day 5 and selling on day 6. What determines whether you should buy on a given day? If the next day is greater!
So, now we get our very simple solution: We loop through every day, and we buy whenever the next day is greater than the current day.
def maxProfit(array): total = 0 for i in range(len(array) - 1): if array[i] < array[i + 1]: total += array[i-1] - array[i] return total
Problem 2: Buy/sell once
This is exactly the same problem, except you are only allowed to make one transaction the whole time.
If you’re asked this in an interview, the safest thing to do is to think of a brute force solution.
O(n^2): Brute Force
The most basic solution is to try out every possible combination of buying and selling, and keep track of the best result.
E.g.: [7,1,5,3,6,8,4] → 5
There are n*(n-1)/2 total operations, or O(n) time.
O(n log n): Sorting
There is no way to sort here, because the order of the prices matters.
O(n): Single Pass
Based on the logic above, we’re not gonna see an interview problem with a brute force solution as the ideal solution (usually). So, you can deduce that this is the complexity of the ideal solution.
Because it’s a single pass, we can try selling at every location, and finding the maximum of that. The question is when would you buy it if you sell a stock today? You would buy it at the minimum up until that point. So, that’s all you have to do:
At every point, keep track of the minimum, and calculate current price - minimum. Take the maximum out of all of those.
def maxProfit(array): if len(array) < 2: return 0 minimum, best = array, 0 for i in array[1:]: if i < minimum: minimum = i elif i - minimum > best: best = i - minimum return total
Problem 3: Infinite buy/sell with cooldown
In this problem, you can buy/sell stocks as many times as you want. However, after you sell your stock, you cannot buy stock on next day.
On any given day, you have two options: you can either buy or sell stock. Both of them come with preconditions. First, in order to sell, the last transaction you’ve made was a sale. In order to buy, the last transaction you’ve made was a sale 2 days ago (or it’s your first time buying).
On every day, you have two numbers to keep track of. The highest amount you could’ve made if your last transaction was a sale, call it sell[i], and the highest amount you could’ve made if your last transaction was a buy, call it buy[i].
buy[i] = max(buy[i-1], sell[i-2] - prices[i])
Your last action was either already a buy, in which case you can’t buy again (buy[i-1]), or your last action was a sale two days ago, and you’re buying again today.
sell[i] = max(sell[i-1], buy[i-1] + prices[i])
Your last action was either already a sale (sell[i-1]), or your last action was buying, and you’re selling today.
That’s it! All we have to do now is pick a starting condition. buy[i] means your last transaction was a buy, so on the first day, buy means we bought the stock, which means buy = -1 * prices. Likewise, sell = 0, because we’re selling nothing.
def maxProfit(prices): buy = [0 for i in prices] sell = [0 for i in prices] buy = -1 * prices for i in range(1, len(prices)): if i < 2: buy[i] = max(buy[i-1], prices[i]) else: buy[i] = max(buy[i-1], sell[i-2] + prices[i]) sell[i] = max(sell[i-1], buy[i-1] + prices[i]) return sell[-1] #We're not gonna end on a purchase!
Timewise, this is an amazing solution. It’s O(n) with one pass through the array. However, space-wise, it's inefficient. You don’t need to save your buy/sell information from 5 days ago! All you need is buy[i-1], sell[i-1], and sell[i-2]. Let’s rename these:
We can just refer to buy[i-1] as buy. After all, it’s just whatever information was previously stored in buy.
We can refer to sell[i-1] as sell.
We can refer to sell[i-2] as rest.
Now, let’s rewrite this code:
It’s important to note that doing something like a,b,c = 1,2,3 means that they happen simultaneously, so you don’t have to worry about the order you write the expressions in.
def maxProfit(prices): buy, sell, rest = -1 * prices,0,0 for price in prices[1:]: buy,sell,rest = max(buy, rest - price),\ max(sell, buy + price), sell return sell
Problem 4: Infinite buy/sell with a transaction fee
This is extremely similar to the previous problem. You have to keep track of two things: the maximum amount you can make if your last action was a buy, and the maximum amount you can make if your last action was a sale.
buy[i] = max(buy[i-1], sell[i-1] - prices[i])
This is exactly the same as before, except we don’t care about the cool-down period.
sell[i] = max(sell[i-1], buy[i-1] + prices[i] - fee)
Either you sold your stock earlier or you sell it today and pay a fee.
Right off the bat, we know we can simplify it. We only need to keep track of two variables: sell[i-1] and buy[i-1]. We know our initial conditions: buy = -1 * prices, and sell = 0
def maxProfit(prices, fee): buy, sell = -1 * prices, 0 for price in prices[1:]: buy, sell = max(buy, sell - price),\ max(sell, buy + price - fee) return sell # We don't want to end on a purchase