DEV Community

Cover image for [Neetcode] When to buy and sell stock
nicha
nicha

Posted on

[Neetcode] When to buy and sell stock

#leetcode

This is my first article in the Neetcode practice series. In this series, I'll be jotting down my approach to problems and how I pick up better habits along the way.

So, let's dive in!

This problem is here:
https://neetcode.io/problems/buy-and-sell-crypto?list=blind75

Essentially, the goal is to determine the lowest price to buy a stock and the highest price to sell it at to maximise profit.

Bruteforce

The most straightforward way to tackle this is to loop through every possible "buy" price, then check every "sell" price after it, calculating the profit each time to find the maximum.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        for index, p in enumerate(prices):
            for j in range(index+1, len(prices)):
                profit = prices[j] - p
                if profit > max_profit:
                    max_profit = profit 

        return max_profit
Enter fullscreen mode Exit fullscreen mode

The outer loop picks a buy price. The inner loop then scans all the prices after the buy price to find a sell price. We calculate the profit for each pair and update max_profit if a better one is found.

This setup involves a nested for loop, resulting in a time complexity of O(n^2) – not ideal for large lists.

A Better Approach

If I step back and think about it, we only need to go through the prices once. We can keep track of the lowest buy price we've seen so far and, as we iterate, continually update our max_profit with the current sell price minus that lowest buy price. If we encounter a price lower than our current buy, that becomes our new buy price, because it opens up the possibility of even greater future profits.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        buy = prices[0]
        for sell_price in prices:
            max_profit = max(max_profit, sell_price-buy)

            # If the current 'sell_price' is lower than our 'buy' price,
            # it means we found a new, better (lower) potential buy point.
            # So, we update our 'buy' price.
            buy = min(buy, sell_price)
        return max_profit
Enter fullscreen mode Exit fullscreen mode

In this code, we start to buy from the very first price. As we loop through prices (treating each sell_price as a potential sell point):

  1. We calculate the profit we'd make if we bought at our buy price and sold at the sell price.

  2. We update max_profit to be the higher of its current value or current profit.

  3. Crucially, we then check if sell_price is lower than our current buy price. If it is, then the sell_price becomes our new buy price, because buying at that point would give us a better starting position for future profits.

This single loop means our time complexity is significantly more efficient, at O(N).

Keep Going
If you're on the same journey of practising LeetCode, let's do this together!

For a bit of extra motivation, I want to share some wise words from the author of this Anki deck: https://ankiweb.net/shared/info/1941530701

Getting good at DSA is not about having a strong intuition or being good at puzzle solving. If I ask you some dumb math like 2+2, you instantly know the answer is 4. This is because you have spent years and years using and testing your basic arithmetic skills. If you ask a 2 year old what 2 + 2 is, they'll likely tell you their favorite color is yellow. The 2 year old is not dumb, they just don't have enough exposure to arithmetic concepts yet. Learning DSA is similar.

If it takes you 1 hour to solve an easy, it doesn't mean you're stupid. It means you're wasting your time. Limit how much time you spend with each problem to maximum 5 minutes, before looking at the answer. Then use spaced repetition to revisit problems you've already learned how to solved in the future. If you limit the amount of time you spend on each problem, you will solve 10 times more problems an hour. You will have exposure to all the tools you need to solve almost any problem on leetcode in a month. You will be able to solve most new problems in less than 5 minutes, which gives you plenty of time to solve similar problems in a room full of strangers for 4 hours straight.

We got this! Until we meet again, Happy coding :)

Top comments (0)