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 that tracks the 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.
Example 1
Input: prices = [7, 1, 5, 3, 6, 4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.
Example 2
Input: prices = [7, 6, 4, 3, 1] Output: 0 Explanation: No transactions are done, i.e. max profit = 0.
Interactive visualizer
See the algorithm run step by step.
Approach
- 1Track the minimum price. Keep track of the minimum price seen so far as we iterate through the array. This represents the best day to buy.
- 2Calculate the potential profit. For each price, calculate the profit if we sell at the current price (current price − minimum price).
- 3Update the maximum profit. Keep track of the maximum profit encountered so far. This greedy approach finds 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: 5Time & space complexity
Time complexity
O(n)
We traverse the array once, performing constant-time operations at each step.
Space complexity
O(1)
We only use two variables (minPrice and maxProfit) regardless of input size.
Discussion
Questions, ideas or a different approach? Join the conversation.