Best Time to Buy and Sell Stock | Typescript Solution

In this post I am going to share how I solved the leetcode problem called Best Time To Buy and Sell Stock. Although this problem is marked as easy but if you do not understand how the sliding window works than it may seems a little bit tough.

What is Sliding Window

Let’s say you have an array or a list and your task is to find a suitable sub section of that array that satisfies a specific condition. For example, we can think that we have an array [1,2,3,4,5,6,7]. We need to find a subset (a portion of an array) where the addition of all the item is 7. In this scenario, let’s say the subset should contain only 2 items. Whenever we say a subset, most of the times it means those values should be together, side by side. That’s how I determine if I can solve a problem using Sliding window. You can take any two of them that are side by side and check if there sum is 7 or not. Here is a representation below for better understanding.

In here we follow this steps:

Take index 0 and 1, Is there sum equals 7?
If no, take index 1 and 2 and check again
if no, take index 2 and 3 and check again,

We continue to do it until we reach the end of the array or whenever we the condition is satisfied

Ok got it. Now how can we solve the best time to buy and sell stock problem?

Now, In our case, we are supposed to do the same thing to solve this problem. We need to find out a sub array where the max amount of profit can be made. Or in other words, find a sub set of array elements that produces the highest number of value but adding them together.

So we at first set the left index as 0 and the right index as 1. We also assume that the max is 0. The left index is yesterday and the right index is today. Notice that we can not go to the previous day in stock price calculation. So whenever we see that the price of today is lower than whatever value we have in the left index, it means we are making a loss. If we are making a loss that we do not need to check any further. We point the left index value to the right index and start continuing from there again. And we continue to increase the window size. But if we see that we are making profit, we check if it the the max so far or not and store it based on that result.

Once we go through all the value we will have the max profit we can have. I have added a nice little animation to show how it works in action.