Best Time to Buy and Sell Stock
Java coding interview problem for Array Logic: Best Time to Buy and Sell Stock.
The Best Time to Buy and Sell Stock problem is one of the most popular array and greedy algorithm interview questions.
It teaches important concepts:
- Finding minimum values
- Tracking maximum profit
- Greedy decision making
- One-pass optimization
- Dynamic programming foundations
This problem appears frequently in interviews at:
- Amazon
- Microsoft
- Meta
- Netflix
- Financial technology companies
What is Best Time to Buy and Sell Stock?
Given an array where each element represents the stock price on a particular day:
- Choose one day to buy.
- Choose a future day to sell.
- Maximize profit.
Example 1
Input:
prices = [7,1,5,3,6,4]
Best transaction:
Buy:
Day 2
Price = 1
Sell:
Day 5
Price = 6
Profit:
6 - 1 = 5
Output:
5
Example 2
Input:
prices = [7,6,4,3,1]
Stock keeps decreasing.
Best decision:
Do not buy
Output:
0
Understanding Stock Trading Problem
Consider:
Day:
1 2 3 4 5 6
7 1 5 3 6 4
Prices:
Day 1 → 7
Day 2 → 1
Day 3 → 5
Day 4 → 3
Day 5 → 6
Day 6 → 4
Possible transactions:
Buy:
7
Sell:
6
Loss:
-1
Buy:
1
Sell:
6
Profit:
5
Best choice:
Buy at minimum price.
Sell at future maximum price.
Why is This Question Asked in Interviews?
This problem tests:
1. Array Traversal
Can you process data efficiently?
2. Optimization Thinking
Can you avoid checking every possible pair?
3. Greedy Algorithms
Can you make the best decision at every step?
4. Time Complexity
Can you improve:
O(n²)
to:
O(n)
Real-World Applications
Stock Market Analysis
Finding the best historical trading opportunity.
Example:
Daily Prices:
$100
$80
$120
Best action:
Buy:
$80
Sell:
$120
Profit:
$40
Cryptocurrency Trading
Finding maximum gain period from price history.
Sales Analytics
Finding:
- Lowest purchase cost
- Highest selling opportunity
Business Planning
Finding:
- Best entry point
- Best exit point
Problem Statement
Given an array:
prices
where:
prices[i]
represents stock price on day i.
Find the maximum profit by choosing:
- One buying day.
- One selling day after buying day.
Return maximum profit.
Constraints
Example:
1 <= prices.length <= 100000
Price range:
0 <= prices[i] <= 100000
Rules:
- Buy before selling.
- Only one transaction allowed.
- Return 0 if no profit is possible.
Understanding Profit Calculation
Formula:
Profit = Selling Price - Buying Price
Example:
Buy:
$10
Sell:
$25
Profit:
25 - 10 = 15
Array Visualization
Input:
[7,1,5,3,6,4]
Graph:
Price
7 | *
6 | *
5 | *
4 | *
3 | *
2 |
1 | *
-------------------
1 2 3 4 5 6
Lowest point:
1
Highest future point:
6
Profit:
5
Brute Force Trading Logic
The simple approach:
Try every possible:
- Buy day
- Sell day
Calculate profit.
Keep maximum.
Example
Prices:
[7,1,5]
Possible combinations:
Buy:
7
Sell:
1
Profit:
-6
Buy:
7
Sell:
5
Profit:
-2
Buy:
1
Sell:
5
Profit:
4
Maximum:
4
Approach 1 — Brute Force Approach
Algorithm
- Select every buying day.
- Select every future selling day.
- Calculate:
sell - buy
- Store maximum profit.
Java Program
public class BestTimeStockBruteForce {
public static int maxProfit(
int[] prices) {
int maxProfit = 0;
for (int buy = 0;
buy < prices.length;
buy++) {
for (int sell = buy + 1;
sell < prices.length;
sell++) {
int profit =
prices[sell] -
prices[buy];
maxProfit =
Math.max(
maxProfit,
profit);
}
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices =
{7,1,5,3,6,4};
System.out.println(
maxProfit(prices));
}
}
Output
5
Step-by-Step Explanation
Input:
[7,1,5,3,6,4]
Buy:
7
Best sell:
6
Profit:
-1
Buy:
1
Sell:
6
Profit:
5
Buy:
5
Sell:
6
Profit:
1
Maximum:
5
Complexity Analysis
Two loops:
Time:
O(n²)
Space:
O(1)
Advantages
- Easy to understand.
- Good for beginners.
- Direct implementation.
Drawbacks
- Too slow for large datasets.
- Checks unnecessary combinations.
- Not interview optimal.
Approach 2 — Sorting-Based Thinking
A common incorrect idea:
- Sort prices.
- Buy minimum.
- Sell maximum.
Example:
Original:
[7,1,5,3,6,4]
Sorted:
[1,3,4,5,6,7]
Profit:
7 - 1 = 6
Looks correct.
But there is a problem.
Why Sorting Fails?
The buying day must come before selling day.
Example:
Input:
[7,6,4,3,1]
Sorted:
[1,3,4,6,7]
Sorting suggests:
Buy:
1
Sell:
7
Profit:
6
But this transaction is impossible.
The price was already decreasing.
Conclusion
Sorting destroys:
Time order
Therefore:
Do not sort.
Approach 3 — One Pass Greedy Approach (Optimal)
The optimal solution uses a greedy strategy.
Idea:
At every day:
- Track minimum price seen so far.
- Calculate profit if selling today.
- Update maximum profit.
Greedy Decision
At every price:
Ask:
If I sell today, what is my maximum possible profit?
Formula:
profit = currentPrice - minimumPrice
Example
Input:
[7,1,5,3,6,4]
Start:
minimum = 7
profit = 0
Day 2:
Price:
1
Update minimum:
minimum = 1
Day 3:
Price:
5
Profit:
5 - 1 = 4
Day 5:
Price:
6
Profit:
6 - 1 = 5
Maximum:
5
Java Program
public class BestTimeStockGreedy {
public static int maxProfit(
int[] prices) {
int minimumPrice =
Integer.MAX_VALUE;
int maximumProfit = 0;
for (int price : prices) {
if (price < minimumPrice) {
minimumPrice = price;
}
int profit =
price - minimumPrice;
maximumProfit =
Math.max(
maximumProfit,
profit);
}
return maximumProfit;
}
public static void main(String[] args) {
int[] prices =
{7,1,5,3,6,4};
System.out.println(
maxProfit(prices));
}
}
Output
5
Step-by-Step Explanation
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
Day 5:
Price:
6
Profit:
6-1=5
Final:
5
Complexity Analysis
Time:
O(n)
Space:
O(1)
Advantages
- Optimal solution.
- Single traversal.
- Constant memory.
- Interview preferred.
Drawbacks
- Only handles one transaction.
- Requires understanding of greedy logic.
Multiple Transactions Variant
The previous problem allowed:
Only one buy and one sell
Now consider:
You can buy and sell multiple times.
Example
Input:
prices = [7,1,5,3,6,4]
Transactions:
First transaction:
Buy:
1
Sell:
5
Profit:
4
Second transaction:
Buy:
3
Sell:
6
Profit:
3
Total Profit:
4 + 3 = 7
Output:
7
Greedy Logic
For unlimited transactions:
Whenever:
Tomorrow price > today price
take the profit.
Formula:
profit += prices[i] - prices[i-1]
Java Program
public class StockMultipleTransactions {
public static int maxProfit(
int[] prices) {
int profit = 0;
for (int i = 1;
i < prices.length;
i++) {
if (prices[i] >
prices[i - 1]) {
profit +=
prices[i] -
prices[i - 1];
}
}
return profit;
}
public static void main(String[] args) {
int[] prices =
{7,1,5,3,6,4};
System.out.println(
maxProfit(prices));
}
}
Output
7
Complexity Analysis
Time:
O(n)
Space:
O(1)
Unlimited Transactions Example
Input:
[1,2,3,4,5]
Profit:
(2-1)
+
(3-2)
+
(4-3)
+
(5-4)
Result:
4
Equivalent to:
Buy at 1
Sell at 5
Transaction Fee Variant
Another popular interview variation:
Every transaction has a fixed fee.
Example
Input:
prices = [1,3,2,8,4,9]
fee = 2
Without fee:
Profit = 8
After transaction fees:
Profit = 6
Dynamic Programming State
We maintain two states:
Hold State
Currently holding stock.
hold
Cash State
Currently not holding stock.
cash
State Transition
Buy:
hold =
max(
old hold,
cash - price
)
Sell:
cash =
max(
old cash,
hold + price - fee
)
Java Program
public class StockWithTransactionFee {
public static int maxProfit(
int[] prices,
int fee) {
int hold =
-prices[0];
int cash = 0;
for (int i = 1;
i < prices.length;
i++) {
int previousCash =
cash;
cash =
Math.max(
cash,
hold + prices[i] - fee);
hold =
Math.max(
hold,
previousCash - prices[i]);
}
return cash;
}
public static void main(String[] args) {
int[] prices =
{1,3,2,8,4,9};
System.out.println(
maxProfit(prices,2));
}
}
Output
8
Complexity Analysis
Time:
O(n)
Space:
O(1)
Cooldown Variant
Problem:
After selling stock, you cannot buy the next day.
Example
Transaction:
Buy
Sell
Wait one day
Buy again
Dynamic Programming States
Three states:
Hold
Holding stock.
Sold
Just sold stock.
Rest
Cooldown or no transaction.
State Transition
Hold:
max(
previous hold,
previous rest - price
)
Sold:
previous hold + price
Rest:
max(
previous rest,
previous sold
)
Java Program
public class StockCooldown {
public static int maxProfit(
int[] prices) {
int hold =
Integer.MIN_VALUE;
int sold = 0;
int rest = 0;
for (int price : prices) {
int previousSold =
sold;
sold =
hold + price;
hold =
Math.max(
hold,
rest - price);
rest =
Math.max(
rest,
previousSold);
}
return Math.max(
sold,
rest);
}
}
State Machine Explanation
Stock problems are often represented as:
Buy
Rest --------> Hold
^ |
| |
| |
+------ Sell --
Java Streams Approach
For one transaction, Streams are not naturally efficient because we need:
- Minimum price so far
- Maximum profit so far
Both require maintaining state.
Example:
Arrays.stream(prices)
can calculate:
maximum value
but cannot easily track:
minimum before current element
Mathematical Proof of Greedy Approach
For one transaction:
The optimal solution is:
maximum selling price
-
minimum previous buying price
At every day:
Track:
lowest price before today
Any better buying day would have already replaced it.
Therefore:
profit =
today price - minimum price
gives the optimal answer.
Comparison of All Approaches
| Approach | Problem Variant | Time | Space |
|---|---|---|---|
| Brute Force | One Transaction | O(n²) | O(1) |
| Greedy | One Transaction | O(n) | O(1) |
| Greedy | Unlimited Transactions | O(n) | O(1) |
| DP State Machine | Transaction Fee | O(n) | O(1) |
| DP State Machine | Cooldown | O(n) | O(1) |
Handling Edge Cases
Empty Array
Input:
[]
Output:
0
Single Day
Input:
[5]
Output:
0
Cannot sell without buying.
Always Decreasing
Input:
[7,5,3,1]
Output:
0
Always Increasing
Input:
[1,2,3,4]
Output:
3
Buy:
1
Sell:
4
Common Interview Mistakes
Mistake 1
Sorting prices.
Wrong:
Sort and find difference
Because order matters.
Mistake 2
Buying after selling.
Invalid:
Sell first
Buy later
Mistake 3
Using unlimited transaction logic for one transaction.
Example:
Input:
[1,5,2,6]
One transaction:
5
Unlimited:
8
Different answers.
Mistake 4
Ignoring transaction constraints.
Always clarify:
- One transaction?
- Multiple transactions?
- Fee?
- Cooldown?
Interview Follow-up Questions
Q1. Best time to buy and sell stock once.
Q2. Multiple transactions allowed.
Q3. Add transaction fee.
Q4. Add cooldown period.
Q5. Maximum two transactions.
Q6. Return buy and sell days.
Q7. Explain greedy proof.
Q8. Solve using dynamic programming.
Related Problems
- Maximum Subarray Sum
- Kadane's Algorithm
- Stock with Cooldown
- Stock with Transaction Fee
- Stock III (Two Transactions)
- Stock IV (K Transactions)
- Dynamic Programming Problems
Key Takeaways
The stock problem is a classic greedy and dynamic programming pattern.
For one transaction:
Track minimum price.
Calculate maximum profit.
Complexity:
Time: O(n)
Space: O(1)
For multiple transactions:
Capture every increasing segment.
For advanced constraints:
Use Dynamic Programming states.
Frequently Asked Interview Questions
Q1. What is the optimal solution for one transaction?
Greedy approach.
Time: O(n)
Space: O(1)
Q2. Why don't we use sorting?
Because the buying day must occur before the selling day.
Q3. What is the key idea?
Track:
Minimum price seen so far
and calculate:
Current price - minimum price
Q4. Is this dynamic programming?
The basic version is greedy.
Advanced versions:
- Fee
- Cooldown
- Multiple transactions
use dynamic programming.
Interview Tip
When asked:
"Best time to buy and sell stock."
First clarify the variation:
- One transaction?
- Multiple transactions?
- Transaction fee?
- Cooldown?
Then explain:
One Transaction:
Greedy
O(n) Time
O(1) Space
This demonstrates understanding of arrays, greedy algorithms, and dynamic programming state transitions.