âš¡ TL;DR
Solve Best Time to Buy and Sell Stock in Python with working code. One-Pass Min Tracking (Optimal) approach with O(n) time, plus complexity analysis and interview tips.
Best Time to Buy and Sell Stock (#121 — Easy): Given an array prices where prices[i] is the price of a stock on day i, choose one day to buy and a different later day to sell to maximize profit. Return that maximum profit, or 0 when no profitable trade exists.
Problem Statement
Given an array prices where prices[i] is the price of a stock on day i, choose one day to buy and a different later day to sell to maximize profit. Return that maximum profit, or 0 when no profitable trade exists.
Example:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1), sell on day 5 (price = 6), profit = 6 − 1 = 5.Approach: One-Pass Min Tracking (Optimal)
Time: O(n) | Space: O(1)
Walk the prices once while remembering the cheapest price seen so far. At each day the best possible trade selling today is today’s price minus that minimum, so update the answer on the fly.
def max_profit(prices):
min_price = prices[0]
best = 0
for price in prices[1:]:
if price < min_price:
min_price = price
elif price - min_price > best:
best = price - min_price
return best
print(max_profit([7, 1, 5, 3, 6, 4]))Approach: Brute Force
Time: O(n²) | Space: O(1)
Try every buy-day/sell-day pair, keep the largest positive difference, and return it. Straightforward but quadratic, which fails on large inputs.
def max_profit_brute(prices):
best = 0
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
if prices[j] - prices[i] > best:
best = prices[j] - prices[i]
return best
print(max_profit_brute([7, 1, 5, 3, 6, 4]))Key Takeaways
- Start with the brute-force approach to understand the problem
- One-Pass Min Tracking (Optimal) gives the optimal O(n) solution
- Practice this pattern — it appears frequently in coding interviews
FAQ
What is the best approach to solve Best Time to Buy and Sell Stock in Python?
The recommended approach is One-Pass Min Tracking (Optimal), which runs in O(n) time with O(1) space. The full Python implementation is shown above.
What is the time complexity of Best Time to Buy and Sell Stock in Python?
Using One-Pass Min Tracking (Optimal), the time complexity is O(n) and the space complexity is O(1).
Happy coding!
