Best Time to Buy and Sell Stock II

Photo by Markus Spiske on Unsplash

Here’s another algorithm style coding challenge that I worked on LeetCode. The problem is rated as easy, and I would agree with that rating. Of course, the easy problems are great for aligning the logical thinking muscles necessary for efficient coding, and I find that the solutions to those problems are often more useful in real-world situations.

In this exercise, we begin with an array of prices. These values correspond to the prices of an unnamed stock over a consecutive number of days. For example, the array[7,1,5,3,6,4] represents the stock price over six days. The price on the first day is 7, the price on the second day is 1, and so on.

Our goal is to create an algorithm that finds maximum profit by buying and selling the stock on appropriate days. We’re only allowed to engage in one transaction at a time, so once we buy we cant buy again until we sell.

In the previous example, we would buy on day 2 and sell on day 3 for a profit of 4, then buy on day 3 and sell on day 4 for a profit of 3. The total profit from the two transactions would be 4 + 3, or 7.

I decided that the best way to calculate the maximum profit was by buying just before the price rises and selling just before the price drops. Isn’t that what every day trader wants to do! If only we all had an array telling us what the price of our favorite stock would be over the next few days.

So my first working submission looked like this:

var maxProfit = function(prices) {
    // buy before price rises, sell before price drops
    let buy = -1
    let sell = 0
    let profit = 0
    prices.forEach((price,i)=>{
        if ((price < prices[i+1]) && buy === -1 ) {
           buy = price 
        } else if (((price > prices[i+1]) || (i === prices.length-1)) && buy !== -1 ) {
            sell = price
            profit += sell - buy
            buy = -1
            sell=0
        }
       
    })
    return profit
};

Fantastic! By saving the buy price before an increase, and adding the transaction profit to the total before a price decrease, this algorithm achieves the desired result.

But there’s a better way.

It turns out that my algorithm is performing a few unnecessary steps. I don’t have to store the buy price and make multiple comparisons. Instead, I can add the change in price from one step to the next to the profit total as long as the price is increasing. That algorithm looks like this:

var maxProfit = function(prices) {
    // add price delta to profit if price is increasing
    let profit = 0
    for (let i=0; i < prices.length;i++){
      if (prices[i] > prices[i-1] ) {
          profit += prices[i] - prices[i-1]
        } 
    }
    return profit
};

We were able to achieve the same result with fewer lines of execution by eliminating unnecessary steps. This was achieved by changing the process to look at the previous step instead of looking at the future step.

This almanac made Biff rich!

Of course, we can’t actually use this algorithm to get rich, because in real life we don’t actually know if the price in the future will rise or drop. Until the day we can see into the future, or we’re handed a book containing future stock prices by a time-traveling bully, we’ll just keep working on our coding skills.

Happy coding!