Best Time to Buy and Sell Stock - Leetcode 121 - Arrays & Strings (Python)

[@GregHogg]

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

[@wilmahutson-e5w]

This is the best channel hands down. Quick to the point, optimal, simple. Thank you!

[@microscorpi0n]

The hardest part about my approaching this problem is the fact that LC's topic tag is DP. I spent 2+ hours trying to identify the recurrence relationship when this solution was more straightforward. Appreciate that your algomap roadmap categorizes this as Arrays and Strings. I suppose that may have helped with my approach. I didn't realize this problem was in your roadmap until after I attempted it after working on LC's daily challenge from Aug 17, 2024 was LC1937 - Maximum Number of Points with Cost, which suggested the Buy and Sell Stock 1 problem as helpful for recognizing the approach to solving.

[@mhmdshaaban]

It was misleading for me as well. I usually spend some time trying to come up with different solutions, even if I find an efficient one. After I checked the tags and saw DP mentioned, I was like, what the hell is DP doing here?

[@fernandolucas2740]

Totally Agree. Same situation Here.

[@ngneerin]

min_price = float('inf') max_profit = 0 for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit

[@playfuss]

I understand the solutions, but when you start at 3:00 it would be nice to know the steps that you took in your mind to finding this solution. My challenge is being able to identify the solution

[@RapidBee]

I appreciate this, visualizing it helped a lot

[@SebastianBeresniewicz]

What if in the optimal solution your first example started with 2, 8 (And then retained the original values right after)? You wouldn't catch that the max profit would be six because you would later move to use one as your min price and then later capture a Max profit of five wouldn't you?

[@CKARlife]

simple class Solution: def maxProfit(self, prices: List[int]) -> int: min_price = float("inf") maxP = 0 for p in prices: min_price = min(min_price, p) profit = p - min_price maxP = max(profit, maxP) return maxP

[@new-anointingaremu3597]

Why do you always use infinity instead of not initializing the variable at all or setting the variable to 0 instead of infinity

[@jamestacular]

If min_price was defaulted to 0 then none of the prices would ever fall underneath it. The point is to set a variable that for certain will be overwritten by the first value (prices[0])

[@yairkaz]

@@jamestacular You can instead initialize min_price to the first variable in the array and in the O(n^2) solution you could have just set max_profit to 0.

[@sierraobi311]

@@jamestacularhow is this true? Say you have an array of practices where all the numbers are non-zero. Why wouldn’t min price be overwritten? Just depends on how you set up the if clause I suppose.

[@Infinitely16]

@@sierraobi311 the problem constraints say "0

[@_sharkdev_]

In the brute force solution, is the check for if profit > 0 necessary? I don't work with python, so does its max function have issues when handling zero as an argument?

[@AnshuKumar-vr4cv]

Which language?

[@sgetti4dinner]

Why do we want to keep track of max profit and not max num?

[@GregHogg]

Because that's what we're trying to find

[@tuandino6990]

I solved this using dp

[@joaoc4508]

could you explain how to use dp here?

[@hamadrehman853]

@@joaoc4508 check neetcode videos. he uses a two pointer approach for this. in neetcode blind 75 series this is the 2nd problem he solves. I came here because his approach was too confusing.