Best Time to Buy and Sell Stock
Walkthrough video coming soon
The full explanation is written out below — the problem, the intuition, the approach, and the solution code.
The problem
You are given an array `prices` where `prices[i]` is the price of a stock on day i. Maximize your profit by choosing one day to buy and a later day to sell. Return the maximum profit, or 0 if no profit is possible.
Constraints & assumptions
- 1 ≤ prices.length ≤ 10⁵
- 0 ≤ prices[i] ≤ 10⁴
In plain English
Imagine walking forward through the days, one at a time, unable to see the future. All you carry is a memory of the lowest price you've encountered so far. Each new day you ask one question: "if I had bought at that cheapest moment behind me and sold today, how much would I pocket?"
You keep the best answer you've ever seen. There's no need to compare every buy-day against every sell-day — the running minimum quietly collapses the entire search into a single stroll down the timeline.
What you need to know
The programming concepts this problem is built on:
How to approach it
- 1The brute-force idea: try every buy-day / later sell-day pair and keep the max profit.
- 2To do better, scan left to right while remembering the minimum price seen so far.
- 3At each day, the best sale today is (today's price − minimum so far).
- 4Keep the largest such profit; if it never goes positive, the answer is 0.
The solutions
2 waysThis one can be solved more than one way. Switch between the methods to compare — each summary explains how it differs.
Try every buy/sell pair. Correct but quadratic.
Two nested loops consider buying on day i and selling on any later day j, tracking the best difference. Clear, but too slow when there are many days.
class Solution {
public int maxProfit(int[] prices) {
int best = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
best = Math.max(best, prices[j] - prices[i]);
}
}
return best;
}
}