Approach Summary
Track running minimum price. At each day, profit = price - min_so_far. Track max profit seen.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Brute Force (All Buy/Sell Pairs) | O(n²) | O(1) | Iterate over all possible buy days i and all future sell days j > i. |
| 2 Approach 2: One-Pass Greedy Tracking (Optimal) | O(n) | O(1) | Maintain minimum price seen so far and compute maximum potential profit at each day. |
Step 1: Baseline
Approach 1: Brute Force (All Buy/Sell Pairs)
Time: O(n²)
Space: O(1)
Consider buying on day i and iterate through every subsequent day j from i + 1 to n - 1. Calculate the difference prices[j] - prices[i] and update the maximum profit recorded. Because this nested loop performs n*(n-1)/2 iterations, it causes TLE on inputs with n = 10⁵.
Approach 1: Brute Force (All Buy/Sell Pairs) Implementation
Approach 1: Brute Force (All Buy/Sell Pairs)
class Solution {
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;
}
}class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
int n = prices.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
maxProfit = max(maxProfit, prices[j] - prices[i]);
}
}
return maxProfit;
}
};def max_profit(prices: list[int]) -> int:
n = len(prices)
max_p = 0
for i in range(n):
for j in range(i + 1, n):
max_p = max(max_p, prices[j] - prices[i])
return max_pfunction maxProfit(prices) {
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
}
}
return maxProfit;
} Step 2: Most Optimized
Approach 2: One-Pass Greedy Tracking (Optimal)
Time: O(n)
Space: O(1)
As we iterate from left to right, we maintain `minimumSoFar`. If we decide to sell on the current day i, our profit is maximized by having bought at `minimumSoFar`. Thus we compute `prices[i] - minimumSoFar` and update `maxProfit`. In a single pass, we guarantee finding the global maximum without looking back.
Approach 2: One-Pass Greedy Tracking (Optimal) Implementation
Approach 2: One-Pass Greedy Tracking (Optimal)
class Solution {
public int maxProfit(int[] prices) {
int minimumSoFar = prices[0];
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
minimumSoFar = Math.min(minimumSoFar, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - minimumSoFar);
}
return maxProfit;
}
}class Solution {
public:
int maxProfit(vector<int>& prices) {
int minimumSoFar = prices[0];
int maxProfit = 0;
int n = prices.size();
for (int i = 0; i < n; i++) {
minimumSoFar = min(minimumSoFar, prices[i]);
maxProfit = max(maxProfit, prices[i] - minimumSoFar);
}
return maxProfit;
}
};def max_profit(prices: list[int]) -> int:
min_so_far = prices[0]
max_profit = 0
for price in prices:
min_so_far = min(min_so_far, price)
max_profit = max(max_profit, price - min_so_far)
return max_profitfunction maxProfit(prices) {
let minSoFar = prices[0];
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
minSoFar = Math.min(minSoFar, prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - minSoFar);
}
return maxProfit;
}Edge Cases to Watch
- Strictly decreasing prices (e.g. [7, 6, 4, 3, 1]) where no profit is possible (returns 0)
- Array of length 1 (returns 0)
- Maximum price appears before the minimum price
- All prices identical
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- Single buy and sell, maximize profit
- Track min seen so far — greedy O(n)
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
Tags
Array Dynamic Programming
Frequently Asked Questions
What is the optimal time and space complexity for Best Time to Buy and Sell Stock?
The optimal solution for Best Time to Buy and Sell Stock achieves O(n) runtime complexity and requires O(1) auxiliary space. We scan the prices array once in linear O(n) time with simple min and max calculations per day. Auxiliary space is strictly O(1) as only two primitive integer variables are tracked.
How do I identify that Best Time to Buy and Sell Stock requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Single buy and sell, maximize profit; Track min seen so far — greedy O(n). Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Best Time to Buy and Sell Stock?
Essential edge cases to verify include: Strictly decreasing prices (e.g. [7, 6, 4, 3, 1]) where no profit is possible (returns 0); Array of length 1 (returns 0); Maximum price appears before the minimum price; All prices identical. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Best Time to Buy and Sell Stock?
Best Time to Buy and Sell Stock is a Easy-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Microsoft, Google, Apple.