Best Time to Buy and Sell Stock

The problem

You are given an array prices of numbers (call its length n). prices[i] is the price of one share on day i.

You may buy one share on one day and sell it on a later day. Return the largest profit you can make. If no trade makes money, return 0, because you can simply not trade.

Example 1

Input: prices = [6, 2, 7, 1, 5, 3]

Output: 5

Buy on day 1 at 2 and sell on day 2 at 7. The profit is 7 − 2 = 5. Buying at 1 later only reaches 5 − 1 = 4.

price by day

Example 2

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

Output: 0

The price only falls. Every trade loses money, so the best choice is not to trade.

Example 3

Input: prices = [3, 8]

Output: 5

Buy on day 0 and sell on day 1.

Constraints

• 1 ≤ n ≤ 100,000
• 0 ≤ prices[i] ≤ 10,000

Clarifying questions

How many trades are allowed?

One buy and one sell. Not several.

Can I sell before I buy?

No. The sell day must come after the buy day.

What if every trade loses money?

Return 0. Not trading is always allowed.

Can I buy and sell on the same day?

That makes 0 profit, which is the same as not trading. It never changes the answer.

Spot the pattern

For a fixed sell day, the best buy day is simply the cheapest day before it. So as we walk the days in order, one number, the lowest price so far, tells us the best trade ending today. It is like a window whose left edge jumps to each new low and whose right edge is today.

Solutions

Brute forceO(n²)One passO(n)

Show all

This problem has two approaches. There is no useful step between them.

Brute force O(n²)

The idea

Try every buy day i with every later sell day j. The profit is prices[j] − prices[i]. Keep the largest. Start the best at 0, so a falling price gives 0 instead of a loss.

It is clearly correct, but there are about n × n / 2 pairs of days.

Walkthrough

price by day

best

0

1. best = 0
2. for i in range(len(prices)):
3. for j in range(i + 1, len(prices)):
4. best = max(best, prices[j] - prices[i])
5. return best

Try every buy day i with every later sell day j. Keep the biggest profit. Profit starts at 0: not trading is allowed.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: try every buy day with every later sell day.
    // About n * n / 2 pairs, so O(n^2) time and O(1) memory.
    public int maxProfit(int[] prices) {
        int pricesLength = prices.length;
        // 0 means "do not trade", which is always allowed.
        int best = 0;
        for (int i = 0; i < pricesLength; i++) {
            // Selling must come after buying, so j starts after i.
            for (int j = i + 1; j < pricesLength; j++) best = Math.max(best, prices[j] - prices[i]);
        }
        return best;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line works out one profit and keeps the larger. It sits inside two loops. One subtract and one max do not grow with n, so each run is 1 step.

   1. best = 0
   2. for i in range(len(prices)):
   3. for j in range(i + 1, len(prices)):
   4. best = max(best, prices[j] - prices[i])
   5. return best

2. 2 Count the runs on Example 1

   Example 1 has 6 days. Buy day 0 has 5 later days to sell on, day 1 has 4, and so on down to day 4, which has 1. Day 5 has none.

   5 + 4 + 3 + 2 + 1 = 15 runs.

   buy day i	0	1	2	3	4	5
   sell days tried	5	4	3	2	1	0

   total

   5 + 4 + 3 + 2 + 1 = 15

3. 3 Write the count for any n

   (n − 1) + (n − 2) + … + 1 = n × (n − 1) / 2 = ½n² − ½n

   Check it with Example 1: 6 × 5 / 2 = 15.

4. 4 Keep only the part that grows fastest

   • Drop the −½n. Next to ½n² it soon stops mattering.
   • Drop the ½. It does not change how fast the count grows.

   What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code keeps best, i and j. That is 3 numbers for any n, so the space is O(1).

   bestij

One pass O(n)

The idea

Pick any sell day. The best day to have bought is the cheapest day before it. So walk the days in order and remember just one number: low, the lowest price so far.

On each day, first ask: if I sell today, what is the profit? That is price − low. Keep the best. Then, if today’s price is a new low, update low, so later days can buy here.

Why it never misses the answer: the best trade sells on some day j. When the loop reaches j, low is the cheapest price before j, so the profit it checks is the best possible for that day.

Walkthrough

price by day

low

6

best

0

1. low = prices[0]
2. best = 0
3. for i in range(1, len(prices)):
4. best = max(best, prices[i] - low)
5. low = min(low, prices[i])
6. return best

Day 0: the lowest price so far is 6. Nothing has been sold yet, so best = 0.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // One pass: the best sale today buys at the lowest price seen before today.
    // One loop, so O(n) time. Two numbers, so O(1) memory.
    public int maxProfit(int[] prices) {
        int low = prices[0];
        // 0 means "do not trade", which is always allowed.
        int best = 0;
        for (int i = 1; i < prices.length; i++) {
            // Sell today: the cheapest earlier day is the best day to have bought.
            best = Math.max(best, prices[i] - low);
            // Update low after selling, so we never buy and sell on the same day.
            low = Math.min(low, prices[i]);
        }
        return best;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Each run of the loop does one subtract, one max and one min. That is a fixed amount of work, so each run is 1 step. There is one loop.

   1. low = prices[0]
   2. best = 0
   3. for i in range(1, len(prices)):
   4. best = max(best, prices[i] - low)
   5. low = min(low, prices[i])
   6. return best

2. 2 Count the runs on Example 1

   Example 1 has 6 days. The loop starts on day 1, because day 0 has nothing before it to buy from. So it runs for days 1 to 5. The table shows each run.

   5 runs.

   day	1	2	3	4	5
   price	2	7	1	5	3
   low before	6	2	2	1	1
   profit	-4	5	-1	4	2

3. 3 Write the count for any n

   n − 1 times

   Check it with Example 1: 6 − 1 = 5.

4. 4 Keep only the part that grows fastest

   Drop the − 1. One run more or less does not change how the work grows. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps low, best and i. That is 3 numbers for any n, so the space is O(1).

   lowbesti

Common mistake

Subtracting the lowest price from the highest

The highest price may come before the lowest one. In [6, 2, 7, 1, 5, 3] the max is 7 and the min is 1, but 1 comes after 7, so 7 − 1 = 6 is not a real trade. The buy must come before the sell.

Tested at the limits

2,000 random price lists of 1 to 10 days, prices 0 to 8, so flat days, falling runs and single days are common. The brute force and the one pass gave the same answer every time.

Largest inputs	Result
100,000 prices (the most allowed) in a V shape: down from 10,000 to 0, then back up. The best day to buy is in the middle. One pass.	0.01 s, and under 0.001 MB of extra memory: just two variables.
2,000 prices, a smaller V. Brute force, about 2 million pairs.	0.09 s. At 100,000 prices it would check 5 billion pairs, which is why the one pass matters.