Interview challenge · easy · array, greedy, sliding-window
Best Time to Buy and Sell Stock
The challenge
You are given an array prices where prices[i] is the price of a stock on day i. Choose one day to buy and a later day to sell. Return the maximum profit you can achieve, or 0 if no profit is possible.
Example
[7, 1, 5, 3, 6, 4] -> 5 (buy at 1, sell at 6)
[7, 6, 4, 3, 1] -> 0 (prices only go down)Idea: walk the prices once, remembering the lowest price seen so far. The best sale today is price - lowest; keep the maximum. Time O(n), space O(1).
The solution
# Buy and Sell Stock - ayotl.dev
def max_profit(prices):
low = float("inf") # cheapest so far
best = 0
for p in prices:
low = min(low, p)
# best sale today: buy at the low
best = max(best, p - low)
return best
print(max_profit([7, 1, 5, 3, 6, 4]))
print(max_profit([7, 6, 4, 3, 1]))
$ python3 best_time_to_buy_and_sell_stock.py
5
0