1. Best Time to Buy and Sell Stock (LeetCode)
Model answer
The task
Given daily stock prices, find the greatest profit possible from one buy followed by one later sale. If no sale would make money, return zero.
Key idea
As we scan the prices, keep the lowest price seen so far. Treat each current price as a possible sale and update the best profit using the difference from that minimum.
Approach
- Initialize the minimum price to a value larger than any price and the best profit to zero.
- Visit each price in order.
- Update the minimum price with the current price.
- Check the profit from selling today and update the best profit.
- Return the best profit.
class Solution:
def maxProfit(self, prices: list[int]) -> int:
min_price = float("inf")
best_profit = 0
for price in prices:
# The current price can be a new best day to buy.
min_price = min(min_price, price)
# Or it can be the day to sell after the cheapest earlier buy.
best_profit = max(best_profit, price - min_price)
return best_profit
Complexity:
- Time: O(n), where n is the number of prices; each is processed once.
- Space: O(1), since only a few variables are stored.
Common follow-ups
- What if multiple buy-and-sell transactions are allowed? Sum the gains from every adjacent price increase.
- What if a transaction fee is charged? Track the best holding and non-holding profits, incorporating the fee when selling.
- What if at most k transactions are allowed? Use dynamic programming over the number of completed transactions and whether a share is currently held.