Best Time to Buy and Sell Stock
Maintained by Vikas D, software engineer
You are given an array where the value at each index is the stock price on that day. You may buy once and sell once, and the sale must happen on a day after the purchase. The goal is the maximum profit achievable from a single buy-then-sell pair.
Profit for any chosen pair is the selling price minus the buying price. Because selling has to come after buying, you cannot just subtract the global minimum from the global maximum if the maximum appears before the minimum in the array.
If prices only ever fall, or every later price is at most the lowest price seen so far, there is no way to come out ahead. In that case the answer is 0, meaning the best move is to make no trade at all.
Examples
Buy at 1 (day 1) and sell at 6 (day 4) for a profit of 5. Buying earlier at 7 or later at 3 would yield less.
Prices only decline, so every later price is below every earlier one. No trade beats doing nothing, so the result is 0.
Buy at 2 and sell at 4 for a profit of 2. The later price of 1 is below the buy price, so it does not help.
Constraints
- 1 <= prices.length
- Prices are non-negative integers.
- Buy and sell must be on different days, and the sell day must come after the buy day.
- A single price (length 1) yields 0 because there is no later day to sell on.
Visible test cases
- maxProfit([7,1,5,3,6,4]) == 5
- maxProfit([7,6,4,3,1]) == 0
- maxProfit([2,4,1]) == 2
Hints
Hint 1
The buy day must come before the sell day, so think about scanning left to right and asking what is the best sale you could make if you sold today.
Hint 2
To sell well today you only need the cheapest price seen on any earlier day, not the full history.
Hint 3
Track the lowest price so far and the best profit so far as you walk the array once. Update the minimum when you see a cheaper price, otherwise check whether selling now beats your current best.
Approaches
Brute force pairs
Time O(n^2) · Space O(1)Try every valid buy day paired with every later sell day and keep the largest difference.
- Set best profit to 0.
- For each index i as the buy day, loop over every index j greater than i as the sell day.
- Compute prices[j] minus prices[i] and update best profit when it is larger.
- Return best profit, which stays 0 if no pair is profitable.
Single pass with running minimum
Time O(n) · Space O(1)Walk the array once while remembering the cheapest price seen so far; at each day the best possible sale equals the current price minus that running minimum.
- Initialize the running minimum to a very large value and best profit to 0.
- For each price, if it is below the running minimum, lower the running minimum to it.
- Otherwise compute price minus the running minimum and raise best profit if that gap is larger.
- After the pass, return best profit.
Common mistakes
- Subtracting the global minimum from the global maximum without checking order: this overcounts when the peak occurs before the trough, as in [7, 1, 5, 3, 6, 4] where the max-minus-min over the whole array is fine here but fails on inputs like [3, 1, 4] vs reversed peaks.
- Returning a negative number for an all-decreasing array instead of 0; the floor of profit is 0 because you can always choose not to trade.
- Updating the buy price after a higher price appears, which loses the cheaper earlier entry point.
- Allowing buy and sell on the same day, which would always give 0 and can mask the real answer if the logic is structured wrong.
Follow-up variations
- What if you may complete as many buy-sell transactions as you like, but only hold one share at a time?
- What if you are limited to at most two transactions across the whole period?
- What if each sale charges a fixed transaction fee, or there is a cooldown day after selling before you can buy again?
- Can you also return the actual buy and sell days, not just the profit value?