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

[@GregHogg]

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

[@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

[@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.

[@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

[@keelanurnishanth5801]

This was my attempt without keeping any complexities in mind. It fails at a later test case when prices =[2,4,1] and expected is 2 and my output is 0
min_val=min(prices)
min_index=prices.index(min_val)
max_val=max(prices[min_index:])
max_index=prices.index(max_val)
if min_val==max_val :
return 0
else:
return max_val-min_val

[@vishwash7416]

same

[@_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.