SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Best Time to Buy and Sell Stock Visualizer

Walk the days once. Remember the cheapest price seen so far; selling today earns today minus that price. Keep the best earning.

Start the Best Time to Buy and Sell Stock simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Day 0 costs 7. That is the cheapest so far, and the best profit is 0. [7, 1, 5, 3, 6, 4, 8, 2]
  2. 1 is cheaper than anything before. Buying here would be better.
  3. Sell today: 1 − 1 = 0, not better than 0.
  4. 5 is not cheaper than 1. Keep the old buy day.
  5. Sell today: 5 − 1 = 4. New best profit.
  6. 3 is not cheaper than 1. Keep the old buy day.
  7. Sell today: 3 − 1 = 2, not better than 4.
  8. 6 is not cheaper than 1. Keep the old buy day.
  9. Sell today: 6 − 1 = 5. New best profit.
  10. 4 is not cheaper than 1. Keep the old buy day.
  11. Sell today: 4 − 1 = 3, not better than 5.
  12. 8 is not cheaper than 1. Keep the old buy day.
  13. Sell today: 8 − 1 = 7. New best profit.
  14. 2 is not cheaper than 1. Keep the old buy day.
  15. Sell today: 2 − 1 = 1, not better than 7.
  16. Done. Buy on day 1 at 1, sell on day 6 at 8: profit 7.

Try it with your own input →

Best time to buy and sell stock in Java, Python, C++, C and JavaScript

int maxProfit(int[] p) {
  int minPrice = p[0], best = 0;
  for (int i = 1; i < p.length; i++) {
    minPrice = Math.min(minPrice, p[i]);
    best = Math.max(best, p[i] - minPrice);
  }
  return best;
}
def max_profit(p):
    min_price, best = p[0], 0
    for i in range(1, len(p)):
        min_price = min(min_price, p[i])
        best = max(best, p[i] - min_price)
    return best
int maxProfit(const vector<int>& p) {
  int minPrice = p[0], best = 0;
  for (int i = 1; i < (int)p.size(); i++) {
    minPrice = min(minPrice, p[i]);
    best = max(best, p[i] - minPrice);
  }
  return best;
}
int maxProfit(int p[], int n) {
  int minPrice = p[0], best = 0;
  for (int i = 1; i < n; i++) {
    if (p[i] < minPrice) minPrice = p[i];
    if (p[i] - minPrice > best) best = p[i] - minPrice;
  }
  return best;
}
function maxProfit(p) {
  let minPrice = p[0], best = 0;
  for (let i = 1; i < p.length; i++) {
    minPrice = Math.min(minPrice, p[i]);
    best = Math.max(best, p[i] - minPrice);
  }
  return best;
}

In an interview

LeetCode 121, Best Time to Buy and Sell Stock: buy on one day, sell on a later day, and make the most profit.

You never need to know the buy day in advance: the cheapest day so far is always the best day to have bought. If prices only fall, the answer is 0.

More patterns