Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python
Vložit
- čas přidán 28. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/buy-and-...
0:00 - Read the problem
0:52 - Drawing solution
5:40 - Coding solution
Leetcode 121
coding interview question
#python #leetcode #neetcode
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
I found even more simple solution, but I can't understand why it works:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
difftemp = 0
n = len(prices)
res = [0]
for i in range(1,n):
difftemp+= prices[i] - prices[i-1]
difftemp = max(0,difftemp)
res.append(max(0,difftemp))
return max(res)
@@PurpleDaemon_ This is not simple. You're using more space...
There is a simpler solution. You move backwards, keeping track of current maximum and updating the profit in case you find a better minimum.
Hey bro, in this case we are only returning the MaxProfit, in there any way where we can get the L and R value at when the profit was Maximum????
Thanks in Advance
@@gugolinyo yes, i find the same solution ahaha
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.
Happy to help!
@@NeetCode Yes, thank-you man. You're very easy to understand, and you have a calm way of explaining things. It makes me feel like I can do it too!!
broh where did u compile these programs
Best interview prep channel I've found. Really appreciate how succinct you are in explaining things, while also still covering the necessary concepts.
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!
i feel the same way. all the best to you! keep up the grind. cheers!
Keep on practicing. With time you'll get better.
There's a book called Elements of Programming for both Python and Java . Check that out. It has around 20 chapters each contains 12 - 15 problems. If you practice those problems you'll get a good intuition how to solve these problems
Frustration is a good thing, it's some kind of indicator that this problem you're solving is getting out of your comfort zone. Which means that trying to solve that problem will create new neurons, and seeing the solution will also create new neurons. And in fact you can solve one problem that is out of your comfort zone, but it doesn't mean that you can solve all the problems that are out of your comfort zone, but the fact that you have created new neurons is a good thing. And in time, when you repeat this many times, your non comfort zone will become a new comfort zone and so the cycle will be repeated endlessly. This is the essence of cognition, life-long cognition.
One year later here I am in the same boat as you were one year ago. Almost losing hope. Had a few very bad interview experiences. Did you get your dream job? How did you practice?
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
That was running in my mind too. But your comments cleared that. I had missed max profit of the logic. Thanks
Exactly, the same question arrived in my mind. But your comment made it clear. Appreciate your effort of clearing the air over this.
I also thought this but now I see. thanks!
@@sreesankalpYengaldas what is the issue with this test case? It returns 3 which is correct (index 2 to index 3)
Yes thats a good observation. We are updating and comparing the max profit every loop, therefore even if we find the delta between the new lowest value is not greater than the previous, we will still get the most profit.
Was having that same doubt regarding the bug you found at the end of the video. Glad to have it cleared up.
Hey man, just wanted to drop by and let you know that your channel is a godsend! :) thank you!
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 :)
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.
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.
Yes, I solved that way. Solution passed in the Leetcode. So, I think both solutions are ok.
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.
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
"We have already calculated what the profit was for the elements between these two, so we freely make l = r"
This is quite misleading. If we find a new minimum - a new lowest price - we don't even calculate the difference between this and the previous lowest price, because there is no point. There is no point because the profit will be in the negative, you are losing money, and your lowest profit by problem definition can be 0.
If a new lowest price is found as you iterate through the list, you simply update the lowest price pointer. That's it. No other calculation is even needed.
Thanks for this, it makes so much sense!
This solution is so much more intuitive and easy to understand the kadane algorithim solution lc provided. Love to see it!
Yeah I think this one should be labeled medium. I think the only reason it's marked as easy is because whoever wrote it assumes that everyone learned Kadane's algorithm in school
Thanks for making these series of videos, really learned a lot! Do you plan to explain all the 75 questions from that list?
Thanks for watching! Yes, I think I plan on having videos for most of those problems!
@@NeetCode Thank you man, your videos are very helpful to me. The drawings, the codes, the explanations are very clear. keep doing this please
Awesome work bro. Good explanations for complex algorithms. 🖥️
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 :)
There's two types of sliding windows. Fixed sized and dynamic. Fixed sized windows have a set window size. Dynamic usually has two pointers that move in the same direction like this problem and Longest Substring Without Repeating Characters. The window expands and shrinks depending on the subset you're looking at in the array. Two pointers are essentially a subset of sliding window and are more generalized as they can move different directions that cause them to cross or can be on different arrays. They still have a window per say think as the pointers move towards each other the window is the left and right boundaries but is constantly shrinking.
If all of that is confusing just think a window can have a fixed sized or have two pointers that move in different directions and/or speed that grows and shrinks the window to capture a specific part of the problem.
@@connorwelch6265 prefect expansion tysm
@@connorwelch6265 great explanation
@@connorwelch6265 Good explanation. To add to this, I think of two pointers when I only care about the elements at those two pointers. And I think of sliding window when I may also care about what's between the start and end pointers.
great
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.
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.
@@vigneshA-qq8xz I too had the same doubt. Thanks Vignesh for the clarification
I thought I spotted the same bug ;-)
@@vigneshA-qq8xz what if l = [2,8,0,9] ? The output of his coude would be 6 but the correct output is 9
@@barhum5765 No , It will return 9
Suppose we start with l=0 and r=1 and MaxProfit=0
1st Iteration
CurrProfit=stock_arr[r]-stock_arr[l]=8-2=6
since the currProfit is not negative we don't have to shift our L since the buy price will not be lower than the current
getMaxProfit by comparing MaxProfit with currprofit
before starting *2nd iteration*variable values are :
l=0,r=2,MaxProfit=6
CurrProfit=stock_arr[r]-stock_arr[l] =0-2=-2
since the profit is negative we know we have an opportunity to buy at a lower price
we shift our l to current r
Max profit remains the same
values before Iteration3 (final Iteration)
l=2,r=3,MaxProfit=6
CurrProfit=stock_arr[r]-stock_arr[l] =9-0=9
now upon comparing with max_profit 9 >6
so max_profit will be 9 not 6
@@rohitsingh-et4dx There was a mistake in the video. He wrote in his code l+=1 and not l=r. When he tested in end the solution the mistake was fixed.
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
*AAAAH* this is *SO MUCH CLEARER* than the dang solution tab for this problem on LC! THANK YOU.
except for the fact that it doesn't works on leetcode
@@e889. Are you using the code at 7:49? That works just fine. There was a bug earlier around 7:35 that he corrected later in the video.
@@codeisawesome369 ok 👍🏻
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
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.
I know exactly what you are talking about. I am on the same bender
@@guratete and 6 months later i finally have time to work on resume, omg...
In the while loop shouldn't we also include one more condition l
no, even though the left pointer l will reach the last element of the array, the while loop will be exited since there is no element left for the right pointer r.
great work! thank you very much
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
lol
Love your explanations so much! Thank you!
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. 😞
got it on the first try 🎉
and thanks man for explaining so clearly
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.
I really found it confusing. I was increasing the left by 1. I got how he explained it, but still wrapping my head around it 😁😁😁
Consider this - Left is the minimum price so far until you find a new right index where the price is the new minimum.
Let's say you found the new minimum at the "right" index.
This means all the prices from "left + 1" till "right - 1" must be greater than the price at left. So, there is no way you can get a more significant profit with these indices.
So, set the left = right instead :)
U mean to say something like this right?
while r
You are best, dude. I'm growing on your videos!
why can't we make l = r in case of if condition false at line numb 8. from l to r we might have seen all the combinations and its for sure l+1 can not be minimum than l in l to r window.
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
Thank you! He's code was incorrect and gave errors
I was about to provide the correct answer, but I see you've already covered it. We all appreciate your efforts.
Awesome Explanation !!!
Such a nice explanation!
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
amazing video!!! learn a lot in short time
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?
I don’t think it matters because we only need to return the max profit
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]
Your right should start at 1 and you don't need both the "right and left" and "buy and sell" as these are variables for the same value
ugly
Your joke about time made me laugh at 8 in the morning. Cheers!
great job man!
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.
I thought I'm not supposed to use 2 pointers too because it's called sliding window XD
sliding window is a type of two pointer solution
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?
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!
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.
Send solution
This is a nice solution, and I think easier to explain/prove. My implementation:
class Solution_2:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
N = len(prices)
max_from_right = [0] * N
max_so_far = prices[N-1]
for i in range(N-1,-1,-1):
max_so_far = max(max_so_far, prices[i])
max_from_right[i] = max_so_far
for i in range(N):
profit = max_from_right[i] - prices[i]
max_profit = max(max_profit, profit)
return max_profit
Love your two pointer strategy. Way more simple and concise than nested for loops--will be using this for many problems in the future :)
you only need 1 for loop, it's easier
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.
If we assign left pointer to right which is at the last then?
we can use euclidian algorithm as well right?
when you did l=r, will this cause shallow copy? I use this and I got my output always as zero....
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
found this approach easier...
I need to learn how to take advantage of "while" loop. Always using for/range loops
Use a for loop when you know the size of a container
Use a while loop when you want to continually do something until a condition hits
:)
So the sliding window is a variation of the two pointer technique?
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!
Thats O(n^2) and wont even be accepted by leetcode...it gives TLE
I think in line 11 it should be l = r
You are a gem!
I know this video is 2 years old but bro I love you❤️
For contains Duplicate in leetcode if i use unordered_map is uesd in cpp then for following example [1,2,...n,1] the insertion time complexity becomes n-1 * n and dosen't it become n^2 solution instead of O(n) Time and space complexity
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
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?
Awesome explanation dude
perfect video! Since the title says "sliding window", does it mean the two pointers method is the same as sliding window for this problem?
a window usually has two pointers to make it a "window" so...
AMAZING CONTENT 10/10
@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!
He must’ve updated his solution
his solution gives 9 for your scenario, which is the answer, isnt it?
+Viraj Mehta @Virah Mehta
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
Hi Neetcode, Thanks for the explanation, shouldn't this be part of the Two Pointers technique instead of Sliding Window?
Hmmm, you might be correct. Considering our answer isn't a contigious set within the window. It's just two pointers that hold our answers.
agree, there is no reason to use sliding window. just need two pointer technique
Can we sell the stock before buying. ie. Can the first day stock(7) be bought? Is that valid?
Thanks a lot, sir 💕
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.
so were you able to solve this with sliding window ? if yes then kindly share the solution
Does anyone know why we didn’t say len(prices) -1?
How to find and return the indices of best day to buy and best day to sell with max profit?
turns out i was doing it the slower way, with a nested loop, never knew about the two pointers method
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
Quick question LeetCode considers this question a dynamic programming question does anyone understand why?
Hello, Im new to leetcode so unfamiliar with how things are done usually, and I have a question about this
If we sort the array in ascending order, have two pointers at idx 0 and idx -1, and increment L by 1 and R by -1 alternatively until we find two values which follow the buy->sell order in the original array, wouldnt this work as well?
From my understanding this approach would have similar time and space complexity to this optimal solution shown in the video
If anyone can disprove or explain why this approach is bad, please help me learn!
If you decide to short the stock day 1 and 2 are the best :D
what if the minimum is the very last element? you can't buy on the last day since there is no day left to sell, is this case is covered in this soln?
If 'r' the last one and 'l' is the next-to-last one when the loop iteration ends, then after increasing 'r' by one the loop breaks, so case covered
Thank you!
I think it also could be solved by Kadane's algorithm on prices' returns.
There's also JohnMcCain's algo
kadane algo can solve anything
thx for the explaination
Is this an optimal solution. I had pretty much the same solution but it only beats 30% solutions and there are people who solved it using numpy & their solutions are much better. Just wanted to know if in a coding interview, I solve using this instead of the numpy method, would I still clear the interview or not?
What’s the time and space complexities for this?
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
why you are the only one mentioning this? I thought the same. Max should be 7. what am i missing here?
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))
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
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
the code is not supposed to do that, it's supposed to compute the maximum profit, not the minimum loss, if you talk about minimum loss it means you cannot get any profit and so the maximum profit is 0
love the problem and love the solution
I feel awesome today because I figured out this solution myself. (Took me about 30 min for an easy problem tho lmao)
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? :/
Hi bro.. do u have the solution to "Best time to buy and sell stock III"... I am in dire need of it!!... The other solutions in the internet are totally going above my head!!
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
i was trying to solve some dynamic programming questions and for some reason this was under dynammic programming tag
“Right is gonna be to the right of left”
-Neetcode 2021 what a legend
what is the time and space complexity of this problem?
I am not able to understand how this problem is under window sliding .please help !!
Thank you !!!
I`ve came up with the exact same solution, but leetCode says that it faster than only 5%
Is there any faster solution???
Why is it call sliding window why it use 2 pointer way, anyone plz explain
Is there a reason why it’s using while loop instead of for loop?
While loop just in case the array input keeps increasing…for loop would work if we know for sure that the array input is not going to increase so we would iterate 8 times since the input here is 8 elements
Forget Netflix, I am gonna watch this from now on 😊