Repeat Code With LeetCode — Best Time To Buy And Sell Stock

I think this is pretty involved for a LeetCode easy, but no one asked me for my opinion

Photo by Maxim Hopman on Unsplash. lmao is this going up or down

Credit where credit is due — a lot of this is taken from the NeetCode solution, a YouTube video that I think provided a much better explanation than its Nick White counterpart. Unlike Nick White, NeetCode explains why his algorithm works.

You may be familiar with the 14 LeetCode Patterns, which are explained here in this Educative advertisement. One of them is called the Two Pointer Technique, which is extremely useful in interviews (I have seen it come up in numerous real interviews) in spite of its non-descriptive name.

The Sliding Window Coding Pattern is a bit like the Two Pointer Technique’s cousin. You still have two pointers, yes, but you apply them in a specific way. Its name is apt and descriptive: You solve a LeetCode question by creating a window. Maybe the size is fixed, or maybe it can expand/contract.

Source: https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed

An example for this is minimum size subarray sum. You obtain an array of numbers. You obtain a window, starting from the left, and “slide right” until some specific condition is met. You keep track of the window that obtains this condition, but now you can “slide left” and contract as long as this condition is still met. You keep a running list and size of potential candidates. The condition itself can vary: Maybe the window needs to be of a certain sum, or maybe the window needs to have a certain number of characters (in some variations that are for characters instead of numbers).

“Best Time To Buy And Sell Stock” can be thought of a bit like a MODIFIED sliding window technique problem. If you have solved sliding window problems before, you may notice similarities like starting from the left, expanding right, and keeping a running tally of all potential maximums.

NeetCode identifies one critical difference in his video: Your condition is that the window needs to have a positive value (ie a window in which you “make money,” as in you buy low and sell high), and if at any point it does not then you move the left pointer all the way to the right pointer. The reason for this is that any value causing you to get a negative return is a potential “valley” worth treating as a new starting point.

This is their first example

[7,1,5,3,6,4]

We are human. We can see that the best thing to do is buy at value=1 and sell at value=6 for a return of 5. We can easily solve this with nested for loops, which LeetCode will respond to by calling us fools. How dare we have the audacity to think that a LeetCode easy question will have such an easy solution.

NeetCode’s algorithm is more efficient.

1. Create a window starting from leftPointer=0 to rightPointer = 1
2. Continue to move your right pointer right (slide the window right), and keep a running tally if you ever obtain a “gain”
3. If at any point you obtain a negative gain, start a new window. You now have a new candidate for maximum

This is a clever solution because, within the constraints of the problem, it accounts for every possibility. Every dip is considered, and it guarantees that it will return the largest gain at the end. It does not require O(n²) time complexity, and it also accounts for if there is no gain (it will just return 0).

The Problem

Best Time To Buy And Sell Stock

Difficulty: Easy

Skills required: Sliding window technique (depending on implementation)

Description:

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

The Solution

The while loop above simply ensures that the rightPointer does not go out of bounds. Slide right at every step, but if at any point you get a negative overall profit then update the left pointer all the way up to the right pointer. This is the “break” from a typical sliding window pattern problem.

Things that make this characteristic of a sliding window problem:

• Left pointer and right pointer, starting at the left
• Keeping a running tally of the maximum

Things that are unique:

• That you update the left pointer to the current right pointer position, which is more akin to a “pivot” than the sliding window metaphor

Further Discussion

There are other solutions, including Kadane’s Algorithm. That may be the reason it is so popular and well-known. This problem is in Blind75, and I saw it once (and immediately failed) during a coding test many years ago.

I am still not sure if I think it is the best measure of coding ability. One user pointed out that you can only actually implement this algorithm in this scenario if you also have a time machine.

Closing Thoughts