Best Time to Buy and Sell Stock
Short Summary
We are given an array of daily prices for a stock. We would like to know the maximum profit we can make if we had one buy and one sell operation.
I/O Example
// inputArr := []int{7, 1, 5, 3, 6, 4}
// output := myFunction(inputArr, windowSize)
// output = 5 (buy at price 1$ on day2 sell at price 6$ on day5)Explanation and Walk-through
Simple approach
Input for the algorithm consists of daily price information for a stock. We are expected to pick a day to buy, and another day to sell in order to get the maximum profit from this transaction. Naturally, we must sell after we buy. If there's no option for a profit (e.g. prices are in descending order) then we must return zero.
The basic approach would checking all possible options. For every day, assume we bought on that day and calculate the potential profits if we sell on any of the upcoming days. Then get the maximum profit and return it if it's positive. This would essentially mean that we must do N-i-1 calculations for each of N days. Thus we will have a time complexity of O(N^2). Brute force approach basically goes through all the combinations of buy and sell and returns the best result. But it takes O(N^2) time so for a large enough input, it could take a significantly long time to come up with a result. Let's check how this looks in code.
func maxProfitBrute(prices []int) int {
maxProfit := 0
for i := 0; i < len(prices); i++ {
for j := i + 1; j < len(prices); j++ {
currentProfit := prices[j] - prices[i]
if currentProfit > maxProfit {
maxProfit = currentProfit
}
}
}
return maxProfit
}Increasing efficiency
Let's see how we can improve and avoid some of the unnecessary calculations. In the brute force approach, we are essentially considering to buy on each day once, and then considering to sell on each day many times. If we could come up with a way to consider each day's price less often, that would be an improvement. To be able to reduce the number of comparisons we make, we need more information whenever we encounter a new price.
What kind of an information we need? We need to be able to detect if the current day's price is a good place to buy or sell given the previous prices we have seen. If we kept track of the price differences for every day (the difference between the current price and the previous price) we can essentially calculate the total profit or loss for every day (given we know the starting point). This is because given prices P1,P2,P3...PN. PN is actually the same as P1 +(P2 - P1) + (P3 - P2) + ... (PN - PN-1). So with this transformation of the input data, we can now quickly calculate the total profit / loss between any two days by simply summing up every difference in between. This is allow us to be able to keep track of how well we are doing without jumping back and forth between prices. So the algorithm becomes:
Calculate the price differences for each day with the previous day (starting from day2). Start walking through the new data and keep track of the currentProfit while just summing up each data point as we encounter them. At each step, check if the current price difference is adding to our profit, meaning it's a positive number. If it's positive number, add to the currentProfit and udpate maxProfit if necessary. If it's a negative number (which means price has dropped since yesterday) check if it still makes sense to keep the day in the currentProfit window. Meaning check if after including current day's price difference, we are still at a profit or not. If we're still at a profit, we can weather this low price day and continue. If with the current days price drop, our currentProfit so far becomes negative (we have a drop more than the total currentProfit) then it's time to drop the previous currentProfit window and start a new one since this is such a huge drop in price, it makes more sense to buy now.
With this algorithm we will be able to just calculate the max profit with only doing two passes over the original input. One to calculate the price differences, and a second one to calculate the maximum profit possible for the input.
We can even improve on this solution by dynamically keeping track of the prices differences so we can avoid the initial data transformation. We will now code both of those solutions to clarify.
func maxProfitDoublePass(prices []int) int {
// create price difference array from input
// pass1
priceChanges := make([]int, len(prices)-1)
for i := range prices{
if i == 0{
continue
}
priceChanges[i-1]= prices[i]-prices[i-1]
}
// set maxProfit to zero
// if current is positive
// add it to currentProfit
// if it's negative
// check if it's absoulte value is more than currentProfit
// if so start new window, because it's buytime (from the next item)
// if not add it to currentProfit and continue
var currentProfit int
var maxProfit int
// pass2
for _, diff := range priceChanges {
if diff >= 0 {
currentProfit += diff
maxProfit = maxOfTwo(currentProfit, maxProfit)
} else {
if diff+currentProfit <= 0 {
currentProfit = 0
} else {
currentProfit += diff
}
}
}
return maxOfTwo(maxProfit, currentProfit)
}Now let's see how we can eliminate the initial price difference calculation pass.
func maxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
// set maxProfit to zero
// if current price diff is positive
// add it to currentProfit
// if it's negative
// check if it's more negative than currentProfit
// if so start new window (from the next item)
// if not add it to currentProfit and continue
var currentProfit int
var maxProfit int
// start from day2 and calculate diff with the previous day
for i := 1; i < len(prices); i++ {
diff := prices[i] - prices[i-1]
if diff >= 0 {
currentProfit += diff
maxProfit = maxOfTwo(currentProfit, maxProfit)
} else {
if diff+currentProfit <= 0 {
currentProfit = 0
} else {
currentProfit += diff
}
}
}
return maxOfTwo(maxProfit, currentProfit)
}Extra comments
The function maxOfTwo returns the bigger integer of the two arguments.
You can try it yourself on leetcode
Please comment or dm me if you have other questions or remarks.
Until next time,
Stay all in!
Reha S.
Oct 19 2022