This problem is worth more than its Easy tag suggests, because the reframing it teaches is the same one behind Kadane's algorithm and most one-dimensional DP. The brute force asks "which pair of days is best?". The linear solution asks "if I sell today, what is the best I could have done?" — and that question has a one-variable answer.
The problem
Given daily prices, you may buy once and sell once, and you must buy before you sell. Return the
maximum profit, or 0 if no profitable trade exists.
[7, 1, 5, 3, 6, 4] -> 5 buy at 1 (day 2), sell at 6 (day 5)
[7, 6, 4, 3, 1] -> 0 prices only fall — do not trade at all
[1, 2] -> 1
[5] -> 0 one day, no trade possibleNote the answer is never negative. You are allowed to decline to trade, and a solution that returns the "least bad" loss on a falling market has misread the problem.
The reframing
Checking every pair is two nested loops and O(n²). It is also doing obviously
redundant work: on [7, 1, 5, 3, 6, 4], once you know the cheapest price so far is
1, there is no reason to consider buying at 5, 3, or
6. Any sale after them would have been at least as profitable had you bought at
1.
So fix the sell day and ask what the best buy day was. The answer is always the same thing: the minimum price seen before today. That is a single running variable, and it makes the whole problem one pass:
price: 7 1 5 3 6 4
cheapest: 7 1 1 1 1 1 min of everything seen so far
profit: 0 0 4 2 5 3 price - cheapest
best: 0 0 4 4 5 5 running maximumBoth variables update in constant time, and neither needs to look backwards. That is the shape to
recognise — iterate over the right endpoint, keep the best left endpoint as a scalar — and
it is the same trick that turns Maximum Subarray from O(n²) into O(n).
Java
class Solution {
public int maxProfit(int[] prices) {
int cheapest = Integer.MAX_VALUE;
int best = 0; // 0, not MIN_VALUE: not trading is allowed
for (int price : prices) {
if (price < cheapest) {
cheapest = price; // a better day to have bought
} else if (price - cheapest > best) {
best = price - cheapest; // selling today beats anything so far
}
}
return best;
}
}The else is safe and worth understanding rather than copying: when today sets a new
minimum, today's profit against it is 0, which can never beat a best that
starts at 0. So there is nothing to check on that branch. Writing two independent
ifs is equally correct and slightly clearer — pick either, but be able to say why the
else loses nothing.
Initialising best to 0 is what encodes "you may decline to trade", and
it also makes the empty and single-element arrays work with no guard.
Python
class Solution:
def maxProfit(self, prices: list[int]) -> int:
cheapest = float("inf")
best = 0
for price in prices:
if price < cheapest:
cheapest = price
elif price - cheapest > best:
best = price - cheapest
return bestComplexity
O(n) time, O(1) space, one pass. The DP framing — an array
min[i] holding the cheapest price in the first i days — is the same
algorithm with O(n) space, and it is worth mentioning only to show you can then collapse
it: min[i] depends solely on min[i-1], so a single scalar replaces the
array. That collapse is a routine DP move and interviewers like seeing it named.
It is Maximum Subarray in disguise
Take the day-to-day differences of [7, 1, 5, 3, 6, 4] and you get
[-6, 4, -2, 3, -2]. The best single buy-sell pair is exactly the maximum-sum contiguous
subarray of that list — [4, -2, 3] = 5 — because a contiguous run of daily changes sums
to the price change over that span.
Knowing this is a good thing to say out loud. It does not make the code shorter, and it shows you see the problem's family rather than having memorised one answer.
The follow-ups
- Best Time to Buy and Sell Stock II (122) — unlimited transactions. Collapses to something even simpler: sum every positive daily change, because you can capture every upward move independently.
- III (123) and IV (188) — at most two, or at most
k, transactions. Genuine DP, with a state per transaction count and per holding/not-holding. - With Cooldown (309) and With Transaction Fee (714) — the same state machine with one extra state or one extra subtraction.
What the interviewer is checking
- That you get to one pass, and can explain why buying at anything other than the running minimum is pointless.
- That a falling market returns
0, not a negative number. - Empty and single-element arrays, ideally with no special case.
- That you can name the
O(n)DP and then collapse it toO(1). - Whether you spot the connection to Maximum Subarray.