Best Time to Buy And Sell Stock #121 [Python]

Best Time to Buy and Sell Stock LeetCode problem presents an array of stock prices, each value for stock price per day, for you and me to find a way to make maximum profit.

Solving this problem may be valuable, not just in interviews, but also in the world of stock trading, you never know 🙂

Because there, the key to success is often summarized in a simple phrase: “Buy low, sell high.”

Best Time to Buy and Sell Stock Problem

You are given an array prices where prices[i] is the price of a given stock on the ith 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.

The challenge in the best time to buy and sell stock is to maximize profit by choosing a single day to buy a stock and a different day in the future to sell that stock.

The goal is to determine the maximum profit that can be achieved from this transaction.

If it’s not possible to achieve any profit, we should return 0.

Example 1:

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6) to maximize profit: 6 - 1 = 5.

Example 2:

Input: prices = [7, 6, 4, 3, 1]
Output: 0
Explanation: In this case, no transactions are made, and the maximum profit remains at 0.

Understanding the Constraints

Before delving into the solution, let’s understand the constraints of this problem:

The length of the prices array is between 1 and 105.
The price of each stock (each element in the array) is between 0 and 10,000.

Now, let’s explore the approach to solving this problem efficiently.

Efficient Approach: Two-Pointer Technique

To solve the best time to buy and sell stock problem efficiently, we’ll utilize the two-pointer technique.

This technique involves maintaining two pointers, left and right, and systematically analyzing the prices to find the maximum profit.

Initialize two pointers, left and right, where left starts on the first day, and right starts at the second day.
Iterate through the prices array while the right pointer has not gone beyond the end of the array.
Calculate the profit by subtracting the price at the left pointer from the price at the right pointer: profit = prices[right] - prices[left].
Update the maximum profit if the calculated profit is greater than the current maximum profit.
Determine whether to update the left pointer:
- If the price at the right pointer is less than the price at the left pointer, it’s not a profitable transaction. In this case, update the left pointer to the right pointer to find a potentially lower buying price.
- If the price at the right pointer is greater than or equal to the price at the left pointer, you can keep the left pointer where it is, as you’re still buying low and potentially selling high.

Continue iterating by incrementing the right pointer.
After completing the iteration, the maximum profit will be stored in the maxProfit variable.

Here’s a Python code solution that implements this efficient approach:

View on GitHub ➹

def maxProfit(self, prices: List[int]) -> int:
    # Initialize pointers and max profit
    left = 0
    right = 1
    maxProfit = 0
    
    # Iterate through prices
    while right &lt; len(prices):
        # Calculate profit
        profit = prices[right] - prices[left]
        
        # Update max profit if necessary
        maxProfit = max(maxProfit, profit)
        
        # Check if it's a profitable transaction
        if prices[right] &lt; prices[left]:
            left = right
        
        # Move right pointer
        right += 1
    
    return maxProfit

Time and Space Complexity

Time Complexity: O(n), where n is the length of the prices array. We iterate through the array once with two pointers.
Space Complexity: O(1), as we only use a constant amount of extra space for the pointers and variables.

Reasoning Behind Our Efficient Approach

The key insight behind this efficient approach is that we want to find the maximum profit by identifying the minimum buying price (lowest value) and the maximum selling price (highest value) while traversing the array once.

By maintaining two pointers and adjusting them based on the price comparison, we can achieve this in linear time complexity.

Conclusion

In the realm of stock trading, making informed decisions to maximize profit is crucial.

LeetCode problem 121, Best Time to Buy and Sell Stock, teaches us the importance of buying low and selling high.

By utilizing the two-pointer technique, we’ve developed an efficient Python solution to find the maximum profit while considering the constraints of the problem.

Remember that in the world of finance and investment, timing is everything.

It’s not just about buying and selling stocks; it’s about making well-informed decisions at the right moment.

As you continue your journey in programming and problem-solving, you’ll find that many real-world scenarios can be tackled with creative algorithms and techniques.

You too can submit a solution to the Best Time to Buy And Sell Stock problem on LeetCode.

Feel free to comment, ask questions, make suggestions, and share your thoughts on this problem.

Happy coding!