LeetCode #121 Best Time to Buy and Sell Stock Solution & Explanation

LeetCode Problem

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

---

Solution

When I first saw this question, the first thing that came to my mind was …

2022 stock market …

C# Solution

❌First Try – Time Limit Exceeded

public class Solution {
    public int MaxProfit(int[] prices) {
        
        int max = 0;
         for(int i = 0;i<prices.Length-1;i++)
         {
             for(int j = i+1;j<prices.Length;j++)
             {
                 int res = prices[j]-prices[i];
                 if(res>max)
                 {
                     max = res;
                 }
             }
         }
        return max;
    }
}

I think this was the first way you have already tried haha !

It doesn’t have any problem but too slow (with a nested loop)

Time Complexity : O(n²)

Solution1

Let’s try another solution.

First, initialize two parameters – 【min– set as first element of array】 and 【max – 0】.

And in the iteration, if prices[i] is less than min, we will set it as min.

Else, check the diff of prices[i] and min, if the diff is greater than max, than set the diff as max.

In this solution, we just need to run the iteration n-1 times. (n = length of array prices)

public class Solution {
    public int MaxProfit(int[] prices) {
        int max = 0;
        int min = prices[0];
        
        for(int i=1;i<prices.Length;i++){
            if(prices[i] < min){
                min = prices[i];
            }
            
            else if((prices[i] - min) > max )
            {
                max = prices[i] - min;
            }
        }
        return max;
    }
}

Time Complexity : O(n)

Java Solution

Solution1

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int min = prices[0];
        
        for(int i=1;i<prices.length;i++){
            if(prices[i] < min){
                min = prices[i];
            }
            
            else if((prices[i] - min) > max )
            {
                max = prices[i] - min;
            }
        }
        return max;
    }
}

Python3 Solution

Solution1

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max = 0;
        min = prices[0];
        
        for i in range(1,len(prices)):
            if prices[i] < min :
                min = prices[i]
            
            elif((prices[i] - min) > max):
                max = prices[i] - min
        
        return max;

JavaScript Solution

Solution1

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    var max = 0;
    var min = prices[0];

    for(var i=1;i<prices.length;i++){
        if(prices[i] < min){
            min = prices[i];
        }

        else if((prices[i] - min) > max )
        {
            max = prices[i] - min;
        }
    }
    return max;
};

Runtime : 78ms、113ms、93ms

---

Submission Detail

---

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot !

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)

"If stock market experts were so expert, they would be buying stock, not selling advice."
                                                                                                          Norman Ralph Augustine

Cover Photo – Photo by m. on Unsplash

Photo Resource – Stock Market Meme : StockMarket (reddit.com)

The problem link : Best Time to Buy and Sell Stock – LeetCode

Latest Post

• Codeforces 490A Team Olympiad Solution & Explanation2024-04-19
• Compare Strings or Characters for Equality in Java (Ignoring Case)2024-04-18
• Codeforces 1560A Dislike of Threes Solution & Explanation2024-04-15
• LeetCode #2073 Time Needed to Buy Tickets Solution & Explanation2024-04-14
• Compare strings or characters for equality in C# (ignoring case)2024-04-13