Best Time to Buy and Sell Stock — O(n) One-Pass Solution
Problem Statement
Given array prices where prices[i] is the stock price on day i, find the maximum profit from one buy and one sell. Return 0 if no profit possible.
Example
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5 # Buy at 1, sell at 6
Time Complexity
O(n)
Space Complexity
O(1)
The Intuition
Track min_price seen so far. At each day, compute profit = price - min_price. Update max_profit if it is bigger.
Solution Code
def maxProfit(prices):
min_price = float("inf")
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit#include <limits.h>
int maxProfit(int* prices, int n) {
int min_p = INT_MAX, max_p = 0;
for (int i = 0; i < n; i++) {
if (prices[i] < min_p) min_p = prices[i];
else if (prices[i] - min_p > max_p) max_p = prices[i] - min_p;
}
return max_p;
}function maxProfit(prices) {
let min = Infinity, max = 0;
for (const p of prices) {
min = Math.min(min, p);
max = Math.max(max, p - min);
}
return max;
}Frequently Asked Questions
Q: Why can't we use nested loops?
O(n²) is too slow for 10⁵ elements. The one-pass greedy approach tracks the historical minimum as we go, giving O(n).
Practice These Problems in a Real Curriculum
DoxaTech Hub's 10-month programme covers Data Structures, Algorithms, Python, C, SQL, and Full-Stack Development through 40 weeks of real, graded projects.
Get Started → More Problems