Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Brute Force

A straightforward approach is to try every possible pair of days.

1. Pick a day i to buy.
2. For every later day j, calculate the profit prices[j] - prices[i].
3. Keep track of the largest profit seen.

There are about n²/2 pairs of days, so this is slow. With up to 10^5 prices, it can exceed the time limit.

Time: O(n²)

Space: O(1)

We can improve this by noticing that we don't need to check every buy day for every sell day.

Optimal Approach: Track the Lowest Price So Far

Think about it from the selling side.

If we decide to sell on a certain day, which day should we have bought on? Obviously, the day with the lowest price before it.

So we scan the prices once from left to right and keep two variables:

• minPrice: the lowest price seen so far, which is the best day to buy up to now.
• maxProfit: the best profit found so far.

For each day:

1. Update minPrice if today's price is lower.
2. Calculate the profit if we sell today: price - minPrice.
3. Update maxProfit if this profit is larger.

Code

class Solution {
    public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;

        for (int price : prices) {
            minPrice = min(minPrice, price);
            maxProfit = max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }
};

Dry Run

For prices = [7,1,5,3,6,4]:

1day   price   minPrice   sell today   maxProfit
2 1      7        7       7 - 7 = 0        0
3 2      1        1       1 - 1 = 0        0
4 3      5        1       5 - 1 = 4        4
5 4      3        1       3 - 1 = 2        4
6 5      6        1       6 - 1 = 5        5
7 6      4        1       4 - 1 = 3        5

The best profit is 5: buy at price 1 on day 2, sell at price 6 on day 5.

Why Does This Work?

Every possible transaction has a sell day.

For a fixed sell day, the best buy day is always the cheapest day before it. minPrice holds exactly that value at every step.

So when we compute price - minPrice, we are calculating the best possible profit for selling on that day. Checking this for every day covers every possible sell day, so the largest of these values is the answer.

The brute force checks every buy day for each sell day. We only need the cheapest one, and we keep it updated as we go.

Complexity

How to Explain It in an Interview