How do you find the maximum profit from buying and selling a stock once?
Scan once while tracking the lowest price so far. At each day, the best profit if you sell today is price minus that lowest price. Keep the maximum of those.
Explain it simply
You can only buy once and sell once later. Imagine looking at a Sensex chart with hindsight. For each day you would ask: if I sell today, what was the cheapest day before it? The gap between today and that cheapest day is your profit.
So walk left to right, remember the cheapest price seen, and compare today's price against it.
Example
function maxProfit(prices) {
let minPrice = Infinity;
let best = 0;
for (const price of prices) {
if (price < minPrice) minPrice = price;
else best = Math.max(best, price - minPrice);
}
return best;
}
console.log(maxProfit([7, 1, 5, 3, 6, 4])); // Output: 5
console.log(maxProfit([7, 6, 4, 3, 1])); // Output: 0Complexity
Time O(n), space O(1).
What to say in the interview
"I keep the minimum price seen so far and, for each day, compute the profit if I sold that day. The answer is the largest such profit, or 0 if prices only fall. One pass, O(n) time, O(1) space. Checking every buy and sell pair would be O(n squared)."
Common mistakes
- Taking the global minimum and global maximum without checking that the minimum comes first.
- Returning a negative number when no profit is possible.