Strong Noob Programmer vs O(n) Remote Engineer on Best Time to Buy and Sell Stock, Leetcode 121

Master Data Structures & Algorithms for FREE at AlgoMap.io/
Code solutions in Python, Java, C++ and JS for this can be found at my GitHub repo here: github.com/gah...
Complete DSA Pathway Zero to Hero: • Data Structures & Algo...
Please check my playlists for free DSA problem solutions:
• Fundamental DSA Theory
• Array & String Questions
• 2 Pointers Questions
• Sliding Window Questions
• Binary Search Questions
• Stack Questions
• Linked List Questions
• Tree Questions
• Heap Questions
• Recursive Backtracking...
• Graph Questions
• Dynamic Programming (D...
My Data Science & ML RUclips Playlist: • Greg's Path to Become ...
Learn Python and Data Science FASTER at mlnow.ai :)
University of California DSA Certificate on Coursera: bit.ly/3CYR6wR

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@smitcher]

You are updating the minimum price first… what if the list ends with a 1… you can buy at 1 yes but can never sell…

[@notIBcomp]

technically you could add a `continue` statement after min_price = price in the if statement, cus then for sure profit = price - price = 0 and of course that is already our max_profit in the beginning no? This statement sucks because it makes it harder to understand the code flow, but because this isn't about code readability rather for speed and efficiency, I think it would be worth to add it :)

[@Bruh-bk6yo]

And here is me who thought about this dumb approach:
Find a minimum, find a maximum, if the maximum has a higher index than minimum - return the absolute value of their subtraction.
Otherwise, we divide the array on [..., (maximum), ..., ..., ...] and [(minimum), ..., ..., ..., ...], where for the right array we find the maximum and take the subtraction in mind, and for the left - repeat the process, compare and so on...

[@Baaldrian]

Hmm.. I don't get it :( You can only see what the best price was. Where is the future part? If Wendnesday was the best price and now it is Friday.. you can't go back in time.. you can just say: well we would have had a better deal on Wednesday... Or am I wrong?

[@rishisutar]

Can I use two pointers approach here

[@yugaank100]

yes, why not ?

[@mujtabarehman5255]

I think sometimes there’s a fine line between a sliding window algorithm and two pointers.
Here the “price” is basically the right pointer and “min_price” is basically the left pointer. So yeah that would work too.

[@rehanadisatrya554]

@@mujtabarehman5255but how to determine when to shift then?

[@iid4rk111]

Its already 2 pointers
One keep track of the minimum and the other to get the max diff which is i

[@LawZist]

Isn’t it sliding window algo?

[@arsheyajain7055]

Damnnn 💪 💪 💪

[@DarinSimmons]

Love the series, the audio reverb/feedback is so awful in this video. Keep up the great work.

[@wbarbosabr]

MAYBE I've overengineered it a little, but...
The maximum profit will involve the minimum (logical) OR the maximum value.
Besides those values, we'll need to track two more: The minimum value before the maximum and the maximum value after the minimum.
I also kept track of the positions of those values, but now I'm writing about this algorithm I just discovered there's no need for it.
Then, you return the bigger value from those: Maximum value after minimum - Minimum and Maximum - Minimum value before maximum, if the minimum occurs before the maximum those values will be the same.

[@smnsr05]

this doesn't work when your max comes first and your min comes last, such as [4,2,3,1]

[@kaze812]

Cant we just sort the array and give the difference between last and first element, does it take more time and not efficient?

[@ChalanthornC]

No, consider this example, 4 3 5 2 1. The answer should be buy 3 and sell 5. You cannot sorted the price because the past price and future price will get mixed up. (You cannot buy 1 sell 5 cuz 5 is before 1)

[@kaze812]

@@ChalanthornC oh, got it, so the order of numbers is imp, my bad, thanks a lot 👍

[@badstep495]

how is this correct? there will be sequences where the minimum price comes after a maximum and your profit potential is not optimal. You have to evaluate the difference between the price at day i and the price at day i + n for each i, return the maximum.

[@gerardomiranda2284]

You don't have to, you are forgetting that the max profit is being stored. If the minimum comes after a max profit like:
[ 3, 4, 10, 2, 8 ]
- The minimum is 3 until the 2 is reached. But the max profit is 7, because of 10 - 3
- The minimum is then changed to 2
- The max profit is still 7 because there is no profit that beats 7 using the 2 as minimum

[@badstep495]

@@gerardomiranda2284Ah, yes you are right. Thanks for clarifying, I stand corrected :)