Best Time to Buy and Sell Stock (LeetCode
Learn how to solve the Best Time to Buy and Sell Stock problem using Brute Force and the Optimal One Pass approach. Includes intuition, dry run, Java code, complexity analysis, interview tips, and production insights.
Introduction
Best Time to Buy and Sell Stock is one of the most frequently asked array interview questions.
Companies asking this problem include:
- Amazon
- Microsoft
- Meta
- Apple
- Adobe
- Walmart
- Goldman Sachs
This problem tests your ability to:
- Optimize from O(n²) to O(n)
- Track minimum values efficiently
- Think greedily
- Write clean production-ready code
It is also the foundation for many advanced stock trading problems.
Problem Statement
You are given an array where each element represents the stock price on a particular day.
You may:
- Buy once
- Sell once
Return the maximum profit possible.
If no profit can be made, return 0.
Example
Input
prices = [7,1,5,3,6,4]
Output
5
Explanation
Buy at 1
Sell at 6
Profit = 5
Approach 1 — Brute Force
Idea
Try buying on every day.
For each buy day,
try selling on every future day.
Keep track of the maximum profit.
Illustration
Buy Day
↓
Compare
↓
All Future Days
↓
Maximum Profit
Java Code
public class BestTimeToBuySellStockBruteForce {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
for (int j = i + 1; j < prices.length; j++) {
maxProfit = Math.max(
maxProfit,
prices[j] - prices[i]);
}
}
return maxProfit;
}
}
Complexity
| Complexity | Value |
|---|---|
| Time | O(n²) |
| Space | O(1) |
Not suitable for large datasets.
Approach 2 — Optimal One Pass
Core Idea
Instead of checking every pair,
keep track of:
- Minimum buying price seen so far
- Maximum profit so far
For every new price
Profit
=
Current Price
-
Minimum Price
Update both values while scanning only once.
Algorithm
Minimum Price = Infinity
↓
Read Current Price
↓
Update Minimum Price
↓
Calculate Profit
↓
Update Maximum Profit
Dry Run
Input
[7,1,5,3,6,4]
Day 1
Price = 7
Minimum = 7
Profit = 0
Day 2
Price = 1
Minimum = 1
Profit = 0
Day 3
Price = 5
Profit = 5 - 1
= 4
Maximum = 4
Day 4
Price = 3
Profit = 2
Maximum = 4
Day 5
Price = 6
Profit = 5
Maximum = 5
Day 6
Price = 4
Profit = 3
Maximum = 5
Final Answer
5
Java Code
public class BestTimeToBuySellStock {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
} else {
maxProfit = Math.max(
maxProfit,
price - minPrice);
}
}
return maxProfit;
}
}
Complexity
| Complexity | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Only one traversal is required.
Why Does This Work?
At every step we know:
Best Buying Price
↓
Current Selling Price
↓
Profit
↓
Maximum Profit
We never need to revisit previous elements.
Visual Explanation
Prices
7 1 5 3 6 4
↓
Minimum Price
7 1 1 1 1 1
↓
Profit
0 0 4 2 5 3
↓
Maximum
5
Edge Cases
Prices Always Decrease
[7,6,5,4,3]
Output
0
Single Element
[5]
Output
0
Same Prices
[4,4,4,4]
Output
0
Increasing Prices
[1,2,3,4,5]
Output
4
Production Applications
The same algorithm is useful in many real-world systems.
Examples
- Stock trading platforms
- Cryptocurrency exchanges
- Commodity price analysis
- Dynamic pricing engines
- Profit optimization
- Revenue analytics
- Cost optimization
- Financial dashboards
Common Interview Mistakes
❌ Buying after selling.
❌ Updating the minimum price incorrectly.
❌ Returning negative profit.
❌ Using nested loops after identifying an optimal approach.
❌ Forgetting to return 0 when no profit exists.
Follow-Up Questions
What if multiple transactions are allowed?
Use a greedy approach.
This becomes LeetCode 122.
What if only two transactions are allowed?
Dynamic Programming is typically used.
What if there is a cooldown period?
Use Dynamic Programming with state transitions.
What if each transaction has a fee?
Subtract the transaction fee while calculating profit.
Interview Tips
Interviewers commonly ask:
- Why is this O(n)?
- Why does keeping the minimum price work?
- Why not sort the array?
- Why can we solve it in one pass?
- What if prices decrease every day?
- Can you solve it with multiple transactions?
- Can you optimize the space further?
- Explain the dry run.
Always explain the intuition before writing code.
Summary
The Best Time to Buy and Sell Stock problem demonstrates how tracking the minimum value seen so far allows us to calculate the maximum possible profit in a single traversal. While the brute-force solution requires O(n²) comparisons, the optimal greedy approach achieves O(n) time and O(1) space, making it suitable for production-scale applications.
Key Takeaways
- Start with the brute-force solution.
- Optimize using a single traversal.
- Track the minimum price seen so far.
- Update maximum profit continuously.
- Never revisit previous elements.
- Return 0 when profit is impossible.
- Achieve O(n) time complexity.
- Use O(1) extra space.
- Explain the greedy intuition clearly.
- Practice the dry run for interviews.