Best Time to Buy and Sell Stock

1. Problem & Core Objective

The problem

You are given an array prices where prices[i] is the price of a stock on day i.

You want to maximize profit by choosing one day to buy and a different, later day to sell. Return the maximum profit achievable, or 0 if no profit is possible.

Input:  prices = [7,1,5,3,6,4]      Output: 5      (buy at 1 on day 1, sell at 6 on day 4)
Input:  prices = [7,6,4,3,1]        Output: 0      (prices only fall — don't trade)

Constraints:

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

What the interviewer is actually testing

This is the gentlest problem in the section, and it's placed here deliberately: it's a sliding window in disguise, and recognizing that is more valuable than solving it.

1. Do you spot the ordering constraint? You must buy before you sell. That single direction is what makes a one-pass solution possible and what a careless max - min gets wrong.
2. Can you reduce it to one running value? The entire history compresses to "the cheapest price seen so far" — nothing else from the past matters.
3. Do you handle "no profit" correctly? A strictly falling market returns 0, not a negative number.
4. Can you connect it to Kadane's algorithm? Profit over day-to-day differences is Maximum Subarray. Seeing that link is the senior-level observation.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 10^5.

• O(n²) → 10^10. Too slow.
• O(n log n) → fine, but nothing here suggests sorting (and sorting would destroy the day ordering, which is the whole constraint).
• O(n) → the target.

Step 2 — State what the brute force does, and find the waste

for (int buy = 0; buy < n; buy++)
    for (int sell = buy + 1; sell < n; sell++)
        best = Math.max(best, prices[sell] - prices[buy]);

O(n²). Now the diagnostic question: what does the inner loop actually need from the outer one?

For a fixed sell day, the best profit is prices[sell] − (the cheapest price before it). The inner loop is re-deriving that minimum from scratch every time.

Step 3 — The reframe

Flip the iteration. Instead of "for each buy day, try every sell day", ask once per day:

"If I sold today, what's the best I could do?"

The answer is today's price − the minimum price seen so far. And "the minimum so far" is a running value updated in O(1).

So one pass, tracking one number.

Step 4 — Why this is a sliding window

It doesn't look like one, so it's worth making explicit:

• right is today (the potential sell day) and advances every step.
• left is the buy day — and it jumps forward to right whenever a new lower price appears, because any earlier buy day is now strictly worse.
• The "summary" of the window is a single value: the minimum price inside it.

That's the degenerate case of the window template — the shrink step moves left all the way to right in one jump instead of one element at a time. Recognizing this makes the harder questions in this section feel like the same machinery rather than new tricks.

Step 5 — The "no profit" case

If prices only fall, every candidate profit is negative. Initializing best = 0 and only ever taking a maximum against it means we never report a loss — which matches "return 0 if no profit is possible".

Step 6 — The alternative framing: Kadane

Consider the array of day-to-day differences:

prices = [7, 1, 5, 3, 6, 4]
diffs  =   [-6, 4, -2, 3, -2]

Buying on day i and selling on day j earns exactly the sum of the differences between them. So "maximum profit" is "maximum subarray sum of the differences" — which is Kadane's algorithm.

Same O(n), and it explains why the greedy works.

3. Solution Paths

Approach 1 — Brute force: try every pair

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

sell starts at buy + 1, enforcing "sell strictly after buy".

• Time: O(n²).
• Space: O(1).

Counter-questions on this approach

⭐ "What does the inner loop actually need from the outer one?"

Only one thing: the cheapest price before the sell day. Everything else about the earlier prices is irrelevant. Once I phrase it that way, the inner loop is just re-deriving a running minimum, which I can maintain in O(1) as I go.

"Why does sell start at buy + 1 rather than buy?"

Because you must sell on a strictly later day. Starting at buy would allow buying and selling the same day for zero profit — harmless to the answer here, since we clamp at 0, but it misrepresents the constraint.

Approach 2 — Track the minimum so far (optimal)

public int maxProfit(int[] prices) {
    int minSoFar = Integer.MAX_VALUE;
    int best = 0;

    for (int price : prices) {
        if (price < minSoFar) {
            minSoFar = price;                       // a cheaper buy day — move `left` here
        } else {
            best = Math.max(best, price - minSoFar); // sell today against the cheapest buy
        }
    }
    return best;
}

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

Answer: 5 ✓

Trace on prices = [7, 6, 4, 3, 1]: every price is a new minimum, so the else branch never runs and best stays 0. ✓

• Time: O(n) — one pass.
• Space: O(1) — two integers.

Counter-questions on this approach

⭐ "Why is this if/else rather than two unconditional updates?"

They're equivalent in result, and writing both unconditionally is also fine:

Java

minSoFar = Math.min(minSoFar, price);
best = Math.max(best, price - minSoFar);

If price is the new minimum, price - minSoFar is exactly 0, which can't beat best since best starts at 0. So the branch is an optimization, not a correctness requirement. I'd mention that I checked, because it's the kind of thing that looks like it might break.

⭐ "Why does best start at 0 rather than Integer.MIN_VALUE?"

Because the problem says to return 0 when no profit is possible. Starting at MIN_VALUE would report the least-bad loss on a falling market. This is the opposite convention from Kadane's algorithm on Maximum Subarray, where you must start at nums[0] because an all-negative array has a genuine negative answer. Same shape, different initialization — worth knowing why.

"You buy and sell in the same pass. How do you guarantee the buy came first?"

Because minSoFar only ever contains prices from days already processed. When I compute price - minSoFar, the minimum is drawn strictly from the past. The ordering constraint is enforced by the structure of the loop, not by an explicit check.

"Can minSoFar starting at Integer.MAX_VALUE cause an overflow in price - minSoFar?"

It can't be reached: on the first iteration price < minSoFar is always true, so the subtraction branch never runs while minSoFar is still MAX_VALUE. In the unconditional variant above, minSoFar is updated before the subtraction, so it's also safe. Worth verifying rather than assuming, since 0 - Integer.MAX_VALUE would be a real problem.

Approach 3 — Kadane on the difference array

public int maxProfit(int[] prices) {
    int best = 0, cur = 0;

    for (int i = 1; i < prices.length; i++) {
        int diff = prices[i] - prices[i - 1];
        cur = Math.max(0, cur + diff);      // drop the run if it goes negative
        best = Math.max(best, cur);
    }
    return best;
}

How it works. cur is the profit of the best trade ending today. If carrying the previous run forward would make it negative, abandon it and start fresh — that "restart" is exactly choosing a new buy day.

• Time: O(n).
• Space: O(1).

Counter-questions on this approach

⭐ "Why is Math.max(0, ...) correct here, when Kadane normally uses Math.max(nums[i], ...)?"

Because a run with negative cumulative profit is never worth continuing — you'd simply have bought later. Clamping at 0 encodes "abandon this trade and wait", which is legal since not trading is allowed. Standard Kadane on Maximum Subarray can't clamp at 0, because there you're forced to pick a non-empty subarray and an all-negative input has a negative answer.

"Is this better than tracking the minimum?"

No — same complexity, same space, and it needs an extra conceptual step (the difference array) to justify. I'd present it as the reason the greedy works, not as the implementation I'd ship.

Comparison

4. Why the Optimal Wins

Against brute force. The brute force re-derives "cheapest price before day j" for every j. The one-pass version maintains it incrementally — the defining move of the whole section. O(n²) → O(n).

Against sorting. Worth stating even though nobody proposes it seriously: sorting is unusable here because it destroys the day ordering, and the ordering is the constraint. Whenever a problem depends on sequence, sorting is off the table by construction.

Why O(n) is the floor. Every price must be examined — an adversary can put the optimal buy or sell day at any index you skip. So O(n) is optimal, and O(1) space is optimal because the entire relevant history compresses into one number.

The transferable principle:

When the inner loop only needs an aggregate of everything before it — a minimum, a maximum, a sum — that aggregate is a running value, not a re-scan.

That's the seed of every other question in this section.

5. Java Prerequisites

Sentinel initialization

int minSoFar = Integer.MAX_VALUE;    // "no minimum yet" — any real price beats it
int best = 0;                        // the problem's floor, not a sentinel

Two different purposes. minSoFar uses a sentinel that any input will replace; best uses 0 because that's the answer the problem demands when no trade is profitable.

An alternative avoiding the sentinel entirely:

int minSoFar = prices[0];
for (int i = 1; i < prices.length; i++) { ... }

Safe here because n >= 1 is guaranteed. With an empty array it would throw — so if the constraint didn't guarantee it, you'd need a length check.

Math.max / Math.min

best = Math.max(best, price - minSoFar);
minSoFar = Math.min(minSoFar, price);

Both overloaded for int, returning int — no accidental widening.

The enhanced for loop

for (int price : prices) { ... }

Correct here because we never need the index. If the follow-up asks which days to buy and sell, switch to an indexed loop and record the positions when best improves.

Overflow

Prices are bounded by 10^4, so price - minSoFar is at most 10^4 — nowhere near int limits. Worth confirming the bound rather than assuming; with unbounded values, 0 - Integer.MIN_VALUE would be the hazard.

6. Interview Communication Guide

Clarifying questions

1. "Can I make only one transaction — one buy and one sell?" — yes for this version, and the answer changes completely for the multi-transaction variants.
2. "Must the sell day be strictly after the buy day?" — yes, which is the ordering constraint that makes this a one-pass problem.
3. "What should I return if no profit is possible?" — 0, not a negative number. Confirm it.
4. "Can prices be zero or negative?" — the constraints say >= 0; real markets don't go negative but the algorithm wouldn't care.
5. "Do I return the profit, or the buy/sell days?" — the profit.

The pitch

"The brute force tries every buy/sell pair — O(n²), too slow at 10⁵.

But notice what the inner loop needs: for a given sell day, the best profit is today's price minus the cheapest price before it. That's the only thing the past contributes. So I can flip it around and ask, once per day, 'if I sold today, what's the best I could do?'

One pass: track the minimum price seen so far, and at each day compute price − minSoFar as a candidate answer. O(n) time, O(1) space.

The buy-before-sell constraint is enforced structurally — minSoFar only ever holds prices from days I've already processed.

I'll initialize best to 0 rather than MIN_VALUE, because the problem says to return 0 when no trade is profitable.

There's also a nice reframing: the profit from buying at i and selling at j is the sum of the day-to-day differences between them, so this is Maximum Subarray over the difference array — Kadane's algorithm. Same complexity, but it explains why the greedy is correct."

Edge cases to raise proactively

The falling-market case is the one to volunteer. It's what separates best = 0 from best = Integer.MIN_VALUE, and it's the only place the problem's "return 0" instruction bites.

[2,1,4] is worth a mention too — the minimum appears after a price that could already have been sold, proving the algorithm doesn't lock in an early buy day.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "What if you could make as many transactions as you like?" (LC 122)

Much easier, and counter-intuitively so. Sum every positive day-to-day difference: if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1]. Since you can buy and sell freely, capturing every upward move is optimal — there's no reason to hold through a decline. O(n) time, O(1) space.

"What if you're limited to at most two transactions?" (LC 123)

Now the greedy breaks — you must choose which two rises to take. State-machine DP with four states: after first buy, after first sell, after second buy, after second sell. Update all four per day. O(n) time, O(1) space.

"At most k transactions?" (LC 188)

Generalize the above to 2k states, or a dp[k][n] table. O(n · k) time. If k >= n/2 it degenerates to the unlimited case, which is an important shortcut — otherwise the table blows up for large k.

"What if there's a cooldown day after each sell?" (LC 309)

Three states — holding, just sold, free to buy — with the "just sold" state forced to wait a day before returning to "free". O(n) time, O(1) space. Covered in 19 — Dynamic Programming.

"What if each transaction charges a fee?" (LC 714)

Same unlimited-transaction structure, subtracting the fee on each sell. The greedy "take every rise" no longer works, because small rises can't cover the fee — so it becomes the two-state DP.

"What if prices stream in and you must answer at any moment?"

The min-so-far solution already works unchanged: keep minSoFar and best as fields, update on each arriving price, and the answer is always available. O(1) per price, O(1) memory. That the algorithm survives this untouched is a sign it's the right one.

"What if you had to return the buy and sell days, not the profit?"

Track the index of the current minimum, and record both indices whenever best improves. No complexity change — just switch from the enhanced for loop to an indexed one.