Best Time to Buy/Sell Stock: Maximizing Profit
The Prompt
You are given an array `prices` where `prices[i]` is the price of a given stock on the `i`th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve. If you cannot achieve any profit, return 0.
Understanding the Problem
Each element is the stock price on one day, and you get exactly one buy followed by one later sell. The brute force tries every buy/sell pair — O(n²). The reframe: if you are standing on day i deciding whether to sell today, the only buy day worth considering is the cheapest day you have seen so far.
That collapses the whole problem into two running values: minPrice (cheapest price seen up to now) and maxProfit (best sale found so far). One pass, updating both, answers the question.
The Interview Flow
Interviewer
Imagine you have an array of stock prices for consecutive days. How would you find the maximum profit you could make from one transaction (one buy, one sell)?
Candidate
I need to find the lowest price to buy and the highest price after that day to sell. A brute-force O(n^2) approach would be to check every possible pair of buy and sell days.
Interviewer
Right, but we can do better. How can you solve this in a single pass?
Candidate
I can iterate through the prices and keep track of two things: the minimum price found so far, and the maximum profit found so far. For each day, I can calculate the potential profit if I were to sell on that day (current price - minimum price so far). Then I update my maximum profit if this potential profit is higher. I also update my minimum price if the current price is lower than what I've seen.
Interviewer
That's exactly right. This is a classic one-pass approach. Let's get that coded.
Why does one pass with a running minimum work?
The invariant: after processing day i, minPrice is the true minimum of prices[0..i], and maxProfit is the best profit achievable selling on or before day i. Both are easy to maintain — a new price either lowers the minimum or offers a profit against it — and selling on day i against anything but the running minimum can only do worse.
Every valid trade has a sell day; when the scan reaches that day, the best matching buy day is already summarized in minPrice. So no pair is missed, in O(n) time and O(1) space — versus O(n²) for checking pairs explicitly.
One-Pass Solution
- Initialize two variables: `minPrice` to a very large number (or the first price) and `maxProfit` to 0.
- Iterate through the `prices` array.
- For each price, first check if it is lower than `minPrice`. If it is, update `minPrice` to this new lower price.
- Then, calculate the potential profit by subtracting `minPrice` from the current price.
- Compare this potential profit with `maxProfit`. If it is greater, update `maxProfit`.
- After iterating through all the prices, `maxProfit` will hold the maximum possible profit.
- Return `maxProfit`.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function maxProfit(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (const price of prices) {
if (price < minPrice) {
minPrice = price;
} else if (price - minPrice > maxProfit) {
maxProfit = price - minPrice;
}
}
return maxProfit;
}Explanation
Scan prices = [7, 1, 5, 3, 6, 4] once, tracking the cheapest day seen (min) and the best profit so far.
1Day 0 sets minPrice = 7. Day 1: price 1 < 7, so minPrice drops to 1. No sale yet — maxProfit stays 0.
2Day 2: selling at 5 against minPrice 1 gives 5 − 1 = 4 → maxProfit = 4. Day 3 offers only 3 − 1 = 2, so nothing changes.
3Day 4: 6 − 1 = 5 beats 4 → maxProfit = 5. Day 5 gives 4 − 1 = 3, no improvement. Answer: 5 (buy day 1, sell day 4).
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.