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)
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
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!
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?
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.
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
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.
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
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.
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.
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
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.
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 :)
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.
@@cmelch 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.
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
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 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
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
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.
@@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
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.
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 :)
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
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.
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
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.
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.
@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!
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]
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))
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
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
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 ```
You're actually doing the same thing, just in a different flavor. Your "min" variable is acting like the left pointer while the "i" in the for loop is your right pointer. That said, I find your way easier to follow.
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
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
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).
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.
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 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.
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`)?
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
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"
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 }
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. 😞
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!
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
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]
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.
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
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
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) ```
the time complexity is greater, since you're calculating maximums on each iteration. the presented solution only goes through the array once, having linear complexity. in the end, it really depends on the reader - if you prefer cleanliness instead of efficiency, that's alright.
@@BrunoBeltran that's right. for some reason I was under the impression that you're using the max function on a list, while you're actually using it so you can find the max of two variables.
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.
There are 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 as 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 windows and are more generalized as they can move in different directions that cause them to cross or can be on different arrays. They still have a window per se 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 size 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. - @Connor Welch I had the same doubt but this helps
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?
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
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 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.
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?
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.
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
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
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
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
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.
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? :/
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.
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!!
just buy put options on day one and sell them on day two? You can absolutely buy a stock ahead of time. You buy a put options contract which is the right to sell at a certain price. Simplified you are borrowing stock from someone who owns it at the price at day one, selling it immediately for that price, and then buying the stock on day 2 and returning it stock the person you borrowed it from.
🚀 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
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?
Best interview prep channel I've found. Really appreciate how succinct you are in explaining things, while also still covering the necessary concepts.
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.
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!
@@infrequent_traveller 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.
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.
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.
This is way better than 2 pointers since it's based more on common sense than "clever sliding techniques".
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.
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
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.
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...
@@kuoyulu6714 hope everything is working out with you now! best of luck in life my guy, you got this
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.
@@cmelch prefect expansion tysm
@@cmelch great explanation
@@cmelch 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
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 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.
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
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
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.
*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 👍🏻
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
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
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]))
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
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.
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
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.
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
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
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.
@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
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
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
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))
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
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
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
```
You're actually doing the same thing, just in a different flavor. Your "min" variable is acting like the left pointer while the "i" in the for loop is your right pointer. That said, I find your way easier to follow.
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
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
I think in line 11 it should be l = r
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?
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).
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.
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 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.
Hey man, just wanted to drop by and let you know that your channel is a godsend! :) thank you!
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`)?
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
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"
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)
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
}
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. 😞
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
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
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]
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.
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
You should update left pointer when the price[r] is lower then price[l] so he can get total max profit
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
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)
```
the time complexity is greater, since you're calculating maximums on each iteration. the presented solution only goes through the array once, having linear complexity.
in the end, it really depends on the reader - if you prefer cleanliness instead of efficiency, that's alright.
@@John-ye8sj are you saying the code I gave is not O(n)? You might want to look again.
@@BrunoBeltran that's right. for some reason I was under the impression that you're using the max function on a list, while you're actually using it so you can find the max of two variables.
@Bruno Beltran nice, but it's not that intuitive
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
Understandable, simple and meanwhile useful!
But why is this problem sets in the sliding window section instead of two pointers?!
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.
There are 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 as 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 windows and are more generalized as they can move in different directions that cause them to cross or can be on different arrays. They still have a window per se 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 size 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. - @Connor Welch
I had the same doubt but this helps
2:15 you actually can go back in time to sell at that price with options
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?
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
you are right, it works. appears to be simpler
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
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
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
:)
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...
You are best, dude. I'm growing on your videos!
Complete Code -
int res = 0;
int l=0,r=1;
while(r
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.
use a for loop when you know how many times the loop should run, use a while loop when you do not know that but you do know when it should stop
@@DetectiveConan990v3 Thank you.
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?
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.
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
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
for test case [1,2] the loop false condn must be r < = len(prices) -1 coz r =1 initially and this wont go through the loop so
Why it won't go through the loop. The len is 2 so 1
Awesome work bro. Good explanations for complex algorithms. 🖥️
I feel awesome today because I figured out this solution myself. (Took me about 30 min for an easy problem tho lmao)
got it on the first try 🎉
and thanks man for explaining so clearly
If you decide to short the stock day 1 and 2 are the best :D
2:17 Fun fact (not related to the problem) In the stock market you can also earn money with this type os situation.
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
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
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 know this video is 2 years old but bro I love you❤️
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
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.
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? :/
var maxProfit = function(prices) {
let smallest = prices[0];
let amount = 0;
for(let i = 1; i < prices.length; i++){
smallest = Math.min(smallest, prices[i])
amount = Math.max(amount, (prices[i] - smallest))
}
return amount;
};
Can we sell the stock before buying. ie. Can the first day stock(7) be bought? Is that valid?
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.
I am not crazy! I know he swapped those numbers. I knew it was 1216. One after Magna Carta. As if I could ever make such a mistake. Never. Never!
This is not a sliding window, but rather 2 pointers solutions. It confused me as I was looking for a sliding window solution.
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
Thanks for this, it makes so much sense!
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!!
just buy put options on day one and sell them on day two? You can absolutely buy a stock ahead of time. You buy a put options contract which is the right to sell at a certain price. Simplified you are borrowing stock from someone who owns it at the price at day one, selling it immediately for that price, and then buying the stock on day 2 and returning it stock the person you borrowed it from.
Serious question, Isn't this problem supposed to be medium level ?
For most people, it's too easy.
But if you are seeing two pointer solution first time, it may be little hard for you