March 24
Best Time to Buy and Sell Stock
How to move away from comparing every pair and notice that the problem only needs the lowest price so far.
Arrays and Single Pass Beginner 15 min TypeScript
You are given an array prices, where prices[i] is the price of a stock on day i. Return the maximum profit you can achieve by buying on one day and selling on a later day.
If no profit is possible, return 0.
Example:
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Buy at 1 and sell at 6.
What to notice before coding
- The buy must happen before the sell.
- The problem asks for the best profit, not a full list of trades.
- If prices only go down, the answer is `0`, not a negative number.
Common mistakes
- picking the global minimum even if it happens after the sell day
- returning a negative loss when the prompt asks for `0`
Step 1 — Read the most important constraint
Profit is sell - buy.
But not every combination is allowed.
The buy must happen before the sell.
That rules out a common bad reading: taking the minimum price in the whole array and the maximum price in the whole array without respecting time order.
Step 2 — Write the correct baseline
The first correct version compares each buy day with every later sell day:
export function maxProfit(prices: number[]): number {
let bestProfit = 0
for (let buyDay = 0; buyDay < prices.length; buyDay += 1) {
for (let sellDay = buyDay + 1; sellDay < prices.length; sellDay += 1) {
bestProfit = Math.max(bestProfit, prices[sellDay] - prices[buyDay])
}
}
return bestProfit
}
It works. But it rescans the rest of the array for every day.
Step 3 — Ask what the current day actually needs to know
When you reach today's price, do you need every earlier day?
No.
To compute the best profit if you sell today, only one thing matters:
what is the lowest price I have seen so far?
If you know that, the candidate profit for today is:
profit = currentPrice - minPriceSoFar
Step 4 — Update two pieces of information during one O(n) pass
During a single pass:
- keep the lowest price seen so far
- compute today's candidate profit
- update the best profit found
The whole problem fits in that loop.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function maxProfit(prices: number[]): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(1)
Solution 1 — Brute force O(n²)
Compare every buy day with every later sell day.
export function maxProfit(prices: number[]): number {
let bestProfit = 0
for (let buyDay = 0; buyDay < prices.length; buyDay += 1) {
for (let sellDay = buyDay + 1; sellDay < prices.length; sellDay += 1) {
bestProfit = Math.max(bestProfit, prices[sellDay] - prices[buyDay])
}
}
return bestProfit
}Correct, but too slow because it repeats too many comparisons.
Solution 2 — Single pass O(n)
If the current day only needs the lowest earlier price, store only that.
export function maxProfit(prices: number[]): number {
let minPrice = Infinity
let bestProfit = 0
for (const price of prices) {
minPrice = Math.min(minPrice, price)
bestProfit = Math.max(bestProfit, price - minPrice)
}
return bestProfit
}You walk the array once and keep exactly the two values that matter.
What to say in the interview
A strong short explanation would be:
The baseline compares every buy against every later sell and costs
O(n²). But for each day, I do not need every earlier price. I only need the lowest price so far. With that, I can compute the candidate profit inO(1)per day and solve the problem in one pass.
That shows that you:
- respected the time-order constraint
- identified the minimum information needed
- justified the optimization without skipping the reasoning
When this pattern shows up again
The same pattern comes back when you need to:
- keep the best value seen so far
- update the answer while scanning
- make decisions from simple accumulated state
- avoid extra structures when two variables are enough
The point is not memorizing
maxProfit.
The point is noticing when a running state during one pass is enough.