Best Time to Buy and Sell Stock (LeetCode #122)

Image by Maxim Hopman on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Maximum Product Subarray.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Best Time to Buy and Sell Stock problem, welcome. 🔥

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a great way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

With that said, let’s get right into it so you can get your solution.

Initial Setup 🏗

Before we write a single line of code, we should try to understand all the rules for the challenge (see: Polya’s Problem Solving Techniques):

1. We’ll be given a list of prices where each price is the cost of a stock on the i day
2. We want to maximize our profits by choosing a single day to buy the stock and a single day to sell it
3. The day we sell the stock must be after the day we buy it
4. We must return the maximum profit possible
5. If no profit is possible, we should return 0

This is enough for us to get started. 🔥

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

I also won’t be talking through “less optimal” solutions. You came here for an answer, right? I’m going to make sure you get a good one.

Let’s get to it.

Building Our Variables

The first thing we need to do is write some variables to track the max_profit and the lowest_price_seen. We can write them inside the function like this:

We can initialize the max_profit variable to 0 since keeping that as the default (if it’s never updated) will be returned. Remember how the ruleset said to return 0 if no profit was possible?

We have that part covered now. ✅

Also, initializing lowest_price_seen to the first price in the prices list gives us a starting point to compare everything else to. We’ll just need to make sure to start our loop at index 1 to compensate.

Building Our Loop 🔁

The next thing we need to do is write a for loop that iterates over our prices and does some comparisons to check if (for each new price) we can get a better max_profit with it or also if it’s lower than our current lowest_price_seen.

This is what it looks like in code form:

This looks fancy, but it’s really straightforward.

All we’re doing here is starting at index 1 (like we talked about in the section above), pulling out each new price by the index, assigning max_profit to be whichever is the maximum between its current value or the new price — lowest_price_seen, and then also updating lowest_price_seen afterwards (for future iterations) to be whichever is the minimum between lowest_price_seen or price.

Finally, we return max_profit after our loop is done running just like we talked about. If no profits were available while the loop runs, this will still be 0 from the value we initialized it with.

This algorithm runs in O(n) time complexity (running once through our for loop) with O(1) space complexity (since we just have a couple of variables) and gives us the answer we need!

Conclusion

There you go. 👏🏻

I hope you learned something as much as I enjoyed writing this article for you.

Keep an eye out for the rest of these Blind 75 coding challenges articles from me. I’m going to be solving them and publishing these as I go.

Also, feel free to reach out to me on any of the links below if you want to talk about coding, cool tech, or anything else (I really, really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)