Sliding Window

Best Time to Buy and Sell Stock

Maximum profit from one buy followed by one later sell.

Easy

Problem

You are given an array prices where prices[i] is the price of a stock on day i. Choose one day to buy and a later day to sell to maximize profit. Return the maximum profit, or 0 if no profit is possible.

You must buy before you sell.
Only one transaction is allowed.
If no profit is possible, return 0.

Examples

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

Output: 5

Buy at 1, sell at 6.

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

Output: 0

Prices only fall, so there is no profit.

Approach

Time O(n)Space O(1)

Ask of each day: "if I sell today, what is the best day I could have bought?" - the cheapest price seen so far.
Start with minPrice = prices[0] and best = 0.
For each later day, lower minPrice if today is cheaper, then compute price - minPrice and keep the best.
The window is [day of minPrice, today]; it slides forward whenever a new low appears.

Brute force: Check every buy day against every sell day - a loop inside a loop.

Common mistakes

Tracking the global minimum and maximum separately ignores order - the maximum may come before the minimum.
Starting best at -Infinity instead of 0 returns a loss when prices only fall.

Step through it

Pick an input and play the algorithm step by step. The highlighted line in the code follows each step, and you can edit the code to experiment.

STOCK

Solution · JS

Prices · day=— min=—

70

11

52

33

64

45

profit check appears here

BESTno profitable trade yet

Day

—

Min

—

Profit

—

Best

0

Trade

—

0 / 0

Speed1×

Execution log

steps appear here…

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

LanguageEdit and run it here

JavaScript solution

Loading...

Output

Run code to see output...