Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python 

🚀 neetcode.io/ - A better way to prepare for Coding Interviews

Bro, I just found your channel as I’m preparing for interviews and I cannot say how much your videos are helping me. Thanks for taking the time to do all of them. Truly.

I always get so close to solving these problems. I have the right idea, but my implementation is never quite there. It is frustrating, but your videos help improve my thinking. Thank you!

Best interview prep channel I've found. Really appreciate how succinct you are in explaining things, while also still covering the necessary concepts.

Q - Is it just me or are we missing something here? Yes you can move your left pointer all the way to the right but that assumes that later in your array you will have > left pointer or you have have a delta between your left and right pointer greater than any delta which may have existed previously, however, just because you've reached a new all time low doesn't mean that there is a differential greater later in the array. Just my thoughts. Ans - No , actually i thought the same but the code returns maxprofit not final l and r let l=[2,8,1,3] final l and r is 1,3 the profit is 2 (but will not be returned) then it is compared with maxprofit which is 8-2=6 , since it is less maxprofit is not updated output will be 6

Alternate view :: for(int i = 1; i < n; i++), if we want to sell at i'th position. what we want is to buy at minimum value from previous i - 1. keep a minimum till here.

The other way without the sliding window technique is : 1. Iterate through the prices array. 2. In each iteration keep track of the minimum element seen so far and check for the maximum difference between the currentElement and the minimum element find so far. For the input from the first Example [7, 1, 5, 3, 6, 4]. The found minimum will be 1 at index 1 and the biggest difference found will be when you are at index 4 with value 6 this will give you the answer 6 - 1 = 5. This solution is intuitive and easy to implement: Here is an implementation in a Java code. class Solution { public int maxProfit(int[] prices) { int result = 0, minNum = Integer.MAX_VALUE; for (int i = 0; i < prices.length; i++) { minNum = Math.min(minNum, prices[i]); result = Math.max(result, prices[i] - minNum); } return result; } } Btw later try "Best Time to Buy and Sell Stock II" you can go Greedy there again without sliding window technique.

class Solution: def maxProfit(self, prices: List[int]) -> int: l,r = 0,1 maxp = 0 while(r < len(prices)): if prices[l] < prices[r]: profit =prices[r] - prices[l] maxp= max(maxp,profit) else: l = r r = r + 1 return maxp it should be l =r

This dude solved the problem in O(n) time with two pointer approach and everyone in the leetcode discussion section were complaining that this problem is supposed to medium level, we've to use dp , bad test cases etc etc

Going through your roadmap right now, I must say, going through each problem with you its so much fun, in fact I don't have time to prepare my resume, portfolio, project etc...omg its like a drug. I keep telling myself I need to start working on other things, but every morning i ended up on your roadmap, working on the next question, oh god I need help.

Is this sliding window or two pointers? I thought for sliding window there needs to be a window size? not sure what the difference between the two is now. Would appreciate an explanation :)

*AAAAH* this is *SO MUCH CLEARER* than the dang solution tab for this problem on LC! THANK YOU.

Is it just me or are we missing something here? Yes you can move your left pointer all the way to the right but that assumes that later in your array you will have > left pointer or you have have a delta between your left and right pointer greater than any delta which may have existed previously, however, just because you've reached a new all time low doesn't mean that there is a differential greater later in the array. Just my thoughts.

If anyone's confused, I thought of this as: We're trying to find maxima and minima across the list. For this, we can only make one comparison: if right (high) is greater than left (low)? Yes? Calculate the profit. Right (high) is smaller than left (low)? That means it's even smaller than what we thought was the minimum, thus it is the new minimum. We have already calculated what the profit was for the elements between these two. So we freely make l = r. We then increase the right pointer in either of the cases and traverse

In the while loop shouldn't we also include one more condition l

I think the case where the new lowest low occurs that is not followed by a higher high or a lower high with greater distance than the previous max.

i did this in a very different way in O(n) time and O(1) space. By iterating through the array from right and storing the max value seen so far in a variable. and then updating the ans variable with the maximum profit that can be made.

This solution is so much more intuitive and easy to understand the kadane algorithim solution lc provided. Love to see it!

I made the same error in my code, was freaking out that I couldn't solve an "easy" but your explanation for the bug helped! Thank you :)

Was having that same doubt regarding the bug you found at the end of the video. Glad to have it cleared up.

Another way to think about it (and why DP is labeled) is ask the question "What is the most money I can make if I sell on each day (where each day is r, or indicated by the right pointer)?" The only thing you would need, is to keep track of the smallest value that came before. This should thoroughly cover each potential case

I guess it's easier just to update current min price and current max profit at each step class Solution: def maxProfit(self, prices: List[int]) -> int: min_p = prices[0] max_prof = 0 for i in range(len(prices)): min_p = min(min_p, prices[i]) max_prof = max(max_prof, prices[i] - min_p) return max_p

Thanks for making these series of videos, really learned a lot! Do you plan to explain all the 75 questions from that list?

def max_profit(arr): max_profit = 0 left = 0 right = 1 n = len(arr) while right < n: if arr[left] < arr[right]: profit = arr[right] - arr[left] max_profit = max(profit, max_profit) else: left = right right+=1 return max_profit print(max_profit([7, 1, 5, 3, 6, 4]))

Excellent video -I was creating a separate array with profits between intervals and was making it more complicated than needed -this is a really great solution and very intuitive! Good catch with the bug and explaining it at the end of the video.

really good video! I wrote this code in phyton it returns not the maxprofit like yours, it should return the optimal buy and sell point: def buyAndSell(a): left = 0 right = 0 maxProfit = 0 buy = 0 sell = 0 while right a[right]: left = right buy = left elif (a[left] < a[right]) and (a[right]-a[left]>maxProfit): sell = right maxProfit = a[right]-a[left] right = right + 1 return [buy, sell]

I am confused, if this is two pointer solution, why is it called sliding window in the description? Also when you look at this problem the brute force approach was to go with two loops comparing each element with next elements in the array. How can we jump to this approach from there? Just by remembering or is there some trick? Nice explanation by the way, thank you.

thanks for this! line 10: if/else is going to be faster than max given we're only ever going to be comparing 2 values if input was a list (esp of indeterminate size) then max is faster

thanks for sharing, I just realized how confusing my solution was, even myself were troubling to understand it and even smallest problem made me rethink whole solution again

Instead of incrementing left by 1, we can set it to right index. As all the prices between left and right are anyway greater than price at right.

@NeetCode thanks for sharing this! I'm not sure if LeetCode has updated their test cases but the current solution fails for this test case: [1,2,4,2,5,7,2,4,9,0,9] I just tweaked the solution slightly to update the l pointer in this fashion which works: if prices[l] < prices[r]: maxP = max(maxP, prices[r] - prices[l]) else: l = r r += 1 Hope this helps for people who are just coming across this problem and trying to solve it through sliding windows!

Hey man, just wanted to drop by and let you know that your channel is a godsend! :) thank you!

This is perfect. Looking at the other solutions in LeetCode made no intuitive sense. It's perfect how this basically puts into logic what our brain is already doing to work out the same thing.

There is an easier and faster way to complete this: buy = prices[0] profit = 0 for i in range(1, len(prices)): if prices[i] < buy: buy = prices[i] elif prices[i] - buy > profit: profit = prices[i] - buy return profit Here we are instantiating buy as the first element in the list. Then we iterate for the length of the list minus one and update the profit if needed.

Every time I watch, I can not help but marvel the way you evolve the algorithm and the way you write code. Your solutions are classic. BTW. You will hear more of me now.. I need to switch jobs. 😞

I think updating l to r when prices[r] < prices[l] make sense instead of increasing l by 1. as previously we have seen all values and all are greater than l

a similar approach, but using iter() rather than searching over the length of the list. Tested on a 10^8 array. Slightly faster by around 30%. def max_profit(array): max_profit = 0 array = iter(array) current_day = next(array) while True: try: next_day = next(array) profit = next_day - current_day if profit > 0: max_profit = max(max_profit, profit) else: current_day = next_day except StopIteration: break return max_profit if __name__ == "__main__": test_array = [random.randint(2, 8) for _ in range(10000)] end_test = [7, 1, 3, 2, 4, 8, 6, 5, 9] test_array.extend(end_test) print(max_profit(test_array))

In the first part we can make profit higher than 5. Day 2 to 3 profit=4 (5 - 1), day 4 to 5 profit=3 (6 - 3). So total profit will be 7

At the end of the video, when you identify the new minimum price and subsequently move the left pointer to the right pointer's position, a potential issue arises if the last price after the new minimum is only one unit higher than the new minimum. In this case, the calculated answer would be incorrect.

An average programmer might not know about two pointers unless they are into problem solving. What I find more intuitive is to loop through the list and keep track of the minimum (and its index), and simply find difference of the current item with the minimum. The result will be the highest difference (to maximize the profit) that comes after the minimum (we know from the index).

This code worked for me. class Solution(object): def maxProfit(self, prices): lp,rp = 0,1 max_profit = 0 while rp < len(prices): if prices[rp] > prices[lp]: profit = prices[rp] - prices[lp] max_profit = max(max_profit,profit) else: lp = rp rp=rp+1 return max_profit Leetcode accepted this, but not the one in the video. The one in the video was giving wrong answer for prices = [1,2,4,2,5,7,2,4,9,0,9] Output: 8 Expected: 9

Hi Neetcode, Thanks for the explanation, shouldn't this be part of the Two Pointers technique instead of Sliding Window?

I don't think this counts as a sliding window problem. It does have some similarities to a dynamic sliding window but I don't think it's the same. Feel free to correct me though. This problem: Right pointer always moves Left pointer jumps to right pointer if right < left The values between pointers are not important The returned value is right - left Dynamic Sliding Window: Right pointer moves if a condition has not been met (and the right value is included in a calculation) Left pointer moves if the condition has been met (and the left value is removed from a calculation) The values between pointer are part of a calculation The returned value is usually a minimum subarray length

this isn't really your "classic" sliding window problem.. although it does sort of implicitly use the two pointers technique def buylow_sellhigh(prices_array): mx = 0 low = prices_array[0] for curr in prices_array: if curr < low: low = curr mx = max(mx, curr - low) return mx in this solution your two pointers are low and curr hope this helps clear up some of the confusion I see in the comments. A better example of the classic sliding window approach would be "longest sub string w/o repeating chars"

At first I just did a running min one-pass solution like the leetcode solution, but wanted to make it a sliding window to match the neetcode roadmap label. I had a while loop for the else clause while l < r: profit = max(profit, prices[r] - prices[l]); l += 1. You skip this in the video setting r = l based on the graph example. The reason it's possible is because we know that all the prices between left and right are greater than prices[left], so profits are only smaller than the current prices[r] - prices[l]. We know they're greater because the previous loops advanced the right pointer based on prices increasing and if they'd failed to increase we'd have set left = right.

I think in line 11 it should be l = r

I have a question about the algorithm. It's clear that the video is about solving the prob with 2 pointers, but what do u think about the following approach: get the min element from the array -> find the max element inside the rest of the array -> subtract min from max?

Correct strategy. Wrong implementation. This is what I did: class Solution: def maxProfit(self, prices: List[int]) -> int: l = 0 r = 1 maxP = 0 while r < len(prices): if prices[r] < prices[l]: l = r r = l+1 else: diff = prices[r] - prices[l] if diff > maxP: maxP = diff r += 1 return maxP

Here’s a different way to solve it that only took me a few minutes and I’m a total noob… It looks at each number once and simply finds the “current min” and then tests each number that’s higher against a “current max” and just returns the max at the end. Sort of similar, but less complicated than tracking multiple indices imo ``` class Solution: def maxProfit(self, prices: List[int]) -> int: max = 0 min = prices[0] for i in range(len(prices)): if prices[i] < min: min = prices[i] if prices[i] - min > max: max = prices[i] - min return max ```

That doesn't seem to work for monotonically descending sequences. It's better if you do something like this (TypeScript): export function solution(A: number[]): number { const length = A.length if (length === 0) return 0 let left = 0 let right = 1 let maxProfit = A[length - 1] - A[0] while (right < length) { const profit = A[right] - A[left] maxProfit = Math.max(maxProfit, profit) if (A[left] >= A[right]) left = right right += 1 } return maxProfit }

Damn! I always used a brute force way to scan through (i.e. storing all the P differences from test buy-index = 0 and sell index = 1/2/3/4/..., then find their max()) and this took alot of memory. Learnt alot from two pointers here!

x = [7,1,5,3,10,4] max_profit = 0 for i,j in enumerate(x): try: if max(x[i+1:]) - j > max_profit: max_profit = max(x[i+1:]) - j except: break print(max_profit)

got it on the first try 🎉 and thanks man for explaining so clearly

Done thanks The goal is to keep track of minimum and maximum, buy at min and sell at max, but with the constraint that min has to come before max in time To enforce this, we use two pointers, min and max (min is always to the left of max) If max is < min then move min and max pointers foreword. If min (left) < max (right) (as expected) then check if you found a new max profit then move max only forward looking for even higher max.

You are best, dude. I'm growing on your videos!

I think it also could be solved by Kadane's algorithm on prices' returns.

I have a genuine confusion. When can we use a while loop and when can we use a for loop? Because in this scenario, I tried to use a for loop, but I couldn't come up with the logic to make that work. Whereas in multiple leetcode problems, you have been consistently using while loops. And it works.

Awesome work bro. Good explanations for complex algorithms. 🖥️

hey Thanks for your content-- it's been helping me a lot. I have a question about this problem I was a bit confused in the beginning because I was trying to solve it with slide window but then I watched your explanation and I could see that it's actually two pointers. As I know slide window is when the window a fixed size, but I can see here that the window can grow as soon as you are moving the right pointer. Help me out here, is this also considered slide window? Thanks for your help

My version (pretty much the same): class Solution: def maxProfit(self, prices: List[int]) -> int: max_profit = 0 purchase_price = prices[0] for num in prices[1:]: if num < purchase_price: purchase_price = num else: current_profit = num - purchase_price max_profit = max(current_profit, max_profit) return max_profit

class Solution: def maxProfit(self, prices: List[int]) -> int: L = 0 res = 0 for R in range(1, len(prices)): if prices[R] < prices[L]: L = R else: res = max(res, prices[R] - prices[L]) return res

Complete Code - int res = 0; int l=0,r=1; while(r

I feel awesome today because I figured out this solution myself. (Took me about 30 min for an easy problem tho lmao)

You should update left pointer when the price[r] is lower then price[l] so he can get total max profit

Understandable, simple and meanwhile useful! But why is this problem sets in the sliding window section instead of two pointers?!

I found this solution a bit confusing. You don't need two pointers. You never use the left pointer for anything except looking up the price (i.e. there's no pointer math), so you could have just stored the minimum price itself instead of a pointer to the minimum price.

I have two questions. Thanks for the help! In the scenario where `l` moves to a new index, there may be cases where `r` should remain in place to potentially find a better profit in future iterations. Even when prices[`r] is greater than `l`, don't we still want to move l by having l+=1 to make sure that we find the lowest possible buy price (`l`)?

I think the "single pointer solution" is much cleaner: First notice that the max profit we can make if we buy at time `i` is `max(price[i+1:]) - price[i]`. Also notice that if we iterate through the array BACKWARDS, then we can keep track of `max(price[i+1:])` as we go along... Then just do it: ```python max_profit = 0 max_after_i = price[-1] for cost in reverse(price): max_profit = max(max_profit, max_after_i - cost) max_after_i = max(max_after_i, cost) ```

class Solution: def maxProfit(self, prices: List[int]) -> int: max_profit = 0 min_price = prices[0] for price in prices: min_price = min(min_price, price) compare_profit = price - min_price max_profit = max(max_profit, compare_profit) return max_profit

I know this video is 2 years old but bro I love you❤️

Runtime of 90ms on the video, +2800ms on my solution made me think I was going nuts or just screwed up somewhere but I copied neetcode's answer and it still gave me +2800ms.

This explanation is so good that it stuck with me for 9 months after watching it the first time. Really appreciate the work you do!

2:15 you actually can go back in time to sell at that price with options

I tried if before knowing the Sliding window concept. Learning new concept everyday int: maxP = 0 val = prices[0] for i in range(1, len(prices)): if prices[i]

I need to learn how to take advantage of "while" loop. Always using for/range loops

What sliding window has to do with this? We use two pointers technique here (comparing prices at the left and right pointers). In sliding window problems we generally care about the values between the left and right pointers as well. At least that's how I understand it. Correct me if I'm wrong.

Your code does not work on leetcode , It seems that the code may be facing efficiency issues, leading to a time limit exceeded error on LeetCode

amazing video!!! learn a lot in short time

Awesome Explanation !!!

Nice explanation. I think there is another approach we can think. We just have to know what is the minimum price we visited so far and calculate the profit with the current and minimum price. class Solution: def maxProfit(self, prices: List[int]) -> int: minPrice = prices[0] result = 0 for p in prices: minPrice = min(minPrice, p) result = max(result, p - minPrice) return result

Interestingly you can also create a new array of size prices.length, and fill it with the change in stock price on that day, so priceChanges[i] = prices[i] - prices[i - 1] and then it becomes the maximal sum sub array problem and you can solve with Kadanes algo

I have a idea please tell me if it's gonna work : We can arrange the prices list in ascending order and then select first I index as buing price (as it is lowest in this case 1 ) and then assign a variable to last index (7) and then calculate max profit that is [selling price -buying price ] 7-1= 6 We will get similar output right?

I could solve the problem immediately after I saw the condition in the explanation that when price[r] < price[l] , bring left_pointer to right_pointer's place. But how to come up with these conditions intuitively?

Thank you for these videos. Just one thing: if the price only decreases as the days goes by, this solution would work? I.e. getting the lowest loss

Thanks for the explanation. I have a question about the last few seconds. It seems like we still need to find out what the profit for the last step is. If profit is not more than max so far, don’t update the left and right pointers. Is that right?

perfect video! Since the title says "sliding window", does it mean the two pointers method is the same as sliding window for this problem?

love the problem and love the solution

Awesome explanation dude

Love your two pointer strategy. Way more simple and concise than nested for loops--will be using this for many problems in the future :)

Appreciate you efforts, hats-off to your commitment for helping the community. I'd like to bring you attention to a problem in the code , in the else part , the left pointer should be shifted to right pointer's position, this can be easily verified by a dry-run and also in leetcode

Why is this slower? I loop through each element a single time... def maxProfit(self, prices: List[int]) -> int: lowest = float("inf") best = 0 for price in prices: lowest = min(lowest, price) best = max(price-lowest, best) return best

This is not a sliding window, but rather 2 pointers solutions. It confused me as I was looking for a sliding window solution.

Thanks for this, it makes so much sense!

Serious question, Isn't this problem supposed to be medium level ?

Maybe this version with less code lines will be interesting def maxProfit(self, prices): if not prices or len(prices) < 2: return 0 max_profit = 0 min_price = prices[0] for price in prices[1:]: max_profit = max(max_profit, price - min_price) min_price = min(min_price, price) return max_profit

I don't understand how this is linear since it takes the first element then goes through all the others, then the 2nd and goes through all the others and so on. Why isn't it exponential? :/

Your joke about time made me laugh at 8 in the morning. Cheers!

2:17 Fun fact (not related to the problem) In the stock market you can also earn money with this type os situation.

Don't forget to increment the right pointer after the first if statement, otherwise you would never reach the end of the list!

import math class Solution: def maxProfit(self, prices: List[int]) -> int: z = math.inf res = 0 for i, y in enumerate(prices): if y < z: z = y elif y > z: res = max(res, y-z) return res