Sliding Window: Best Time to Buy and Sell Stock - Leetcode 121 - Python

Tutorial: Finding the Best Time to Buy and Sell Stock using Two Pointers Technique

Step 1: Understanding the Problem

• The goal is to find the best time to buy and sell a stock to maximize profit.
• We are given an array where each element represents the price of the stock on a particular day.
• We can only perform one transaction (buy on one day and sell on another day).

Step 2: Implementing the Two Pointers Technique

1. Initialize two pointers, left and right, where left starts at day 0 and right starts at day 1.
2. Set the max_profit variable to 0 as the default maximum profit.
3. Iterate through the prices array while the right pointer has not passed the end of the prices array.
4. Check if the price at left is less than the price at right:
   • Calculate the profit as prices[right] - prices[left].
   • Update max_profit to the maximum of the current max_profit and the profit calculated.
5. Update the pointers:
   • If the left price is not less than the right price, shift the left pointer to the right to find a lower price.
   • Always update the right pointer.
6. Continue this process until the right pointer reaches the end of the array.

Step 3: Implementing the Solution in Python

def maxProfit(prices):
    left = 0
    right = 1
    max_profit = 0
    
    while right < len(prices):
        if prices[left] < prices[right]:
            profit = prices[right] - prices[left]
            max_profit = max(max_profit, profit)
        else:
            left = right  # Shift left pointer to find a lower price
        
        right += 1  # Always update right pointer
    
    return max_profit

Step 4: Testing the Solution

• Create a list of stock prices to test the maxProfit function.
• Call the function with the list of prices and print the result.

prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices))  # Output: 5

Step 5: Analysis of the Solution

• The two pointers technique helps in efficiently finding the best time to buy and sell the stock.
• The solution has a time complexity of O(n) and uses constant extra space (O(1)).
• The algorithm iterates through the prices array once to find the maximum profit.

By following these steps, you can implement a Python function to determine the best time to buy and sell stock to maximize profit using the two pointers technique.