💬 Discord
Sign In
NeetCode #220LC-121EasySliding WindowBlind 75NC 150NC 250
← Back to All Problems

#220 · #121 · Best Time to Buy and Sell Stock(买卖股票的最佳时机)

📌 Problem Statement & Constraints

You are given an array prices where prices[i] is the price of a stock on day i. You want to maximise profit by choosing a single day to buy and a different later day to sell. Return the maximum profit, or 0 if no profit is possible. Constraints: 1 <= prices.length <= 10^5, 0 <= prices[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. Sweep once and maintain the minimum price seen so far.
  2. At each day, the best profit achievable by selling today is price - min_so_far.
  3. Track the maximum of those differences.
  4. This is the simplest instance of the running-minimum template and is the foundation for the whole stock series.

💻 Benchmark Python3 Implementation

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float("inf")
        best = 0
        for p in prices:
            min_price = min(min_price, p)      # best buying price so far
            best = max(best, p - min_price)    # sell today?
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): two scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Tracking the maximum price instead of the minimum: you need the cheapest prior buy, not the most expensive price.
  • Allowing a same-day buy and sell: the profit would be 0, which the best = 0 initialisation already handles, so no special case is needed.
  • Returning a negative profit: the answer is 0 when prices only fall, hence the initialisation to 0.
  • Using a nested loop: O(n^2) and unnecessary.