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! 😎