0121.Best Time to Buy and Sell Stock

• Link: 121. Best Time to Buy and Sell Stock - Easy
• Track: NeetCode150

Question

Restate the problem

• Given an array, where prices[i] is the stock price on dayi
• Choose one day to buy and a later day to sell to maximize profit.
• Return the maximum profit, return 0 if no profitable transition exists.

Edge Case

• If prices are decreasing, return 0

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Greedy	$O(n)$	$O(1)$
Method 2	Two Pointers	$O(n)$	$O(1)$

Method 1 - Greedy

Key idea: Keep the minimum price so far; at each day, treat today as the sell day and update the best profit.

Approach

• Invariant: min_price is always the minimum of all prices seen so far.
• max_profit is always the best achievable profit up to the current day
• Iterate through each price:
  • Update min_price
  • Compute profit if selling today and update max_profit

Complexity

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

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_buy = float("inf")
        max_profit = 0
        for p in prices:
            min_buy = min(min_buy, p)
            max_profit = max(max_profit, p - min_buy)
        
        return max_profit

Method 2 - Two Pointers

Approach

• Use two pointers:
  • left = buy day (the lowest price in the current window)
  • right = sell day (moves forward to scan prices)
• Initialize left = 0, right = 1, profit = 0
• While right < n:
  • If prices[right] > prices[left], selling on right is profitable:
    • update profit = max(profit, prices[right] - prices[left])
  • Otherwise, prices[right] is a better (lower) buy price:
    • move left = right to start a new window
  • Move right += 1
• Return profit (remains 0 if no profitable trade exists)

Complexity

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

Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        left = 0    # buy
        right = 1   # sell
        profit = 0
        while right < len(prices):
            if prices[right] > prices[left]:
                profit = max(profit, prices[right] - prices[left])
            else:
                left = right
            right += 1
        
        return profit

---

Mistake