Best Time to Buy and Sell Stock - LeetCode Problem

Best Time to Buy and Sell Stock - LeetCode Problem

Welcome to another exciting blog post where we will be solving a LeetCode problem "Best Time to Buy and Sell Stock" in Python. This problem is perfect for beginners who want to practice their coding skills and learn about sliding windows technique.

Problem Description

The question asks us to find the maximum profit we can make by buying and selling a stock. We are given an array of prices where the ith element is the price of a given stock on day i.

Solution

We can solve this problem by using the sliding window technique. The idea is to keep track of the minimum price we have seen so far and the maximum profit we can make by selling the stock at the current price. We can do this by initializing two pointers, l and r, where l points to the first element of the array and r points to the second element.

We start iterating through the array from the second element using r. If the price of the stock at r is greater than the price at l, we calculate the profit we can make by selling the stock at r and buying it at l. We update the maximum profit if the current profit is greater than the previous maximum profit. If the price at r is less than the price at l, we update l to r. We keep iterating through the array until we reach the end.

Here is the Python code for the solution:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l, r = 0, 1
        max_profit = 0

        while r < len(prices):
            if prices[l] < prices[r]:
                max_profit = max(max_profit, prices[r] - prices[l])
            else:
                l = r
            r += 1
        return max_profit

Complexity Analysis

The time complexity of this solution is O(n) because we iterate through the array only once. The space complexity is O(1) because we use a constant amount of extra space.

Conclusion

In conclusion, we solved the "Best Time to Buy and Sell Stock" problem using the sliding window technique in Python. This is a great problem for beginners to practice their coding skills and learn about sliding windows. I hope you found this post helpful and happy coding! 😎