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.

EasyTime O(n) · Space O(1)

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.

Stock Prices
$7
Day 0
$1
Day 1
$5
Day 2
$3
Day 3
$6
Day 4
$4
Day 5
Statistics
Min Price
-
Max Profit
$0
Current Index
-
Progress
0/6
0%
Day 0 / 60%

Approach

  1. 1
    Track 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.
  2. 2
    Calculate the potential profit. For each price, calculate the profit if we sell at the current price (current price − minimum price).
  3. 3
    Update the maximum profit. Keep track of the maximum profit encountered so far. This greedy approach finds the optimal solution in one pass.

Solution

JavaScript
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: 5

Time & 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.