Best Time to Buy and Sell Stock

Easy Dynamic Programming State Machine DP - Stock Problems Original on LeetCode

Best Time to Buy and Sell Stock is a easy dynamic programming problem solved with the state machine dp - stock problems pattern. The best approach, optimal (track the minimum so far), runs in O(n) time and O(1) space. Below are 2 approaches in Java, from brute force up.

Problem

You know a stock’s price on each day. Choose one day to buy and a later day to sell to maximise profit. Return the maximum profit, or 0 if no profit is possible.

Examples

Example 1

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Why: Buy at 1, sell at 6.

Example 2

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

Constraints

1 <= prices.length <= 10^5.
One buy and one later sell at most.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Brute force	`O(n²)`	`O(1)`
Optimal (track the minimum so far)	`O(n)`	`O(1)`

1Brute force

TimeO(n²)

SpaceO(1)

Try every pair of buy day i and sell day j > i.

best = max(prices[j] - prices[i]).

Java

class Solution {
    public int maxProfit(int[] prices) {
        int best = 0;
        for (int i = 0; i < prices.length; i++)
            for (int j = i + 1; j < prices.length; j++) best = Math.max(best, prices[j] - prices[i]);
        return best;
    }
}

2Optimal (track the minimum so far)

TimeO(n)

SpaceO(1)

Scan once. Keep the lowest price seen so far and, for each day, the profit from selling today. This is the one-transaction version of the stock state machine (states: not holding, holding).

min = prices[0].
best = max(best, price - min); min = min(min, price).

Java

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

Edge cases to test

Prices only fall (answer 0)
One day

Hints

Hint 1

For each day as the selling day, the best buying day is the cheapest day before it.

FAQ

What is the best time complexity for Best Time to Buy and Sell Stock?

Optimal (track the minimum so far) runs in O(n) time and O(1) extra space.

Which pattern does Best Time to Buy and Sell Stock use?

It is a dynamic programming problem that uses the state machine dp - stock problems pattern. Other problems with the same pattern: Best Time to Buy and Sell Stock II, Best Time to Buy and Sell Stock with Transaction Fee, Best Time to Buy and Sell Stock with Cooldown.

Is there a brute force solution for Best Time to Buy and Sell Stock?

Yes. Brute force takes O(n²) time and O(1) space. Try every pair of buy day i and sell day j i.

Which edge cases should I test for Best Time to Buy and Sell Stock?

Prices only fall (answer 0); One day.