Best Time to Buy And Sell Stock

The problem

You are given prices, the price of one stock on each day, in order. You may buy the stock once and sell it once on a later day. Return the largest profit you can make: the selling price minus the buying price. If no trade makes money, or there are fewer than two days, return 0.

What to write

function solve(prices: number[]): number

Input
prices = [7,1,5,3,6,4]

Output
5

Input
prices = [7,6,4,3,1]

Output
0

Constraints

0–10,000 nonnegative integer prices.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 10,000 prices. Trying every buy day with every later sell day is about 50 million pairs, so look for a way to settle each day with one look. Sorting cannot help either: it loses the order of the days, and you must buy before you sell.

2. Hint 2: Ask a smaller question

   Suppose you have decided to sell on the fifth day of 7, 1, 5, 3, 6, 4, at a price of 6. Which earlier day is the best one to have bought on? What single number about the earlier days answers that?

3. Hint 3: Name the pattern

   A trade is a stretch of days from the buy day to the sell day. Move the end forward day by day. The best start for each end is the cheapest day before it. A cheaper day can only turn up later, so the start only moves forward. Two ends that only move forward make a variable sliding window. Read the lesson on variable sliding window.

4. Hint 4: State the invariant

   When you reach a day, you hold two numbers. One is the lowest price among all the days before it. The other is the best profit of any trade that sells before it. One comparison with today's price brings each of them up to date.

5. Hint 5: Sketch the pseudocode

   low = infinity, best = 0. For each price p, in order: best = the larger of best and p - low. Then low = the smaller of low and p. Return best.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Track the cheapest earlier price and the largest sell-price difference. Initialize profit to zero to allow no trade.

The slow way

Try every pair of days: buy on the earlier one, sell on the later one, and keep the largest difference. It is correct, but n days make about n × n / 2 pairs, which is 50 million when there are 10,000 prices.

The insight

Fix the day you sell. The best day to have bought is then the cheapest day before it, and nothing else about the past matters. As the sell day moves forward, that cheapest day can only move forward too. The two days are the ends of a window that slides over the prices, and all you carry along is the lowest price so far.

Step by step

1. Remember the lowest price so far and the best profit so far. No day has been read yet, so the lowest price starts at infinity and the first day cannot look like a sale. The best profit starts at 0, which is what making no trade earns.
2. Work out what selling today earns, and keep the best profit. The best partner for a sale today is the lowest earlier price, so one subtraction covers every possible buy day at once. The result replaces the best profit only if it is larger.
3. Today's price becomes the lowest if it is cheaper. From tomorrow on, today is one of the earlier days. So today's price joins the comparison now, or a later sale could miss the cheapest day to buy.
4. Return the best profit, which is 0 when no trade pays. Every day was tried as the day to sell, against the best day to buy for it. If the prices only fall, no difference ever beats the starting 0.

The same numbered steps are the comments in each solution.

function solve(prices) {
  // 1. Remember the lowest price so far and the best profit so far
  let low = Infinity,
    best = 0;
  for (const p of prices) {
    // 2. Work out what selling today earns, and keep the best profit
    best = Math.max(best, p - low);
    // 3. Today's price becomes the lowest if it is cheaper
    low = Math.min(low, p);
  }
  // 4. Return the best profit, which is 0 when no trade pays
  return best;
}

function solve(prices: number[]): number {
  // 1. Remember the lowest price so far and the best profit so far
  let low = Infinity,
    best = 0;
  for (const p of prices) {
    // 2. Work out what selling today earns, and keep the best profit
    best = Math.max(best, p - low);
    // 3. Today's price becomes the lowest if it is cheaper
    low = Math.min(low, p);
  }
  // 4. Return the best profit, which is 0 when no trade pays
  return best;
}

def solve(prices):
    # 1. Remember the lowest price so far and the best profit so far
    low = float("inf")
    best = 0
    for price in prices:
        # 2. Work out what selling today earns, and keep the best profit
        best = max(best, price - low)
        # 3. Today's price becomes the lowest if it is cheaper
        low = min(low, price)
    # 4. Return the best profit, which is 0 when no trade pays
    return best

Example 1, traced

Input
prices = [7,1,5,3,6,4]

Output
5

Why it works

Take the best possible trade. It sells on some day. When the loop reaches that day, the lowest earlier price is no higher than the price that trade bought at. So the profit computed there is at least as large. No profit is invented either: every difference that beats the best profit is one day's price minus the price of a real earlier day.

Time and space

Time O(n), extra space O(1). The loop makes one pass over the n prices and does two comparisons for each, so the time is O(n). Whatever the length of the list, it stores two numbers, the lowest price and the best profit: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not subtract the lowest price in the list from the highest. In example 1 that gives 7 - 1 = 6, but the 7 comes before the 1, and you cannot sell before you buy.
• Start the best profit at 0, not at the first difference you compute. When prices only fall, as in example 2, every trade loses money and the right answer is to make no trade.
• Do not fix the buy day at the lowest price of the whole list. In 3, 8, 1, 2 that buys at 1 and earns 1 at most, while buying at 3 and selling at 8 earns 5.

Pattern

Variable sliding window.

Keep going