Best Time to Buy and Sell Stock
Find the maximum profit you can achieve from buying and selling a stock once. Learn the greedy approach to track minimum price and maximum profit.
Problem Statement
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Examples
Interactive Visualizer
Approach
Track Minimum Price
Keep track of the minimum price seen so far as we iterate through the array. This represents the best day to buy.
Calculate Potential Profit
For each price, calculate the profit if we sell at the current price (current price - minimum price).
Update Maximum Profit
Keep track of the maximum profit encountered so far. This greedy approach ensures we find the optimal solution in one pass.
Solution
function maxProfit(prices) {
let minPrice = Infinity;
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
// Update minimum price seen so far
if (prices[i] < minPrice) {
minPrice = prices[i];
}
// Calculate profit if we sell at current price
else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
// Example usage
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // Output: 5Complexity Analysis
O(n)We traverse the array once, performing constant time operations at each step.
O(1)We only use two variables (minPrice and maxProfit) regardless of input size.
Ready for More Challenges?
Continue practicing with more array problems and master dynamic programming concepts.