Solving Popular Algorithms: Best Time To Buy and Sell Stocks

One thing that I’ve found to be super helpful in my technical interview prep is solving Leet Code problems and today, I’m going to walk you through a solution to a leet code problem that I struggled with during my first attempt: Best Time To Buy and Sell Stocks.

Not a good time to sell, but maybe a great time to buy?

The Problem

The goal for this problem is to determine the maximum amount of profit you can make on a stock where the stock prices for each day are given to you in an array.

A couple quick things to note about this problem, is that first you are only able to complete at most one transaction (aka you can buy and sell one share of the stock)Note that you cannot sell a stock before you buy one. Second, and this may be obvious, but you can not sell a stock before you buy one.

So, here’s an array for an example:

let stockPrices = [7,1,5,3,6,4]

Now, based on that array, the cheapest day to buy would be day 2 (i.e. index 1, remember arrays start with index 0!) where our stock price is 1. Then, the best time to sell our stock would be (remember we have buy before we can sell!) day 5 (i.e. index 4) when the stock price is at 6. Thus, our solution/our maximum profit from this specific stock would be 5.

Hopefully, that all makes sense and let’s get into solving this problem!

The Solution: My First Thoughts

The way I first attempted to solve this problem was to find the minimum number in the array, then, starting at the index of the minimum number, find the largest value. Then, you could subtract the minimum from the largest and voilà we would have the maximum profit we could make from this stock!

While this solution will allow us to pass the test case above, do you think it will work for all cases?

Let’s see if it will work for this array:

let prices = [7,3,6,1,2]

If we were to follow the steps of the above solution to this problem, we would first find the minimum value, in this case it would be 1. Then, we find the largest subsequent value, in this case 2. Then, we would subtract 2–1 and get a maximum profit of 1…which is incorrect.

As you may have already noted, the real maximum profit we could get from this stock is 3 (if we bought on day 2 at a price of 3 and sold on day 3 at a price of 6).

So, unfortunately this solution doesn’t work. Let’s try a different approach!

The Solution: Round Two

For this solution, we are going to iterate through the array twice over in order to find all of the potential profits in the array. Then, we will compare whatever our current profit is to the largest profit we’ve found thus far in the array. If the current profit is larger than the largest profit we’ve found so far, we will set the largest profit found equal to the current profit. Then, ultimately, we will return the largest profit.

Hopefully, our pseudo code description makes sense, however I find it often a lot easier to see things written out in actual code, so here we go!

First, we are going to start by declaring two variables:

let largestProfit = 0
let currentProfit = 0

Now, we are going to do our first and second iterations through the array and make the comparison to find the maximum profit in our stocks array:

for (let i = 0; i < arr.length; i++) {
   for (let j = i+1; j < arr.length; j++) {
      currentProfit = arr[j] - arr[i]
      if (currentProfit > largestProfit) {
         largestProfit = currentProfit
      }
   }
}

Then, if we put it all together:

maxProfit = (arr) => {
   let largestProfit = 0
   let currentProfit = 0
   for (let i = 0; i < arr.length; i++) {
      for (let j = i+1; j < arr.length; j++) {
         currentProfit = arr[j] - arr[i]
         if (currentProfit > largestProfit) {
            largestProfit = currentProfit
         }
      }
   }
   return largestProfit
}

There you have it: a simple solution to the Best Time to Buy and Sell Stocks Problem.

Before we go, do you see any major flaws with this solution? It does pass all of our leet code test cases (which is great!) but is there anything wrong with it?

Yes, okay, so this solution does have a quadratic runtime of O(n²). Obviously, ideally we love all of our algorithms to run atO(n) or O(1) runtimes.While getting all of the test cases to pass is an achievement, what’s even better is coming up with the fastest or best solution to every problem. So, if you’re feeling up to it try to see if you can figure out a solution that runs at a faster runtime!

Good luck and happy coding!

Lol stonks