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?
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.
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 :)
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.
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
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.
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.
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
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
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
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
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 :)
@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!
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))
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
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 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 ```
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.
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!
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.
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.
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
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) ```
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.
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 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]
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
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?
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
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?
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
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? :/
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