16. Best Time to Buy and Sell Stock · DSA Practice

prices[i] is a stock price on day i. Choose one day to buy and a later day to sell. Return the maximum profit, or 0 if no profit is possible.

Example 1

Input: prices = [8,2,6,1,4]

Output: 4

Explanation: Buy at 2, sell at 6.

Example 2

Input: prices = [9,7,4,1]

Output: 0

Explanation: Prices only fall, so do not trade.

Hint 1

For each day as the selling day, the best buy is the minimum price before it.

ArraySliding Window

Approach 1: All pairs

Try every buy/sell pair.

⏱ Time O(n²)💾 Space O(1)

Approach 2: Running minimum ✅

Track the cheapest price so far and the best profit.

⏱ Time O(n)💾 Space O(1)

Reference solution for Running minimum (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        lowest, best = float('inf'), 0
        for p in prices:
            lowest = min(lowest, p)          # cheapest buy so far
            best = max(best, p - lowest)     # sell today
        return best

class Solution {
    public int maxProfit(int[] prices) {
        int lowest = Integer.MAX_VALUE, best = 0;
        for (int p : prices) {
            lowest = Math.min(lowest, p);
            best = Math.max(best, p - lowest);
        }
        return best;
    }
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int lowest = INT_MAX, best = 0;
        for (int p : prices) {
            lowest = min(lowest, p);
            best = max(best, p - lowest);
        }
        return best;
    }
};

function maxProfit(prices) {
  let lowest = Infinity, best = 0;
  for (const p of prices) {
    lowest = Math.min(lowest, p);
    best = Math.max(best, p - lowest);
  }
  return best;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Sliding Window.