What is the brute force approach and complexity for Best Time to Buy and Sell Stock?

Check every pair of days i < j and keep the best profit with time complexity O(N^2) and space complexity O(1).

What is the optimal approach and complexity for Best Time to Buy and Sell Stock?

Walk once; keep the lowest price seen; profit today = price − lowest with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Best Time to Buy and Sell Stock?

Look for key signals in the prompt: "buy one share and sell it later" indicates One buy, then one sell, and the sell must come after the buy: the order of the days matters.; "largest profit" indicates One sale's profit is today's price minus the cheapest earlier price, so it can be tracked in O(1) per day.; "return 0 if no profit" indicates Starting best at 0 handles falling prices without a special case..

Best Time to Buy and Sell Stock

Q: What is the optimal approach and complexity for Best Time to Buy and Sell Stock?

Walk once; keep the lowest price seen; profit today = price − lowest with optimal time complexity O(N) and space complexity O(1).

Q: How do you identify the pattern for Best Time to Buy and Sell Stock?

Look for key signals in the prompt: "buy one share and sell it later" indicates One buy, then one sell, and the sell must come after the buy: the order of the days matters.; "largest profit" indicates One sale's profit is today's price minus the cheapest earlier price, so it can be tracked in O(1) per day.; "return 0 if no profit" indicates Starting best at 0 handles falling prices without a special case..

Easy·LeetCode #121Basic Anchor

LeetCode

Jump:

30-Second Mental ModelKadane / Subarray — running minimum (Stock buy / sell, Basic Anchor)

Complexity:O(N^2)→O(N)

Key Insight

Walk the days once and keep the cheapest price so far. For each day, selling there at the cheapest earlier price is the best sale that day. Keep the largest such profit.

Core Validity Invariant

A sale is valid only when the buy came before the sale, so minPrice is taken only from earlier days. That is why the sale check runs before today's price joins the minimum.

Problem

You are given prices, where 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. You get one trade only.

Return the largest profit you can make. If no profit is possible, return 0, because doing nothing is allowed.

Input

An integer array prices.

Output

The largest profit from one buy and one later sell, or 0 if no profit is possible.

Example 1

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

Output: 5

Buy at price 1 (index 1) and sell at price 6 (index 4). The profit is 6 − 1 = 5. Buying at 7 (index 0) never helps, because every later price is lower.

Example 2

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

Output: 0

The price only falls, so every sale would lose money. Doing nothing gives 0.

Constraints

• 1 ≤ prices.length ≤ 10^5
• 0 ≤ prices[i] ≤ 10^4

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Can I sell on a day before I bought? What does the order of the days change?
2.
If I know the cheapest price up to day 4, what else do I need to find the best sale on day 4?
3.
Do I need to compare every pair of days, or can I remember one number from the past?
4.
What should the answer be when the prices only go down?
5.
How is this different from subtracting the smallest price in the array from the largest one?

Brute force approach

Idea

Buy on day i and sell on any later day j. Try every such pair and keep the largest prices[j] − prices[i]. If no pair makes money, the answer stays 0.

Thinking process

1
The buy must come before the sell, so a pair is (i, j) with i < j. No other pairs are allowed.
2
For one pair the profit is prices[j] − prices[i]. Buy at index 1 (price 1) and sell at index 4 (price 6): 6 − 1 = 5.
3
Some pairs lose money. Every pair that starts at index 0 (price 7) is negative, for example 1 − 7 = −6.
4
Check every pair, keep the largest result, and start that result at 0 because doing nothing is allowed.

Visual

Blue (info) = the buy day i and sell day j of the pair being checked. Purple (best) = the best pair found so far.

Brute force checks every pairprices = [7, 1, 5, 3, 6, 4]step 1/16

prices

▲buy

▲sell

Work

pairs checked: 1
buy i: 7 (day 0)
sell j: 1 (day 1)
profit: -6
best: 0

1 − 7 = -6 → not better

Pair (buy day 0, sell day 1): profit -6. Every pair is looked at on its own, even when the same buy day was just used.

Code & Implementation

brute.cpp

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int best = 0;   // doing nothing is allowed, so the answer is never below 0

        // Try every buy day i and every later sell day j.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                best = max(best, prices[j] - prices[i]);
            }
        }
        return best;
    }
};

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int best = 0; // doing nothing is allowed, so the answer is never below 0

        // Try every buy day i and every later sell day j.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                best = Math.max(best, prices[j] - prices[i]);
            }
        }
        return best;
    }
}

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        n = len(prices)
        best = 0  # doing nothing is allowed, so the answer is never below 0

        # Try every buy day i and every later sell day j.
        for i in range(n):
            for j in range(i + 1, n):
                best = max(best, prices[j] - prices[i])

        return best

export function maxProfit(prices: number[]): number {
    const n = prices.length;
    let best = 0; // doing nothing is allowed, so the answer is never below 0

    // Try every buy day i and every later sell day j.
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            best = Math.max(best, prices[j] - prices[i]);
        }
    }
    return best;
}

Complexity

Time O(N^2)Space O(1)

Every pair (i, j) with i < j is checked once, which is about N²/2 pairs. For N = 10^5 that is about 5·10^9 checks, too slow.

Optimized approach

Idea

Walk the days once and keep the cheapest price so far. For each day, selling there at the cheapest earlier price is the best sale that day. Keep the largest such profit.

Start from brute force

Brute force tries every buy day for every sell day. Most of those pairs can be skipped, because for one sell day only the cheapest earlier price matters.

Find the repeated work

For each sell day j, brute force searches all the earlier days again to find the cheapest one. Each search differs from the last by a single new price, so one running number replaces all of them.

Define the state — what variables do I need?

minPrice: The cheapest price on the days before today. It is the best buy for a sale today.
best: The largest profit found so far. It starts at 0, which means no trade.

Define validity

A sale is valid only when the buy came before the sale, so minPrice is taken only from earlier days. That is why the sale check runs before today's price joins the minimum.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

minPrice = prices[0]; best = 0;

Day 0 can only be a buy. No sale is possible yet, so the best profit is 0.

Each day i from 1 to n − 1: the sale check

best = max(best, prices[i] − minPrice)

Selling today at the cheapest earlier price is the best sale on day i. Keeping the maximum covers every sale day.

Right after the check

minPrice = min(minPrice, prices[i])

Today's price can be the buy for later days. It is updated after the check, so we never buy and sell on the same day.

What does the current window add to the answer?

Each day adds one candidate: the best sale on that day. After the loop, best holds the largest candidate over all sale days.

Code & Implementation

optimal.cpp

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = prices[0];   // cheapest price on any day so far (the best buy)
        int best = 0;               // largest profit so far

        for (int i = 1; i < (int)prices.size(); i++) {
            // Sell today, buying at the cheapest earlier price.
            best = max(best, prices[i] - minPrice);
            // Only after the check: today's price can be a buy day for later sales,
            // and we never buy and sell on the same day.
            minPrice = min(minPrice, prices[i]);
        }
        return best;
    }
};

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;

        int minPrice = prices[0]; // cheapest price on any day so far (the best buy)
        int best = 0;             // largest profit so far

        for (int i = 1; i < prices.length; i++) {
            // Sell today, buying at the cheapest earlier price.
            best = Math.max(best, prices[i] - minPrice);
            // Only after the check: today's price can be a buy day for later sales,
            // and we never buy and sell on the same day.
            minPrice = Math.min(minPrice, prices[i]);
        }
        return best;
    }
}

class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        if not prices:
            return 0

        min_price = prices[0]  # cheapest price on any day so far (the best buy)
        best = 0               # largest profit so far

        for p in prices[1:]:
            # Sell today, buying at the cheapest earlier price.
            best = max(best, p - min_price)
            # Only after the check: today's price can be a buy day for later sales,
            # and we never buy and sell on the same day.
            min_price = min(min_price, p)

        return best

export function maxProfit(prices: number[]): number {
    if (prices.length === 0) return 0;

    let minPrice = prices[0]; // cheapest price on any day so far (the best buy)
    let best = 0;             // largest profit so far

    for (let i = 1; i < prices.length; i++) {
        // Sell today, buying at the cheapest earlier price.
        best = Math.max(best, prices[i] - minPrice);
        // Only after the check: today's price can be a buy day for later sales,
        // and we never buy and sell on the same day.
        minPrice = Math.min(minPrice, prices[i]);
    }
    return best;
}

Complexity

Time O(N)Space O(1)

One pass over the array. Only two numbers are kept: the cheapest price and the best profit.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Check every pair of days i < j and keep the best profit	O(N^2)	O(1)
Optimal	Walk once; keep the lowest price seen; profit today = price − lowest	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“buy one share and sell it later”One buy, then one sell, and the sell must come after the buy: the order of the days matters.
“largest profit”One sale's profit is today's price minus the cheapest earlier price, so it can be tracked in O(1) per day.
“return 0 if no profit”Starting best at 0 handles falling prices without a special case.

one buy before one sell+profit = sell price − buy price+buy price = cheapest earlier price→Kadane / Subarray — running minimum (Stock buy / sell, Basic Anchor)

This is the anchor of the Stock buy / sell sub-pattern. The sell day decides the profit, and for a fixed sell day the best buy is the lowest price before it, so one running minimum is enough. The rule here allows only one trade, so there is one minimum and one maximum. The next two questions keep the same walk but change the rule: many trades (LC 122), then a cooldown after each sale (LC 309).

Don't make this mistake

Pattern confusion: max minus min ignores the order of the days

✗ return *max_element(prices.begin(), prices.end()) - *min_element(prices.begin(), prices.end());

✓ int minPrice = prices[0], best = 0; // then walk the days, as in the optimal

On [7, 1, 5, 3, 6, 4], the biggest price is 7 (day 0) and the smallest is 1 (day 1). 7 − 1 = 6 would sell on day 0 before buying on day 1, which is not allowed. The real answer is 5 (buy at 1, sell at 6). On [5, 9, 1, 3] it gives 9 − 1 = 8, but the 9 comes before the 1. The real answer is 4 (buy at 5, sell at 9).

Starting best at the first price change

✗ int best = prices[1] - prices[0];

✓ int best = 0;

On [7, 6, 4, 3, 1] the first change is 6 − 7 = −1, so this returns −1. Doing nothing is allowed, so the answer must be 0.

Comparing each day only with the day before

✗ best = max(best, prices[i] - prices[i - 1]);

✓ best = max(best, prices[i] - minPrice);

On [7, 1, 5, 3, 6, 4] the largest single-day change is 4 (from 1 to 5), so this returns 4. The real answer is 5, which buys at 1 and sells at 6, two days apart. A profit can span many days, so compare with the cheapest earlier price, not just yesterday.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Kadane / Subarray translate into production architectures and low-level memory mechanics.

LLD Architecture