buy_sell_stock_1.py

def maxProfit(self, prices: List[int]) -> int:
    # buy and then sell. 
    # sol 1:
    # time O(n) space O(1)
    if not prices: 
        return 0
    buy_price = float('inf')
    max_profit = 0
    for p in prices: # O(n)
        if buy_price < p: 
            max_profit = max(max_profit, p - buy_price) # O(1)
        else:
            buy_price = min(p, buy_price)
    return max_profit

    # sol 2:
    # time O(n * log n) space O(n)
    import heapq
    if not prices: 
        return 0
    buy_price = float('inf')
    max_profit = 0
    heap = []
    for p in prices:
        if p > buy_price:
            heapq.heappush(heap, -(p - buy_price))
        else:
            buy_price = p 
    return -heap[0] if heap else 0