Best Time to Buy and Sell Stock

• Difficulty: Easy
• Primary pattern: Dynamic Programming
• Tags: Array, Dynamic Programming
• Time taken: 09:09
• LeetCode Link

Key Idea

• You can only move forward
• You do NOT need to report indices
• You are finding the best “difference” between the values you read
• For every possible selling day, what is the cheapest price I could have bought at BEFORE today?

Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Understanding:
            # Iterate and find maximal difference
            # Array is irregular
            # You can only go forward, meaning you have to finding earnings forward
            # Read the question carefully you do NOT need to report the index, only MAXIMIZED earning
        # Track lowest prices so far
        lowest = prices[0]
        # Earnings
        earnings = 0

        # Iterate
        for price in prices:
            # If the current price beats the lowest you saw
            if price < lowest:
                # Update the lowest price
                lowest = price
            # If current price does NOT beat
            else:
                # find the maximum earnings comparing to previous earnings
                earnings = max(earnings, price - lowest)
        return earnings

Complexity

• Time: O(n)
• Space: O(1)